問題概要 長さN(区間で両端の値が等しくなるような部分列がいくつとれるか求める問題。ただし端点しか交わってはならない。 考えたこと サンプルが分からない。 ああ端点は交わっていいのか。納得。 貪欲で行けそう。区間スケジューリングみたいな感じで。 …

問題概要 二人用のゲームがある。1*N( 考えたこと 二つの問題を解かなければならないのか。 どちらもプレイヤーの間隔を状態にしてDPっぽく解くんだろう、きっと。 前者の問題について考えてみると、勝つ確率はΣ(1.0 - dp[cur-i])の計算ができれば行ける。 …

問題概要 ノード数V( 考えたこと どこかで、というかCodeForcesで似た問題を解いた記憶がある。 普通のEuler tourだと2*V-2が総経路長になるが、戻ってくる必要がないのでdist(start, goal)の分だけ差っ引くことができる。 なのでstart, goalを最大化してや…

問題概要 長さL( 考えたこと とりあえずuniqueしても良さそうなのでuniqueして考える。 要するに最長回文？ 本当に最長回文だった。Manacherで通した。

問題概要 長さL( 考えたこと 桁数と直前の値を状態としてDP? いやいや、値が小さいんだから全探索で行ける。comb(20, 9)も大した大きさではないし間に合うはず。 分割を全部試した後は単純な組み合わせの問題に落ちるはず。 最初はTLEしてもいいからmap使っ…

結果。 どれも適度に難しかった。 とりあえずGがBITとかRMQとか使えば解けそうだったので飛び込んだら答えが合わない。小さいケースに関しては解が出せるので小さいところを出力して眺めていたら嘘仮定が思いついたのでその仮定の元で解いたらACが貰えた。実…