■126:F - XOR Matching(1770)
まず
0 = 0;
0 xor 1 = 1
以下、
0 xor 1 xor 2 xor ,,,,,,,,,,,, 2^N -1 = 0
です。
これに気がつくと
0,1,2,3....K-1,K+1........2^M-1,K,2^M-1,,,,,K-1,K+1,,,,,3,2,1,0,K
のように構築すれば良いことがわかります。
構築できないケースと、上に上げたような例外ケースは別処理。
■127:F - Absolute Minima(2003)
手元で実験を行うとグラフの形が見えてきます。
更新クエリで与えられたaの値のうち真ん中のものを答えればいいということがわかります。
ですが毎回毎回、sortしていると確実にTLEするので工夫が必要です。
今回ほしいのは真ん中のみなので、右集合と左集合をそれぞれ持っておけばいい。
なので、priority_queueを2本持っておけばいいですね。
f(x)の値は、左右のpriority_queueに詰まっている要素の合計値を持っておけば求まります。
maspyさんのSlopeTrickの記事を読むと本質的な理解が深まります。
■128:F - Frog Jump(2464)
これは流石に解説動画見たほうがいいですね。
言葉のみで説明するものではない。
ゴールの到達するまでに訪れた座標は以下のようになります。
0,A,A-B,2A-B,2A-2B,,,,,,,,,,,,,,,,,,,,,kA-kB,(k+1)A-kB = N-1
A-B = C と置くことで整理すると
0,A,C,A+C,2C,A+2C,,,,,,,,,,,,,,,A+(k-1)C,kC,A+kC = N - 1
となります。
kとCが決まればAが決まるので経路が決まります。
A = N - 1 - k*Cなことを考えると
0,N - 1- kC,C,N - 1 - (k-1)C,2C,,,,,,,,,,kC,N - 1
となります
k = 0
0,N-1
k = 1
0,N-1-C,C,N-1
k = 2
0,N-1-2C,C,N-1-C,2C,N-1
となることを考えるとCと固定してkを増加させていけば前の結果を利用しつつ
答えを求める事ができます。
■129:F - Takahashi's Basics in Education and Learning(2621)
行列累乗の形に持ち込む
(X,s)->(X*10^d+s,s+B)の形に遷移させられるような行列式を作れば良い
(dはsやs+Bの桁数)
■130:F - Minimum Bounding Box (2240)
変化イベントが発生する瞬間のみ抑えるとよい。
解説を書くのが面倒になった
