CodeFestival2015本選の問題（解法メモ）

備忘録に解法に至るアプローチを貼っておきます。

A: 575判定。cin >> s >> t >> u; cout << (s.length()==5&&t.length()==5&&u.length()==5) ? "YES":"NO" << endl;

B: N≧2における合計値の確率分布では平均が一番盛り上がっている。N=1では均一なので1が答え。

C: 前から文字列を見ていき、"01"か"10"が見つかったら即座にペアにしていって良い。（010…とあったとき、0「10」…としても「01」0としても前3文字までの分解数は同じ＆0「10」とすると残った0とペアになる1が絶対なくなるが「01」0とすれば残った0とペアになる1があるかもしれない -> そのときは得！）などと考えたが、詳しい証明は分からない。

同じ文字を複数のペアに割り振らないように注意する。

①いつだれがどのスイッチを押すかと考えると闇 -> 人数だけ求めればよい！

②N点取る場合…区間が最大M個かぶっていたらM人以上必要、また、M人で十分。

③N-1点取る is 全区間 - {ある一つの区間}

④(ある区間にXを足す, 区間のMaxを求める)というクエリが沢山来る -> StarrySky木

もしくは、N点取る場合に区間が最大M個かぶっているとき、答えがMかM-1であることを利用すればO(N)。(M個区間が被っている時間の(左端, 右端)を覆えるかどうかで判定できる）

答えはそんなに長くならない -> 反復深化で全探索しよう！判定は色んな入力を元のコード, 生成したコードの2つに与えて、出力の一致を確かめるなど…。

①サイクルにする（グラフ問題にする）

②頂点と辺の通る回数に注目する

③辺を通る回数を考える

④連結判定

・列の問題に落とせるらしい？？

・3枚重ねるのはタブー

・重なって損した量（ペナルティー）で辺を貼ると、最短経路問題になるらしい