AtCoder Beginner Contest 198の感想
AtCoder Beginner Contest 198に参加しました。先週はABCが開催されなかったので、2週間ぶりのコンテストということでかなり緊張していました。結果はA,B,Cの3完で無事レートを伸ばせて一安心です。以下、簡単にコメントしていきます。
A問題 - Div
基本的にABCは前から解いていく方針を取っているので、一番最初に手を付けました。区別のないN個のモノを2人（ヒトは区別する）で分ける方法は何パターンあるのか？という問題。1問目ということでガチガチに緊張しており、N-2個の〇と1本の棒を描いてN-2+1C1と計算しました。
実は、2人で分けっこするので片方が貰う個数が確定した時点でパターンが確定し、その貰い方が1個～N-1個で解答のN-1通りが一瞬で求まるみたいです。最速の人は10秒で提出していたのでまだまだ無駄が削れそうです（）
B問題 - Palindrome with leading zeros
整数Nは回文か？ただし、先頭に0を付け放題。という問題。最初に思い付いたのは、Nの先頭に1個ずつ0をつけ足していって、その都度回文かどうかの判別をする方針。しかし、問題文をよく読んでみると「付け足す０の数」は問われていなかったので、Nの後ろにくっついている0を全部削除した時に回文の判定をする方針に変更。サンプルケースも一発であってたので、かなりいい感じに実装できたと思います！
ちなみに、公式解説は前者の解法、ユーザー解説は後者の解説をされていました。Nは高々10桁なので前者の方針で問題ないみたいです。ぐぬぬ
C問題 - Compass Walking
一回の操作で一定距離離れた場所にしか移動できない高橋君が目的地にたどり着く最小回数を求めよという問題。基本的に目的地までの最短距離＜(一回の移動距離)*(移動回数)となる最小の移動回数を求めればいいわけですが、C問題だと何かしら罠が敷かれがちなのでまだ安心はできません。ここで、円の定義が定点 Oからの距離が等しい点の集合でできる曲線なことを思い出して、1回の移動では原点中心の円上に目的地がないとたどり着けない（つまり円の内側に移動するには2回の移動が必要）ことに気づきました。（こちらのツイートが分かり易かったので引用させていただきます）
アライグマ「ABC198のwriterだったのだ！ C問題は、(X,Y)までのキョリをDとして、だいたいceil(D/R)が答えなのだ。D<Rのときは1歩じゃ行けないから、場合分けするのだ。2歩で行けることの証明は……この図を見たらわかるのだ！」 pic.twitter.com/QGLDCXHwy7
— 競技プログラミングをするフレンズ (@kyopro_friends) 2021年4月11日
かなりペナを出してる方が多かったのでノーペナで出せたのは結構嬉しかったです。
D問題 - Send More Money
覆面算をプログラミングで解きなさいという問題。方針が立たなかったので色々ググってみると、プログラミングの練習としては一般的（？）な課題らしく特定のケースでの実装例がたくさん出てきました。そんなこんなで、「各文字に対して0-9を割り当てて全探索すればいけそう！」というところまで行き着きましたが、与えられた文字に数字を割り当てる段階で実装に詰まってしまいそのままコンテスト終了。
E問題 - Unique Color
グラフということで飛ばしました。最短、電車、村、道あたりのワードが見えただけで目を逸らしたくなっちゃいます・・・。
順位表を眺める限り、D問題よりも解いている人が多いのでグラフの問題にも取り組んでいきたいです。
F問題
見てません。いつか全完してTLでのんびり余生を過ごしたいものです。
まとめ
今回はCからDで難易度の差があったので速解きで良いパフォーマンスが出ましたが、そろそろできることを増やさないと停滞しそうな感じがしています。その対策もこのブログを始めた目的の１つなので本業に影響しない程度に頑張ります！
