第10回日本情報オリンピック予選（オンライン）E - チーズ (Cheese)

atcoder.jp

1→2→…→N と順番に辿っていけばいい。答えは「(S から 1 までの距離) + (1 から 2 までの距離) + … + (N - 1 から N までの距離)」になるので、幅優先探索による全探索を、開始地点を変えながら繰り返す。

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

namespace JOI2011YO_E
{
    class Program
    {
        static void Main(string[] args)
        {
            var HWN = Console.ReadLine().Split(' ');
            var H = int.Parse(HWN[0]);
            var W = int.Parse(HWN[1]);
            var N = int.Parse(HWN[2]);
            var grid = new List<string>();
            Point? s = null;
            for (var y = 0; y < H; y++)
            {
                var row = Console.ReadLine();
                grid.Add(row);

                if (s == null)
                {
                    for (var x = 0; x < row.Length; x++)
                    {
                        if (row[x] == 'S')
                        {
                            s = new Point(x, y);
                        }
                    }
                }
            }

            // S から 1 までの距離を幅優先探索で計測
            // 1 から 2 までの距離を幅優先探索で計測
            // …
            // N - 1 から N までの距離を幅優先探索で計測
            var answer = 0;
            for (var goal = '1'; goal <= '0' + N; goal++)
            {
                var dist = new List<List<int>>();
                for (var i = 0; i < H; i++)
                {
                    dist.Add(Enumerable.Repeat(-1, W).ToList());
                }

                var queue = new Queue<Point>();
                queue.Enqueue(s.Value);
                dist[s.Value.y][s.Value.x] = 0;
                while (queue.Count > 0)
                {
                    var current = queue.Dequeue();
                    foreach (var next in current.GetNext())
                    {
                        if (next.x >= 0 &&
                            next.x < W &&
                            next.y >= 0 &&
                            next.y < H &&
                            grid[next.y][next.x] != 'X' &&
                            dist[next.y][next.x] == -1)
                        {
                            dist[next.y][next.x] = dist[current.y][current.x] + 1;
                            if (grid[next.y][next.x] == goal)
                            {
                                answer += dist[next.y][next.x];
                                s = next;
                                queue.Clear();
                                break;
                            }
                            else
                            {
                                queue.Enqueue(next);
                            }
                        }
                    }
                }
            }

            Console.WriteLine(answer);
        }
    }

    readonly struct Point
    {
        public Point(int x, int y) => (this.x, this.y) = (x, y);
        public readonly int x;
        public readonly int y;

        public IEnumerable<Point> GetNext()
        {
            yield return new Point(x - 1, y);
            yield return new Point(x + 1, y);
            yield return new Point(x, y - 1);
            yield return new Point(x, y + 1);
        }
    }
}

ぼくたちは勉強ができない(19)

19巻は文乃ルート。他人の気持ちに聡いために、うるかと理珠の恋心に気づいて板挟みになり、自分の気持ちを押し殺そうとする姿が不憫だった。

それでも完璧に押し殺すことはできずに気持ちが溢れ、少しでも成幸の側にいたいためについた、嘘とも呼べないようなささやかな嘘が健気。

そんな文乃は最終的に理珠とうるかに背中を押されるわけだけど、誰が成幸の隣になろうとも揺るがない友情が 3人の間に存在していて尊い。そして文乃の秘めた恋心が報われてよかったと思える結末。この文乃ルートが本編でも何ら問題ないと思えた。

ぼくたちは勉強ができない 19 (ジャンプコミックスDIGITAL)

ABC007B - 辞書式順序

atcoder.jp

'a' を出力すれば、入力 A のほとんどのケースで正解になってしまう。例外は入力 A が 'a' のとき。そのときは -1 を出力するしかない。プログラミングコンテストは時間との勝負でもあるので、簡単な方法で解けそうなら、その方法を選んで時間を短縮すべし、ってことかな。

using System;

namespace ABC007B
{
    class Program
    {
        static void Main(string[] args)
        {
            var A = Console.ReadLine();
            var answer = A == "a" ? "-1" : "a";
            Console.WriteLine(answer);
        }
    }
}

アカシア

iTunes Store で先行配信されたので購入。 スペシャルMV「GOTCHA！」のタイアップで、ポケモン視点の歌詞が「ずっと隣にいてくれる相棒」感溢れていて鳥肌モノだった。聞けば聞くほど味わいが出てくるスルメみたいな良曲*1。

単体で聞いても素晴らしいんだけど、YouTube で公開されているMVを見ると、良さがさらに引き立つ。曲と映像がお互いを高めあってる感じ。作品の世界観を曲で見事に表現する才能は相変わらず流石だなぁ。

【Official】Pokémon Special Music Video 「GOTCHA！」 | BUMP OF CHICKEN - Acacia

アカシア

• BUMP OF CHICKEN
• J-Pop
• ¥255
• 

• provided courtesy of iTunes

*1:過去に隠しトラックでイカを収録したことがあるくらいなので褒め言葉

Gravity

9月入ってすぐにリリースされていたのを知らなくて、遅れて購入。アニメーション映画『思い、思われ、ふり、ふられ』主題歌で、映画と原作どちらも見ていないけど、作品をリスペクトした良い意味のネタバレソングだったりするんだろうな。

購入した時期が時期だけに、メロディと歌詞がチャマの件での、バンプの残るメンバーやファンの心情を表していると勘違いしてしまう。1ファンとしては幼なじみ4人揃ってこその BUMP OF CHICKEN と思っているので、チャマが禊を済ませて戻ってくる日を待ちたい。

Gravity

• BUMP OF CHICKEN
• J-Pop
• ¥255
• 

• provided courtesy of iTunes

ABC091B - Two Colors Card Game

atcoder.jp

カードの文字列を読み込みながら、その文字列が言われたとき何円もらえるかを計算しておく。

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

namespace ABC091B
{
    class Program
    {
        static void Main(string[] args)
        {
            var N = int.Parse(Console.ReadLine());
            var cards = new Dictionary<string, int>();
            for (var i = 0; i < N; i++)
            {
                var s = Console.ReadLine();
                if (cards.ContainsKey(s))
                {
                    cards[s]++;
                }
                else
                {
                    cards[s] = 1;
                }
            }
            var M = int.Parse(Console.ReadLine());
            for (var i = 0; i < M; i++)
            {
                var s = Console.ReadLine();
                if (cards.ContainsKey(s))
                {
                    cards[s]--;
                }
                else
                {
                    cards[s] = -1;
                }
            }

            var answer = Math.Max(0, cards.Values.Max());
            Console.WriteLine(answer);
        }
    }
}

ABC088D - Grid Repainting

atcoder.jp

幅優先探索でスタート地点からの距離を測ってみた。ゴール地点の距離が判明していたら到達可能と判断できる。

ゴール地点の距離 + 1 が必須の白いマスで、それ以外の白いマスは黒に塗りつぶせる。あらかじめ白いマスの数を数えておき、ゴール地点の距離 + 1 を引けばいい。

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

namespace ABC088D
{
    class Program
    {
        static void Main(string[] args)
        {
            var HW = Console.ReadLine().Split(' ');
            var H = int.Parse(HW[0]);
            var W = int.Parse(HW[1]);
            var grid = new List<string>();
            var dist = new List<List<int>>();
            var whiteCount = 0; 
            for (var i = 0; i < H; i++)
            {
                var row = Console.ReadLine();
                grid.Add(row);
                whiteCount += row.Count(c => c == '.');
                dist.Add(new List<int>(Enumerable.Repeat(-1, W)));
            }

            dist[0][0] = 0;
            var queue = new Queue<(int x, int y)>();
            queue.Enqueue((0, 0));
            while (queue.Count > 0)
            {
                var current = queue.Dequeue();
                foreach (var next in GetNext(current))
                {
                    if (next.x >= 0 &&
                        next.x < W &&
                        next.y >= 0 &&
                        next.y < H &&
                        dist[next.y][next.x] == -1 &&
                        grid[next.y][next.x] == '.')
                    {
                        dist[next.y][next.x] = dist[current.y][current.x] + 1;
                        queue.Enqueue(next);
                    }
                }
            }

            var answer = -1;
            var goalDist = dist[H - 1][W - 1];
            if (goalDist != -1)
            {
                answer = whiteCount - goalDist - 1;
            }
            Console.WriteLine(answer);
        }

        static IEnumerable<(int x, int y)> GetNext((int x, int y) c)
        {
            yield return (c.x - 1, c.y);
            yield return (c.x + 1, c.y);
            yield return (c.x, c.y - 1);
            yield return (c.x, c.y + 1);
        }
    }
}