煮え切らねぇ
メモ
AB
はい
C
ソート
D
コンビネーションの計算できますか？僕はできました。ちゃんとライブラリ置いた方がよい？
E
頂点を3倍してBFSするとよい。すなわち「i 歩目 (i=0,1,2) で頂点 v に着く」という状態を頂点 (v, i) とするとよい。元のグラフで u → v とすると、辺は (u, i) → (v, (i+1)%3) を引けばよく、O(N+M) でできる。典型だけど、すぐ分かってよかったね。
F
DPなんですが、愚直にやると dp[k][i] を「長さ k でラストが i の列の個数」とするとよさそう、しかし状態数が O(NK) で N が大きいのでできない。観察すると、同じ値のものがたくさんある。具体的には s=sqrt(N) を境に状況が変わるので、まとめられる部分はまとめて計算するとよい。遷移も累積和にすれば O(1) でできるので、O(K sqrt(N)) でできる。
まあ実装できなかったんですがね、悲しいね...
反省
DPするときは、初期値と遷移をちゃんと書き出してから実装しようね！
結果
181位、pf 2080くらい、rateが1800になりました。F できなかったんで内容的には煮え切らないけど、結果には満足しておこう。
