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が小さければ結構すぐに）無視できるということになる。（この問題もそれを利用して解く）

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

FII Code 2020 Round #3

　Bまでの二完でした。A, Bの後Dを考えていて、実装終わらずに終了。とはいえ、仕方ない面もある。

コンテストへのリンク
コンテスト後のツイート

（このブログの記事は、主に、当時の自分のツイートを参考にして書いています。なら、そのツイートも載せておいた方が良いのでは？　と思ったので、今後はできるだけ載せます）

Confused Robot

　これを飛ばしてDにいった。

　Sをひとまとめに見て、「それぞれの地点から、S一回分進むとどこへいくか？」を考えてダブリングするのが自然。

　が、これだとPython/PyPyで間に合うのか分からず（制限時間が長めなのも不安材料）飛ばした……んじゃないかと思う。あまり記憶にないけど。

　二個ほど他の人の提出を見たけど、大体そういう方針で解いているようだった。

　公式解説には、ダブリングを使わず、「S一回進んでも動かなくなる回数」を前計算すれば良いと書いてある気がする。けど、これって最大N*M回かかるのでは？　よく分かりません……。

　O(N*M*S)でいけるなら実装してみようと思ったけど、よく分からないので実装してません。

　ダブリング解でもPyPyでちゃんと書けばACできそう……？

追記）ダブリングなしで「S一回進んでも動かなくなる回数」は求められることに気付きました。グリッドの各マスについて、「S一回でどのマスにいくか」を調べておけば、

・S一回後に自分自身に戻るマスは0回（以後Sを実行しても動かなくなる）
・S一回後に0へ行くマスが1回

　という風にして、DFS/BFSで求められますね。

　ただ、それを求めても、「S一回進んでも動かなくなるギリギリの回数」は最大N*M回あると思うので、O(N*M*S)では無理な気が……。（やっぱりダブリングが必要では？）

Double Palindromes

　コンテスト中ずっと考えていて、コンテスト後実装が終了したので提出したらTLEでした。

　Manarcherの解説はすぬけさんの記事が分かりやすい。

　その上で、アルメリアさんが解説している方法が使えます（この解説の例題の中に、この問題があります）。いや、この記事は勉強になりますね……。こういう観点で問題を見たことがありませんでした。

　これを読むと、コンテスト中に考えていたセグ木を使う方法は本質的には間違っていなかったようですが、BITを使うことで高速化できそうです。

　というわけで、もしかするとアルメリアさんの方法を使えばTLEにならないのでは？　と思い実装してみたのですが、いつの間にか、CS AcademyではPyPy/Python3が使えなくなってました！（え？）

　「Non zero exit code = 127」というエラーが返ってきてどうしようもありません。

　Python3だとTLEなのは仕方ないですし……。まあ、しょうがないですね。

　勉強になったので良かったと思っておきます。

FII Code 2020 Round #2 (rated)

　Dまでの四完でした。まあ実力相応か。

コンテストへのリンク

Big String

こういう問題は実験してみるしかなさそう。
　実験してみると、「Sの最後の文字」が、一回目だけS[-1]でそれ以後はS[0]と分かります。

Connecting the Graph

　最小全域木を作るアルゴリズムをそのまま適用したのでは、計算時間が間に合わない。

　では、コストが小さいのはどういうものか？　と考えると、A_iとA_jの差が小さいとき。なので、Aをソートして、ソートした隣あった二項が候補。それらの差が小さい（つまり、コストが小さい）方から同じグループへ入れるかを決めていく。

Disproportionate Tree

　Kを二進数に直すのがポイント。

　あとは、下の桁から適切に割り振っていく感じで。

FII Code 2020 Round #1 (rated for all)

　約一年ぶりのCS Academyのコンテストでした。
　CS Academyは動的配点（解いた人数によって配点が変化）など、コンテストの仕組みは面白いのですが、問題の不備などは結構多い印象です。
　ただ、この一年の間にいつの間にかPyPyが使えるようになっていたのは嬉しかった。

　このコンテストはCまでの三完。Dは実質的にはできていたのですが……。

コンテストへのリンク

As easy as ABC

　配列Aが与えられ、そのうちのK個を+1したとき、中央値は最大いくつになるか、という問題。

　元々の中央値をMとすると、答えは高々M+1（全部に+1したとしても中央値は1しか増えないので）。

　結論としては、MがA中に何個含まれるかを調べれば良い。

　K個以上あればそのK個に+1することで、中央値も+1される。

Boring Operation

　$10^9/2$以上なら$10^9$から引く。

Cosmological Nightmare

　連鎖的に点が現れたり消えたりする場合に注意。

　逆に言えば、mod (x,y)$\in$ Vで一致している点の個数の偶奇を数えさえすればOK。

　その方針でACした提出

　コンテスト中は、一回移動したらどうなるか……みたいなことを考え、それで上手くいかなかったために解法に気付いた。そのせいで、コンテスト中のコードは無駄が多いものになってしまっている。

Driveaway

　コンテスト中、PyPyで提出してTLEでしたが、Python3で出せばACできました。PyPyだとheapq+tupleが遅いようです。注意。

　また、JOI春合宿2018　J - 飴 (Candies)とほとんど同じ内容だったようです。

　この問題のコードをそちらに合わせて修正すれば通りました。

　ただ、この問題の方が若干解法に辿り着きやすいかな、と思います。

　で、解法。

　おおまかに言えば、隣り合った二要素の和が最大になるものに貪欲にvoucher（商品券？）を使っていくのがベスト。ただし、voucherでの減額は最高Kなので、min(二要素の和, K)の最大値をheapqに入れて管理する。

　そして、単純に最大値を考えるのではなく、差分計算を考えなくてはダメ。

　たとえば、サンプル2。

・1 3 7 7 3 1

　なら、「3 7」「7 7」「7 3」のいずれかでK減額できる。たとえば、「7 7」にvoucherを使うと、残ったものは、

・1 3 3 1

　

　次にvoucherを使うのは「3 3」なのだけど、これにvoucherを使ったとき減額できるのは3+3=6ではない。実際は「3 7 7 3」に二回voucherを使っていることに注意。

　このとき、本当は「3 3」にvoucherを使っているのではない。でも、「7 3」「3 7」とvoucherを使えば「3 7 7 3」にvoucherを使うことは実現できる。

　そして、減額される額は、3+7+7+3から、前回までで減額されていた額10を引いた10となる。

　残りは、

・1 1

　で、最後にこの二つに使う。

　という感じでやればOK。

　あとは、実装だけれど、その際、ある数の左右に何があるか、を管理できれば良い。

　それを実現できるのが「隣接リスト」。それとも、「左右隣接リスト」と書いた方が良いのかな。（「隣接リスト」という名前は、以前Codeforcesでこういうデータ構造が必要な問題が出たときに、誰かがTwitterで使っていたのだけど、グラフ理論での隣接リストと意味的に対応しているのですね。なるほど。）

　つまり、その点から一つ左にある要素、右にある要素を持っておき、要素が取り除かれるごとにそれを更新していく。

　時々出てくるデータ構造なので、自分はしていないけど、ライブラリ化している人もいると思う。