http://agc012.contest.atcoder.jp/tasks/agc012_c 解法 空の列も良い文字列だとみなす。順列 A, B があって、AとBを連結したもの(A+Bと表す)のパターン数が X だったとする。 A←A+[foo], B←B+[foo] とすると A+B のパターン数は 2X になる。 A←A+[foo], B←[…

http://agc012.contest.atcoder.jp/tasks/agc012_b 解法 di が小さいのが鍵に見える。dp[v][i] を「頂点 v から距離 i の範囲を dp[v][i] で塗りつぶせ」と考えると上手くいく。命令を小さい距離へどんどん伝搬していくイメージ。 補足 ある頂点から距離 d …

http://agc012.contest.atcoder.jp/tasks/agc012_a 解法 入力を昇順にソートして考える。適当な戦略を取ってみる。先頭から3つずつペアにしていくのはどうだろう。 _o__o__o__o_ 000111222333oになっているのが中央値。これは改善ができる。 _o__o___o_o_ 00…