昨日なんか作業をしていたら寝るに寝れず、5時くらいまで起きていた。起きて気が付いたら昼すぎだった。
ABC329に出た。久しぶりに黄perfが出たが、本当に早押しクイズみたいな内容だったので薄氷の高perfという感触が拭えない。
A: やるだけ
B: setに入れると手っ取り早い
C: 各アルファベットについて連続する最大数を求めて総和をとる
D: (投票数, -番号)をmaxのセグ木に記録してみたが、なんか別解がありそうな気もする
E: 例えばS=AAABCCC, T=ABCという場合を考える。SからABCをとるとS=AA###CCとなり、#の部分は元々どうであっても良かったということになる。どうであってもよいのでその前の段階でBC#とかであっても良かったことになるのでS=A####CCにできる。こういうことを繰り返すと良さそうだと考えられる。
このように考えると、Tと一致させられる部分を探し、#で置き換えては隣り合うまだ#でない部分を探索候補地に入れる、ということを繰り返すとよさそうだと考えられる。実装はだるいがこれで実際解ける。
F: データ構造をマージする一般的なテク
G: 解けず。オイラーツアーに制約を持たせてその制約を満たすオイラーツアーのパターン数を調べろという問題。2分木のどちらへ先に行くかということになるので制約がなければ2^(2分岐する頂点の数)というパターン数になるが、2頂点間に順序制約があるとそのLCAでどちらへ先に行くかが決まってしまうので、2^(2分岐かつ自由に順序を選べる頂点の数)ということになる。ここまではできた。
あとはかごに入る数Kを考慮する必要があるが、これが何も思いつかず。制約からしてDPのような気はする。ノードと
Mac Miniを買ったのに全く使っていないので、とりあえずXCodeを入れている。
Windows文化出身なのでXCodeとかいうのがよく分からないというのが買った大きな理由の一つだったことを思い出した。
気が遠くなるほど時間がかかっている。
Categories: 未分類