ARC119

■A - 119 × 2^23 + 1
bは高々60なので全探索
bを固定したときのa,cの値は
aを1減らすとcが2^b増えるのでaを最大にしたい。

■B - Electric Board
明らかに0の数が不一致ならNG
可能なときは左から揃えていけばいいので
sのi番目の0とtのi番目の0の位置が不一致な場所の数を数える。

■C - ARC Wrecker 2
区間の偶数番目の和と奇数番目の和が一致すれば良い。
a-b+c-d+e....のようにする。

■D - Grid Repainting 3
二部グラフに読み替えるところと、木と森の考えはほとんどできていたのですが
公式解説でいうタイプAとタイプBののどちらかに寄せるという部分が詰めきれないなかった。
これができれば橙パフォだったので悔しい。

■E - Pancakes
こっちのほうが正解者か多いのだからこっちをコンテスト中に読むべき。
それすらしてないのは怠慢です。

変わるところのみ取り出して、どのような関係性が保たれていれば見栄えが良くなるかを考える。
すると全部で24パターン考えると
a<b かつ c<dなところを差し替えるか
a>b かつc>dなところを差し替えればいいとわかる
ただし端が絡む場合は別処理。
区間の共通部分の倍だけ減ることも考察をすすめるとわかるので
最長共通区間を求めれば良い。
最長共通区間は、ソートして最右を更新しつつ保持しておけば良い。

 

ABC201

■A - Tiny Arithmetic Sequence
std::sort

■B - Do you know the second highest mountain?
std::sort

■C - Secret Number
0000から9999まで全部試す。

■D - Game in Momotetsu World
ゲームの最適戦略苦手。
dp[i][j]:=(i,j)から始めてお互いが最適に行動したときの
始めた人からみた最大得点差

■E - Xor Distances
終了15分前に完全に方針が間違っていたことに気がつく。
そこから頑張って2分前AC
(x,y)の最短パスのxorは
(0,x)と(0,y)それぞれ最短パスのxorに等しい
理由は共通部分((0,lca(x,y)))が打ち消されるから
なので、すべての点に対して原点からのxorを求め、
各bit毎にこのbitが立つための条件を考える。

■F - Insertion Sort
セグ木dp
それぞれの人間は高々一回しか動かさない。
動かない人達の集合を決め打つ。
動かない人たちは、初期状態で既に最終状態と前後関係が一致している必要がある。
dp[i]:=Sに含まれる人の番号の最大値がiで、i以下の人を照準に並び替えるのに必要なコスト。
とすると
dp[i] = min(dp[j] + Σ(n=j + 1,i - 1)A[n] )
当然だが、iが最初の動かさない人のケースも考慮する必要がある

dpをセグ木にそのまま乗せずにdp-ΣA[n]として乗せる必要がある。

ABC-F略解(146-150)

■146F - Sugoroku
単純にdpをするとO(NM)かかる
貰うdpで考えると結局欲しいのは区間minなので
セグ木におまかせする。


■147F - Sum Difference
選ぶ個数に着目する。
数列が(4,6,8,10)だったとすると

2個選ぶ場合:10,12,14,16,18
3個選ぶ場合:18,20,22,24
という感じで小さい方からi個数選んだ場合から大きい方からi個選んだ場合
の間を交差Dでまんべんなく選択できる。
mod Dで考えれば場合分けそうな気がする。

上の例だと
2個は0+2*5から0+2*9を
3個は0+2*9から0+2*12なので
[5,9],[9,12]のような形管理しておき
最終的にmodごとで[5,12]のような形にマージすると答えが出る
マージ部分は座圧imos法っぽくすれば良い。

dが負のケースがあるので単調増加にならないことに注意。
d = 0もコーナーケース。

■148F - Playing Tag on Tree
dfsを2回する。
注意する点は、捕まる場所は葉ではなく、葉の親になること。

■149F - Surrounded Nodes
各点を独立に考える。
?-0-?
見たくなっていたとして
穴あきにならないのは全ての?上の頂点がすべて白

どれか一つの?には黒があるが、それ以外の?には白しかない時。
なのでdfsすれば良い。

■150F - Xor Shift
xorで書いているからややこしくなるのであって
ただの数列に+xして一致するかのように考えればよい
1,2,5を
11,7,8をシフトと+xをして一致できるかはかは差を見れば良い
というわけaとbの階差数列を用意しそれらがスライドしたら一致するかを考えれば良いので
bを2周分持つようにし、KMPを使う。

ARC118

■A - Tax Included Price
100円周期。

■B - Village of M People
二分探索

b/m-a/n <=xは扱いにくいので

任意のiに対して|bn-am|<=x/(n*m)となる最小のxを求める。
bは負にならないことに注意。
構築は一旦全て最小で作って、余った分を適当に振り分けるイメージ

■C - Coprime Set
最大ケースを見ると1/4を含む必要がある。
2,3,5をベースに考え
素因数に上記の3つの素数のうち2つ以上を含む整数を小さい方から列挙するといい
6,10,12,15,18,20.....
しかしこれだとn = 3の時にgcdが2になるので細工をする。

■D - Hamiltonian Cycle
群論
サンプル1で考えると
1,4,3,12,9,10,1
5,7,2,8,6,11,5
12,9,10,1,4,3,12
8,6,11,5,7,2,8
1,4,3,12,9,10,1
となる(右移動が*4、左移動が*5に対応している)
上の図でいうところの
2*6の区間と4*3の区間
最後に1に戻るようにひと筆書きすれば良い事がわかるので
構築をする。

ABC200

■A - Century
(n+100-1)/100

■B - 200th ABC-200
long longに収まることを確認して
問題に書かれているとおりにやる

■C - Ringo's Favorite Numbers 2
mod200で分類しておき
Σx(x-1)/2

■D - Happy Birthday! 2
実装重たくない?と思って答えを見たら鳩の巣原理。。天才!
Cと同様にmod200で分類しておく
同じmodの物があればそれが答えなので別処理しておく。

すると、
{1,2,5,7,11}みたいな集合から適当に2グループ作ってmod200で和の等しいグループが作れるか?
という問題になる
前から
dp[i][j] := i番目まで見た、mod200でjな数が作れるかどうか
を言う感じでdpをする。
しかし、これだと復元パートが面倒なので
vector dp[i][j] とでもしておいて使ったものを保持しておく

■E - Patisserie ABC 2
i + j + kで順番に見ていく
i + j + kを固定したときの場合の数は
更にiを固定をすればj + kが固定されるため
必要なのはj + kの区間和で、前のi + j + kの結果に足し引きすれば尺取法と同じ容量なので合計でO(3*N)で求まる
これで答えを満たすときのi+j+kが特定できたので
同じ要領でiを特定し、jとkも特定すれば良い。

■F - Minflip Summation
解説放送のやり方が天才。
01011110のような文字列をフリップして全て同じにするためにかかる回数は
円環にして01と10の回数を足し2で割った物になる。

K個連結しているがabcabcみたいなものは円環にして考えるのなら
abcを考え倍にすればいいので行列で頑張る必要がない。

ABC199.5

■A - UFO襲来
全て探す

■B - 友好の印
UFOをビルを結んだ傾きが一番緩やかなものが答え。
地中からは見えないことに注意

■C - MAD TEAM
二分探索

■D - 宇宙人からのメッセージ
反転はフラグで管理する
dequeで管理しつつ、最後にやる処理は途中にやっても問題ないので
途中にする。

■E - 潜入
愚直でも通るらしい。(は?)
それぞれの頂点にサブ頂点を用意しておき
下がるときは、サブ頂点にコスト1で移動してから
下マスのサブ頂点にコスト1で移動する。
サブ頂点から、メイン頂点にはコスト0で戻れるようにする。

■F - 出会いと別れ
線形代数
頂点0から頂点xに移動できるかどうかは
0 xor bi xor bj xor bk.... = xとできればいい。
任意のxをb0,b1.....の部分集合のxorで作成するためには
bのrankがnになれば良い。
構築はここまでの処理で基底として採用するbを使って
非連結なら結んでいけば良い。
n*2^nをすべて試してもたかが知れているので問題なし。

ABC-F略解(141-145)

■141:F - Xor Sum 3
これ、難しくないですか?
xorなので、当然bitごとに考える。
入力例2をもとに考える
23:0010111
36:0100100
66:1000010
65:1000001
である。
32,16のような奇数本bitが立っているものは
どう振り分けようが、答えもbitが立つので考える必要がない
なので、入力を以下のように変形する
07:0000111
04:0000100
66:1000010
65:1000001
この残っている要素を、xorができるだけ大きくなるように分割したい
{4,7,65,66}の集合のxorで作ることのできる要素は
これを行基本変形した
{0,3,4,65}の集合のxorで作れる要素と等しい。
のでここから最大なものを求め、最初に弾いた奇数本bitが立っているものを加える。

この例だと48 + 70 + 70 で188


■142:F - Pure
最小のサイクルを求めればよい
サイクルの中に余計な辺があれば、その辺を採用して更に小さいサイクルが作れるので

■143:F - Distinct Numbers
二分探索
K=kのときにi回取れるかを考える
1 1 1 2 2 2 2 2 3 3 3 3 4 4 4を
3個セットで5回取れるかは
1 1 1 2 2
2 2 2 3 3
3 3 4 4 4
とすればよく
3個セットで4回取れるかは
1 1 1 2
2 2 2 3
3 3 3 4
と取ればいい

■144:F - Fork in the Road
特定の通路がないものとしてゴールまでの期待値を求めるのにはO(M)かかる
辺ごとにやるとO(M^2)かかるのでTLEしてしまう。
頂点ごとに考え、ここから生えている辺をどれか取り除くならどれがいいかを考えるのは
そこから一番遠回りになるものを取り除けばいいので
頂点ごとに考えるとO(NM)

■145:F - Laminate
dp[i][j][k]:=i番目まで見た、最後尾の高さがh[j]、k個取り除いた