人生のやることが多すぎる
コンテスト
パ研合宿2024 第3日「Teamwork」
Rho17, shinchan, harurun4635 チーム 魔法つかいプリキュア！！～MIRAI DAYS～
shinchan「自分キュアミラクルやれます！」らしい そしたら自分キュアマジカルとキュアフェリーチェどっちにしよう......
BCHIKMN 700点 7位
B: 「x番目の要素を採用する/しない」でDPを頑張る CHIK: haru M: shin N: shin「二部グラフだと答え2で奇閉路だと答えが3」Rho「彩色数では？」→彩色数をLuzhiled memo から強盗して投げるとAC
ARC196
ox-- 345位 Perf 1946 2077->2064 (-13)
Aはどこかで見覚えのあるような感じだったのでやることはすぐに分かった。上半分の値を求めるやつをsetで書こうとして相当手間取ったの最悪!
Bはよく分からなかったので実験を回したが結局よく分からなかった。こういうのちゃんと理詰めしないとダメそう？
-> upsolved 一番左を決めるとその行の自由度が減る。具体的には、各マスの左右の接続がすべて決まる。同様にやると上下の接続も決まり、Aについてはこれですべて条件が確定する。Bについての条件が未確定なので、Bのあるマスと同じ行と同じ列について追加の条件が要請される。
ABC401
ooooo-- 950位 Perf 1611相当
D: 条件がむずかしい oの隣はすべて.にしてよい。残ったoが0個ならば全部.で埋めてよい。（これを忘れて1ペナ）残った?の区間に詰めるだけ詰め込んだ時残ったoを全部ちょうど使うならば、長さが奇数の?からなる区間は確定する。偶数の場合は確定しない。
E: よく読むと、辺(u,v)があったときvの昇順に追加していけばよさそう。
F:
実は本質が過去に出ている。それぞれの頂点から最も遠い点を出せばよいが、全方位木DPっぽいことをしようとして迷宮入りし時間切れ...... 木の直径の性質を用いると、直径の端点2つをとってきてそれらとの距離のmaxを取ればよかった。悲しいね......
Todo: 全方位木DP
G: 読んでない→読んだ ただの二部マッチングでは？→二部マッチングで終わりですね 死ぬほど簡単だった......
その他
Trieの実装を履修した。昔JOIの何かで書いた気がするが昔過ぎて覚えていない。
過去問
ネタバレ注意
ARC125-D (Diff 2187)
$dp[i] = $最後が $A_{i}$ であるような部分列 としてDPを行う。以前現れたのと同じ文字が出てきたら以前の部分のdp配列を0にして、あとはセグ木上で区間加算とか管理しながらやる
ARC130-D (Diff 2437)
元の条件は木の頂点を白黒で2彩色すると「隣接する頂点について、白より黒に書かれている数の方が大きい」という条件を満たすように順列を書き込む通り数は？という問題になる。白と黒を反転させたバージョンの問題とも答えが等しいので、片方だけ考えることにする。（x->N-xとすれば一致）
$dp[v][j]$ を、頂点 $v$ とその子を条件に合うように並べたとき、頂点 $v$ に書かれた数が $j$ 番目に小さいような通り数として定める。（順列→挿入DPの要領）親 $u$ が $k$ 番目に小さくなるような通り数 $dp[u][k]$ を考えるとき、 $u$ より小さい要素を合計 $k-1$ 個子の列たちから取ってきて並べる、ということを考え式に表すと畳み込みの形になっている。よって、 階乗の係数をかけたり累積和を取ったりした後$dp[v]$ を多項式だと思って適切に掛け合わせればよい。
これが600点しかもらえてないのよくわからない
ARC152-C (Diff 2081)
最小値と最大値の差は一定→最小値をできるだけ小さくしてあげればよい
各要素を選んだ時の最小値の移動距離は求められる。実はそれらのgcdを取ればその倍数全部作れる？→AC
確かに(max-min)を使って右に寄せた後適当に操作して(max-min)で左に戻せば良さそう
ARC152-D (Diff 2381)
偶数は絶対無理
$N$ と $K$ の最大公約数を $G$ として、 $G \times N/G$ のグリッドをお絵描きして全域木を作ろうとすると、作れる
