AtCoder Beginner Contest 203（Sponsored by Panasonic）

　Eまで五完。Fも解けるべきだったが、最近ABCの成績が低迷したことを考えれば、まあ満足すべきか。

コンテストへのリンク

コンテスト後のツイート

F - Weed

　コンテスト後、

・青木君は配列の前と後ろのみ刈れば良いと勘違いしていた、

・DPを使う

　というツイートを見たら分かってACできました。

　前者は全く同じ勘違いをしていた。この勘違いがなければDPは思いつけたんじゃないか、とは思うけど、一度嵌ると抜けにくい勘違いな気もする。

　まず、Aはソートしておく。

　高橋君だけが草を刈ることを考えると、$A_i$を切るとき一つ前に切っているのは、$A_i*2$以下のもの。このようなもののうち最大のものを持つ配列を用意する。

　まあ、ダブリングするときの、一番最初に用意する配列ですね。

　これを用いて、DPする。

　$DP[i][j]$で、高橋君が$i$回操作したとき、青木君は最低でも何本草を刈らねばいけないか、とする。

　$i$が変わらないところは、1ずつ増えていく感じで。$i$が増える方向の遷移は、事前に用意した配列を使えばできます。

京セラプログラミングコンテスト2021（AtCoder Beginner Contest 200）

　Dまで四完。だが、そのDもafter_contestで落ちた。

コンテストへのリンク

コンテスト後のツイート

D - Happy Birthday! 2

　たとえば数列Aの値がランダムなら、配列の長さが長くても、mod 200がすぐに埋まりそうなことは分かる。なので、DP[x]に、和のmod 200がxになるような部分列を入れていき、二通りの表し方が登場したら、それを出力すれば良い。

　……のだが、まずい実装をしていたため、BやCの長さが1のときにおかしくなってしまった。

E - Patisserie ABC 2

　snukeさんの解説動画を見てAC。

　時間をかけて頑張ればできる、とは思ったけど、良い方法があるのかな？　と動画を見て正解だった。

　

　「和がSになる個数」を求めるのが重要だけど、こういう$l\leq x\leq r$みたいなものを求めるときは包除原理を使うのが定石らしい。

　ほえ～、知らなかった。

　それさえ分かれば後は簡単……なはずだけど、コンテスト中は、その後も二分探索とかしなくちゃいけない気がしていた（こともあって飛ばした）。その後は簡単、というのはちゃんと分かっておくべきだった。

F - Minflip Summation

　snukeさんの解説動画を見てAC。

　これはコンテスト中考えたことで大体あっていた。

　S[0]とS[-1]が一致するか異なるか……といったあたりの場合分けがおかしかったと思う。

　時間内に解けるべき問題だった。

　あと、解説ACにもかかわらず、文字数が一文字のときに引っ掛かってWAを出してしまったのも反省。Dと似たミスですね。注意しましょう。

Divide by Zero 2021 and Codeforces Round #714 (Div. 2)

　Dまで四完。

　Eは「全部同じ数字のとき」の場合分けが抜けていてWAになっていただけで、解法は合っていた。

コンテストへのリンク

コンテスト後のツイート

F. Swapping Problem

　コンテスト後、自力で解こうと考えていたけれど、AtCoder Regular Contest 119で類題が出題されたので、コンテスト中に公式解説を読んだ。

　結果、その問題をACできたため、ARCで良い成績を取れたのだけど、もし解けなければ復習していなかったのを後悔するところだった……。

　maspyさんがツイートしているように、区間の交わり方は3通り（交わらない/片方が片方を内包する/普通に（？）交わる）しかない、ということに思いを馳せることが重要。

　そうすると、

・$A[i]\geq B[i]$

・$B[i]\geq A[i]$

　で場合分けするという方針は結構自然か。

　その場合分けさえできれば、後の考察は、やや煩雑だが難しくはない。

FIICode 2021 Round #2

 　二完でした。

コンテストへのリンク

Clown Fiesta

　解説AC。

　「オイラーのφ関数」に関する理解が乏しかった。

　Editorialにある次の式は覚えておいてもいいと思う。

・$a^b = a^{b \,\,\mathrm{mod}\,\, \varphi (m)}(\mathrm{mod}\,\,m)$

・$a^{b^c} = a^{b^{c \,\, \mathrm{mod}\,\,\varphi (\varphi (m))} \,\,\mathrm{mod} \,\,\varphi (m)}(\mathrm{mod}\,\,m)$

（もちろん、「覚えておいてもいい」は言葉の綾で、「オイラーのφ関数を使う」ということさえ記憶しておけば導出は簡単なので覚える必要はない）

　これをふまえると、mod mで考えるとき、ベキ乗の肩にたくさんの数が乗っていても途中から（それも、mが小さければ結構すぐに）無視できるということになる。（この問題もそれを利用して解く）

　競技プログラミングをやっていれば知っていて当然の知識だろうけど、ちょっと驚いた。