ATC001A - 深さ優先探索

atcoder.jp

スタックを使って深さ優先探索を実装。深い＝sから遠い。次に調べる区画をスタックにプッシュしていき、調べ終わったらポップして前の区画に戻る、の繰り返し。

using System;
using System.Collections.Generic;

namespace ATC001A
{
    class Program
    {
        static void Main(string[] args)
        {
            var head = Console.ReadLine().Split(' ');
            var H = int.Parse(head[0]);
            var W = int.Parse(head[1]);
            var map = new char[W, H];
            var arrived = new bool[W, H];
            var start = new Point();
            for (var y = 0; y < H; y++)
            {
                var line = Console.ReadLine();
                for (var x = 0; x < W; x++)
                {
                    map[x, y] = line[x];
                    if (line[x] == 's')
                    {
                        start = new Point(x, y);
                        arrived[x, y] = true;
                    }
                }
            }

            var answer = "No";
            var stack = new Stack<Point>();
            stack.Push(start);
            Point current;
            while (0 < stack.Count)
            {
                current = stack.Peek();
                MarkAsArrived(current);

                if (IsFence(current))
                {
                    stack.Pop();
                    continue;
                }

                if (IsGoal(current))
                {
                    answer = "Yes";
                    break;
                }

                var east = new Point(x: current.X + 1, y: current.Y);
                if (CanArrive(east))
                {
                    stack.Push(east);
                    continue;
                }

                var west = new Point(x: current.X - 1, y: current.Y);
                if (CanArrive(west))
                {
                    stack.Push(west);
                    continue;
                }

                var north = new Point(x: current.X, y: current.Y - 1);
                if (CanArrive(north))
                {
                    stack.Push(north);
                    continue;
                }

                var south = new Point(x: current.X, y: current.Y + 1);
                if (CanArrive(south))
                {
                    stack.Push(south);
                    continue;
                }

                stack.Pop();
            }

            Console.WriteLine(answer);

            bool IsFence(in Point p) => map[p.X, p.Y] == '#';

            bool IsGoal(in Point p) => map[p.X, p.Y] == 'g';

            bool CanArrive(in Point p)
            {
                if (p.X < 0) return false;
                if (p.Y < 0) return false;
                if (p.X >= W) return false;
                if (p.Y >= H) return false;
                return !arrived[p.X, p.Y];
            }

            void MarkAsArrived(in Point p) => arrived[p.X, p.Y] = true;
        }

        readonly struct Point
        {
            public Point(int x, int y)
            {
                X = x;
                Y = y;
            }

            public readonly int X;

            public readonly int Y;
        }
    }
}

ABC002D - 派閥

atcoder.jp

N 人の議員がそれぞれ派閥に参加するかどうかのパターンは 2^N なので、ビット全探索を使ってみた。仮の派閥を作っておいて、全員がお互いに知り合いかどうかを調べる。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;

namespace ABC002D
{
    class Program
    {
        static void Main(string[] args)
        {
            var input = Console.ReadLine().Split(' ');
            var N = int.Parse(input[0]);
            var M = int.Parse(input[1]);
            var relations = new Vector2[M];
            for (var i = 0; i < M; i++)
            {
                var line = Console.ReadLine().Split(' ');
                var x = int.Parse(line[0]);
                var y = int.Parse(line[1]);
                relations[i] = new Vector2(x: x, y: y);
            }

            var answer = 0;
            for (var bit = 0; bit < (1 << N); bit++)
            {
                // 仮の派閥を作成する
                var faction = new List<int>();
                for (var i = 0; i <= N; i++)
                {
                    if ((bit & (1 << i)) != 0)
                    {
                        faction.Add(i + 1);
                    }
                }

                // 派閥が成り立つかチェック
                var success = true;
                for (var i = 0; (i < faction.Count) && success; i++)
                {
                    var x = faction[i];
                    for (var j = 0; j < faction.Count; j++)
                    {
                        var y = faction[j];
                        if (x == y)
                        {
                            continue;
                        }
                        // 知り合いじゃない組が存在したら派閥は成り立たない
                        if (!relations.Any(r => (r.X == x && r.Y == y) || (r.X == y && r.Y == x)))
                        {
                            success = false;
                            break;
                        }
                    }
                }
                if (success)
                {
                    answer = Math.Max(answer, faction.Count);
                }
            }

            Console.WriteLine(answer);
        }
    }
}

人間関係をビットで管理したら速くなりそうだったのでやってみたら、平均で 70ms 速くなった。

using System;
using System.Collections.Generic;
using System.Linq;

namespace ABC002D
{
    class Program
    {
        static void Main(string[] args)
        {
            var input = Console.ReadLine().Split(' ');
            var N = int.Parse(input[0]);
            var M = int.Parse(input[1]);

            // 人間関係をビットで管理
            var relations = new int[N];
            for (var i = 0; i < relations.Length; i++)
            {
                relations[i] = 1 << i;
            }
            for (var i = 0; i < M; i++)
            {
                var line = Console.ReadLine().Split(' ');
                var x = int.Parse(line[0]) - 1;
                var y = int.Parse(line[1]) - 1;
                relations[x] |= 1 << y;
                relations[y] |= 1 << x;
            }

            var answer = 0;
            for (var bit = 0; bit < (1 << N); bit++)
            {
                var faction = new List<int>();
                for (var i = 0; i < N; i++)
                {
                    if ((bit & (1 << i)) != 0)
                    {
                        // ビット演算で知り合いかどうかを判定
                        if (faction.Count == 0 ||
                            faction.All(x => (relations[i] & (1 << (x - 1))) != 0))
                        {
                            // 全員と知り合いのときだけ追加
                            faction.Add(i + 1);
                        }
                    }
                }
                answer = Math.Max(answer, faction.Count);
            }
            Console.WriteLine(answer);
        }
    }
}

ARC029A - 高橋君とお肉

atcoder.jp

焼く時間が長い順にソートしてから、2台の肉焼き機に振り分けた。

using System;
using System.Linq;

namespace ARC029A
{
    class Program
    {
        static void Main(string[] args)
        {
            var N = int.Parse(Console.ReadLine());
            var t = new int[N];
            for (var i = 0; i < N; i++)
            {
                t[i] = int.Parse(Console.ReadLine());
            }

            var descT = t.OrderByDescending(x => x).ToArray();
            var grill1 = descT[0];
            var grill2 = 0;
            for (var i = 1; i < descT.Length; i++)
            {
                var ti = descT[i];
                if (grill1 + ti > grill2 + ti)
                {
                    grill2 += ti;
                }
                else
                {
                    grill1 += ti;
                }
            }

            var answer = Math.Max(grill1, grill2);
            Console.WriteLine(answer);
        }
    }
}

でもこれ、よく考えると N 枚の肉を 2 台の肉焼き機のどちらで焼くかを、ビット全探索で調べればよかったな。別解。

using System;

namespace ARC029A
{
    class Program
    {
        static void Main(string[] args)
        {
            var N = int.Parse(Console.ReadLine());
            var t = new int[N];
            for (var i = 0; i < N; i++)
            {
                t[i] = int.Parse(Console.ReadLine());
            }

            var answer = int.MaxValue;
            for (var bit = 0; bit < (1 << N); bit++)
            {
                var grill1 = 0;
                var grill2 = 0;
                for (var i = 0; i < t.Length; i++)
                {
                    if ((bit & (1 << i)) != 0)
                    {
                        grill1 += t[i];
                    }
                    else
                    {
                        grill2 += t[i];
                    }
                }
                answer = Math.Min(answer, Math.Max(grill1, grill2));
            }
            Console.WriteLine(answer);
        }
    }
}

インベスターZ(1)〜(21)

だいぶ前に Kindle で凄く安くなっていて、まとめ買いしたはいいものの、積読してしまっていたのをようやくを消化。「ぜんぜんわからない。俺たちは雰囲気で株をやっている」のセリフが有名になってしまった本作だけど、実際はそんなセリフ登場しない。投資を題材にしたマンガで、株式投資を中心にしつつ、たまに FX や不動産や保険を扱ったりして、金融商品を広く浅く部分的に少し深く知ることはできる。当然ながら、このマンガを読んだからといって投資ができるようになるわけじゃない。まぁでも、お金の教育で子供に投資を学ばせるときの導入としてはいいかも。

ABC104C - All Green

atcoder.jp

1 〜 D の各難易度の問題を 1 問でも解くかどうかの組み合わせは 2^D 通り、と考えられなくもないので、ビット全探索を使ってみた。

using System;

namespace ABC104C
{
    class Program
    {
        static void Main(string[] args)
        {
            var DG = Console.ReadLine().Split(' ');
            var D = int.Parse(DG[0]);
            var G = int.Parse(DG[1]);
            var p = new int[D];
            var c = new int[D];
            for (var i = 0; i < D; i++)
            {
                var pci = Console.ReadLine().Split(' ');
                p[i] = int.Parse(pci[0]);
                c[i] = int.Parse(pci[1]);
            }

            var min = int.MaxValue;
            for (var bit = 0; bit < (1 << D); bit++)
            {
                var restScore = G;
                var count = 0;
                for (var i = D - 1; i >= 0; i--)
                {
                    if ((bit & (1 << i)) != 0)
                    {
                        for (var j = 0; j < p[i]; j++)
                        {
                            count++;
                            restScore -= 100 * (i + 1);
                            if (restScore <= 0)
                            {
                                min = Math.Min(count, min);
                                break;
                            }
                        }

                        restScore -= c[i];
                        if (restScore <= 0)
                        {
                            min = Math.Min(count, min);
                            break;
                        }
                    }

                    if (restScore <= 0)
                    {
                        min = Math.Min(count, min);
                        break;
                    }
                }
            }

            Console.WriteLine(min);
        }
    }
}

ARC061C - たくさんの数式

atcoder.jp

入力文字列 S の長さを N として、文字と文字の間に '+' が入るまたは入らないパターンは全部で 2^N-1 通り。2^N 通りの全探索で有効なビット全探索を使ってみた。

using System;
using System.Collections.Generic;

namespace ARC061C
{
    class Program
    {
        static void Main(string[] args)
        {
            var S = Console.ReadLine();
            var bitLength = S.Length - 1;
            var answer = 0L;
            for (var bit = 0; bit < (1 << bitLength); bit++)
            {
                var buf = new List<char>();
                for (var i = 0; i < S.Length; i++)
                {
                    buf.Add(S[i]);
                    if ((bit & (1 << i)) != 0)
                    {
                        answer += long.Parse(buf.ToArray());
                        buf = new List<char>();
                    }
                }
                if (buf.Count > 0)
                {
                    answer += long.Parse(buf.ToArray());
                }
            }
            Console.WriteLine(answer);
        }
    }
}

ARC004A - 2点間距離の最大値

atcoder.jp

単純に全探索すれば良い。座標の格納には System.Numerics.Vector2 を使った。2点間距離の計算が Vector2.Distance 一発で済んで楽。

using System;
using System.Numerics;

namespace ARC004A
{
    class Program
    {
        static void Main(string[] args)
        {
            var n = int.Parse(Console.ReadLine());
            var v = new Vector2[n];
            for (var i = 0; i < n; i++)
            {
                var l = Console.ReadLine().Split(' ');
                v[i] = new Vector2(
                    x: int.Parse(l[0]),
                    y: int.Parse(l[1]));
            }

            var a = 0.0d;
            for (var i = 0; i < v.Length; i++)
            {
                for (var j = 0; j < v.Length; j++)
                {
                    var d = Vector2.Distance(v[i], v[j]);
                    a = Math.Max(a, d);
                }
            }
            Console.WriteLine(a);
        }
    }
}