コンテスト後のツイート
B A[i]が今までのMINより小さいなら、A[i]をMINまで増やし、そこでとっておく値（POと呼ぶ）は後で使い切りたい。A[i]がMINより大きいときは、まず使っていないPOを使い（その次にPO2を使い）、足りなければMINを上昇させて対応。そこで余った値（PO2）は適宜使う。最終的にPO=0にときYes
— titia (@titia_til) October 13, 2024
C - Sum of Three Integers
解説放送を見てAC。
FFTは全く考えなかったが、登場回数の配列同士を畳み込めば、二つの配列の和の要素の登場回数になる……というのは初見ではなかったかもしれない（よく覚えていないが）。これは身に着けておきたい。
ただ、解法が分かった後もACに非常に苦労した。ランダムケースで実行しても何で落ちているのかが分からず、かなりたくさん提出デバッグをしてしまった。
・PythonでFFTを使うなら、配列をnumpy.arrayで書き、np.fft.rfft(A,k)やnp.fft.irfft(f)を使うと速い。
・畳み込み後の要素の値が大きくなることがあるため、np.fft.rfft(A,k)のkの値をギリギリに取るのではダメ。最大値をきちんと見積もる。
このあたりが問題だった。気を付けないと。
D - Random Walk on Tree
解説放送を見てAC。
解説放送で一番難しいといっていたパートは、ChatGPTに「ランダムウォークで、スタート地点からn歩の点にはじめて到達する歩数の期待値を教えて下さい。」と聞いたら、「スタート地点 0 から n に初めて到達するまでの期待値は、1次元ランダムウォークでは次のように表せます:
・En=n^2 つまり、最初に n に到達するための期待歩数は n^2 です。」と正しい返事がきた。
また、コンプガチャについてはけんちょんさんの記事など詳しいものがある。
どちらも、自力で導出できると良いけど、覚えておいても良いくらいの内容な気がする。
なので、対称性に関する考察さえきちんと行ってどんな問題に帰着できるか分かれば、あとは知識（もしくは調べて）で解けたんですね。
E - Adjacent GCD
解説放送を見てAC。
約数包除を行うとき、各素数についての他次元平面と考えると分かりやすい、というのは知っていた（が、コンテスト中は出てこなかった）。
で、約数包除のとき、あるxについて、その約数に関する値の総和を取るとxになるような値があると良い。そういうのがあれば、毎回包除をして約数の個数^2の計算時間をかけず、約数の箇所にある値の和を取る/値を書き込むさえすれば、毎回約数の個数回の計算時間で済む。
それを実現するのが、オイラーのトーシェント関数だった！
オイラーのトーシェント関数の定義を考えれば簡単に分かることなのだが、はじめて知りました。
約数包除に関して理解できた気がするので、もう忘れないといいな……。
なお、今回の問題は、100000までのトーシェント関数の値と約数のリストを予め列挙してACしました。
0 件のコメント:
コメントを投稿