AtCoder Beginner Contest 206（Sponsored by Panasonic）
久しぶりにABC受験記をしたためています。今更ながらコンテストに”受験記”ってどうなんだろうと思い始めていますが、もうええかという感じです。
A - Maxi-Buying
問題文の通り、math.floor(1.08 * N)を計算して206円と大小判定しました。108 * N//100の方がシンプルでしたね。計算した金額を格納する変数名を何にするか悩んで15秒ぐらい使ったと思います。結局moneyにしました。
B - Savings
単純なforループの問題と思い解こうとしたところ、何やら制約が気になり始めました。だと…？間に合うのかこれは…？そこからO(1)解法を探して方程式を解いている途中で、「実は愚直にループ回しても大丈夫じゃないか？」と気付き実装。ローカル環境でのケースを試して一瞬で処理が終わることを確認。ACでした。Writerの物理好きさんは意図的にこのような制約にされたようですね。まんまと引っかかりました。あとこの問題でもAtCoDeerくんが貯めた金額を格納する変数名で悩んでしまいました。結局moneyにしました。
コンテスト終了後に解説読んでたら、二分探索でもっと早く解けるんですね。いろんな解き方があって面白いです。
C - Swappable
Bで時間を使ったので焦りながら解きました。極力早解きにこだわらないように心がけてるんですが、Dがたまにしか解けない今の実力だと、どうしてもCを何分で解けるか、というのが頭を過りますね。
問題見て、大体こういう数え上げ問題は各数字の出現頻度を使うんだろうなと思いながらPythonのCounterを引っ張ってきました。結局、全組み合わせ数であるから、Counterで数えた各要素の出現頻度をとした時のをそれぞれ引いていけば答えが求まりました。
この間整備したのライブラリが早速役立ちました。
def nCr(n, r):
res = 1
for i in range(r):
res = (res*(n-i))//(i+1)
return resD - KAIBUNsyo
頑張って考えたんですが解けませんでした。解説見たら、なんとUnion-Findが使えるんですね！回文の問題をグラフで考えるという発想が1ミリも無くて、本当に感動しました。与えられた問題をいかに知っている問題に帰着させるかの重要性を痛感しますね。とても良い問題だと思ったので、DFSの解き方も含めて復習したいと思います。
以上、ABC206は3完ノーペナでした。
最近の精進の話
余談ですが、最近は久しぶりにABCのCD問題埋めをしています。C問題は即答できる問題が多くなり、D問題も茶Diffだと結構戦えているので、進歩を感じて嬉しいです。また、気が向いた時にE8さんの典型90問を解いたりもしています。日本語の良いコンテンツが見つかってきたのでEducational Codeforces埋めは一旦中止です。
それとは別に、邪道かも知れませんが見たことのある問題を増やすという意味で、GeeksforGeeksにある大量の典型DP問題一覧を眺めてます。
というのも、DPで解ける問題に関しては、まずその問題がDPで解けることに気づくところが始まりだと思っているからです(全問題そうでしょうが個人的にDPは特にそう)。
その意味で、競プロ頻出のDPに関してはまず多くの典型に触れるということを重視したいと思っています。
以上です。