WUPCに引き続き書いていきます。メンバーは前回と一緒の3人です。
考察：つちのこ
実装：つちのこ
つちのこが1人でパッと通す。
考察：zkou
実装：zkou
zkou担当。TLが大丈夫そうなこともあり普通にPythonで書いて、普通に通してた。
考察：つちのこ、クマー
実装：つちのこ
Cの方針が立ったものの慣れないTrieの書き方でグダるとまずいので、先に簡単なこちらをつちのこと2人で処理。うっかりもいろいろあったが結局はつちのこがノーペナで通してくれた。
考察：つちのこ、zkou
実装：つちのこ
私が書いていたC問題がなぜかREして焦っていた中で見た問題。落ち着いてみれば二部グラフの最小点被覆。グーグル先生曰く二部グラフの最大マッチングと一致するらしい。へえ。ネタがおおよそ分かってからはつちのこがあっという間に書き上げて通した。
考察：クマー、zkou
実装：クマー
制約によりhokudaiの出力は必要なく、また少し考えれば先頭20文字だけ考えればよいことが分かる。よってpow(2,20)通りの全探索で終わり。
…のはずだったのだが、ここが本日で一番のやらかしだった。真っ先に思いついた実装方針は
・与えられた文字列をTrieに全て入れる
・接頭辞が一致する文字列ができるだけ少なくなるように接頭辞のmin(20,n)文字を決定していく
というもの。サンプルが合い、提出すると謎のRE。どこを探してもバグが見当たらず不可解だった。Trieライブラリがバグっている可能性を考慮して
・与えられた文字列Sの接頭辞min(n,20)文字を2進数符号とみなして、その値をsetにそれぞれ格納する
・setに入っていない0 <= i < (1 << (min(n,20)) ) を満たす i を2進数に直して、あとは'*'を付ける
という方針に切り替えてなんとか5ペナAC。チームに安堵の空気が流れる。これがこの日の自分の初仕事だった。何やってんだか…。
ところで、Trie解のコードのREの原因がまだ分かってない。他の問題でTrieを使ってみたところバグってなかったが、うーん…？
考察：全員
実装：クマー
君こういうの得意そうだよね、と言われて見たら確かに解けそうな見た目をしていた。「数え上げは同じものを何回ずつ使うかを考える」というセオリー通りに、それぞれの辺が答えに何回影響するかを考える。対称性があるので、答えは (定数 * ∑a_i + 定数 * ∑b_i)の形になるっぽい。
しかしpathをどのように取れるかが良く分かっていない。頂点0を通る辺を何回使用するかで場合分けして、1回目の移動で行く位置を固定すると、結局「1つ以上のボールを配らないといけない重複組み合わせ」2つに帰着されることが分かる。「1つ以上のボールを配らないといけない」部分を忘れたせいでしばらくバグらせたが、結局ノーペナでACしてチームは12位に。この瞬間は盛り上がった。
考察：つちのこ、zkou（、クマー）
「なんかこれyosupo judgeで見たことある」と思ってyosupo judgeの提出欄を見てみたらSegment Tree Beatという怪しいデータ構造が。ググったりして仕様を確認している間に空しく時間は過ぎていった。こんな趣味全回のデータ構造問出すなよと思ったら平方分割だそーな。ええ…。
考察：つちのこ、クマー
設定が複雑すぎて、こんなんどうせMinCostFlowだろ！と喋ってはいたが、チームの誰一人として最小費用流の実装をしたことがなく、断念…。
F通せて14位なので結構満足です。ちゃっかりjoeさんチームやけんちょんさんチームに勝っちゃいました。Cで大量にタイムロスしなければ…とか思ってもしょうがないですね。明日はつちのこがいないので、zkouと2人で頑張るぞ。
