ABC-F略解(126-130)

■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)
変化イベントが発生する瞬間のみ抑えるとよい。
解説を書くのが面倒になった

ARC-C問題埋め(051～057)

■51:C - 掛け算
ある程度まで揃えてから、
全てに同じ数を掛ける

■52:C - 高橋くんと不思議な道★★★
難しかった。
枝刈りダイクストラ。
O(N^2)だとTLEするので、なにかの工夫が必要
まず特定の頂点に到達するまでにタイプBの辺を最低でも何回使う必要があるかを調べる。
すると、それをneedBとでも置くと
needB[v](needB[v] + 1 )/2 + N 以下にコストが収まることがわかる。
なので実際に使うタイプBの辺の回数は
needB + 150程度もあれば十分だとわかる。(150は√2 * N＋余裕)
以上の情報を持ってダイクストラを行う。

■53:C - 魔法使い高橋君
グループに分けてしてソート

■54:C - 鯛焼き
行列式の偶奇と完全マッチングの偶奇は一致する

■55:C - ABCAC★★★
Z-algorithm

■56:C - 部門分け
状態SからSの部分集合TとS/Tでdp
類題
abc187:F - Close Group
EDPC:U - Grouping

■57:C - 2乗根
//多倍長整数
#include
namespace mp = boost::multiprecision;
using Bint = mp::cpp_int;

＜＜完結＞＞

ARC116

■A - Odd vs Even
愚直にやって一回TLEしました。
奇数なら、約数も全て奇数
偶数のときに４の倍数でないなら、奇数と偶数が半分半分
そうでないなら偶数のほうが多くなる

■B - Products of Min-Max
とりあえずソートします。
minを大きいものから小さいものに下げながら前の状態を保持しておいて計算量を減らす
例
A = {1,2,3,4}
min = 4 -> 4*4
min = 3 -> 3*(3+4)
min = 2 -> 2*(2+3+2*4)
min = 1 -> 1*(1+2+2*(3+2*4))

■C - Multiple Sequences
最後尾のA[N-1]を決め打ちする
A[N-1]を素因数分解すると出来る
例
A[N] = 6 N=3として
2は{1,1,2},{2,2,2},{1,2,2}となるが(3も同様)
これの場合の数は、前計算しておけばいいので求められる
説明適当。

■D - I Wanna Win The Game
形式的べき級数風に考えて、畳み込み
それぞれのbitごとに、何個選ぶかで考えればいい。
普通にdpで良かったみたいですけど

■E - Spread of Information
JOIに同じ問題があるらしい
木＋分割とかで検索すればいいらしい。
二分探索だろうというのはコンテスト中に思いついていたが
貪欲パートがわからず。
各頂点ごとに{置いた都市への最短距離、届いてない都市の最長距離}を返すdfsをする。
マージした結果、"置いた都市への最短距離＋届いてない都市の最長距離"がc以下なら
全て覆うことが出来るので"届いてない都市の最長距離"を-INFで初期化
"届いてない都市の最長距離" = cなら置いて初期化{0,-INF}

ABC197

■A - Rotate
cout << S[1] << S[2] << S[0] << endl;

■B - Visibility
それぞれ４方向に行う。
自分自身を含め忘れるor４回カウントしないように注意

■C - ORXOR
bit全探索
2^30は1e9より大きいためWA

■D - Opposite
回転行列

■E - Traveler
それぞれの色ごとに一番左にいってから一番右までいくかその逆かが最適
最後に原点に戻ることと、無い色の処理に注意

■F - Construct a Palindrome
あと20分あれば。
dp[0][N-1] = 0から初めて、同じ文字の辺が選べるならcost + 2 に 遷移
dp[i][j] = costとして
i == jならans = min(ans,cost)
iとjが直通していたら ans = min(ans,cost + 1)

ARC115

■A - Two Choices
生徒Aと生徒Bの不一致解答の数が偶数個なら
同じ点になる可能性がある。
生徒BとCの不一致の偶奇は
AとBの不一致の偶奇は、AとCの不一致の偶奇からわかる

■B - Plus Matrix
100マス計算的な。
どこかをベースにして、定数を足すイメージ。

■C - ℕ Coloring
エラトステネスの篩風にやっていけばいい。

■D - Odd Degree
非連結部分は、それぞれで考えればいいのはわかる。
グラフの辺を減らして、木にして考える。
木の辺を選択するorしないの問題になる。
考察を進めると、奇数次の頂点数が偶数個なら構築できることがわかる。
木をグラフに戻して考えると、上の考察の延長で不要辺はあろうがなかろうがあまり関係ないことがわかる。
以上より、連結部分ごとに求めて畳み込むと良い。

■E - LEQ and NEQ
座圧＋遅延セグ木で通す。
1700msかかっているので非想定

ABC196

■A - Difference Max
xは大きく、yは小さくしたいので
b-cが答え

■B - Round Down
findとsubstr
nposとか扱いたくなければXの末尾に'.'をつける

■C - Doubled
全部試しても10^6なので全部試す。

■D - Hanjo
dfsすれば良い。
ということが思いつかなかったので。
bit全探索をしてbitがA個立っているものだけ考える。
立っているところに縦置きor横置きすればいいので、さらに2^A分全探索する
制約が小さいので2^(HW+HW/2)で済むので十分に間に合う。

■E - Filters
バグらせまくって間に合わなかった。
解説pdfの情報のもたせ方が思いつかなかったので
F(-INF)とF(INF)の値をとりあえず持ってみる。(Fは合成関数)
これが一致すれば、定数関数。
そうでないときはどこかの区間に傾き1のゾーンがあるはずなので、その区間を二分探索で探す。
三点あれば、グラフの形がわかるのでそこから答えを求める。

■F - Substring 2
難しい。解説見てやっとわかった。
以下メモ。

(1,0),(0,1)のときにコスト1がかかるのでxorを使いたくなる。
求めるのは
min(ΣS[i + j] xor T[j]) iはsの開始位置(0 <= i <= S.size() - T.size())、jはTのどこを見ているか。
これはFFTできそうな気がする(らしい)(は？)

Tをreverseすると
min(ΣS[i + j] xor T[(T.size() - 1 ) - j)]となり
SとTの添字の和が定数(i + T.size() -1)になる。

すると答えは
Ci =ΣS[j] xor T[k] (j + k == i)な配列Cの
T.size() -1 <= i <= S.size() - 1の範囲内のminになる

なので配列Cを求めればいい。
xorのままでは扱えないので、掛け算に分解する。
a xor b = a*(1 - b) + (1 - a) *b なので
FFTを２回すると出来る。

ARC114

■A - Not coprime
50以下の素数はたかだか15個なので
bitDPを行う

■B - Special Subsets
unionfindでサイクルの数を求める
2^c-1

■C - Sequence Scores
dpじゃなかった。
根本的に方針が悪かったので解説AC
N*M^Nから余計なものを省く
一旦tleするループを書いて、整理する
ΣΣΣM^(N-(j-i+1))*(M-k-1)^(j-i-1)
をj-iとkの二重シグマに変形し
ΣΣ(N-i)*M^(N-(i+1))*(M-j-1)^(i-1)

区間dpでもできそうだけど無理なのか？？

■D - Moving Pieces on Line
未読。
読む気にならなかったです。

■E - Paper Cutting 2
Dよりかはとっつきやすそうでしたが。。
dpでやるには状態数が多すぎるので他の方針を考える必要がある。
各操作が選ばれる確率は、それより後にしか来ない(orやらない)は操作がそれより前に来ない確率になるのでそれの総和

参考：Erasing Vertices(agc49)