AtCoder Regular Contest 104 感想

はじめてのナンバリングARC

Problem A

X+YとX-YからXとYを復元せよ

考察

• 全探索で行けそうだけど
• 中学時代を思いだす。足し引きするといい感じになるやろ
• 問題にならってX+Y=A, X-Y=Bとすると、
• X=(A+B)/2
• Y=(A-B)/2

Problem B

AGCT文字列の連続な部分列のうち、並び替えて自信に相補的な文字列を構成できるものの数

相補的とは、文字列の対応する文字がA<->T、C<->Gみたいになってること。

考察

• AとTの数が一致、CとGの数が一致してる区間
• 累積和使う
• 始点と終点を全探索して終わり

Problem C

エレベータの乗り降り情報（エラーあり）を見て、一瞬でも同乗した人たちの使った階数がすべて同じになるように復元できるか

コンテスト後AC

考察

• エラー以外を見てその時点でアウトなことがあるので排除
• 人ABCDE乗る->ABCDE降りる、みたいな区間はよい区間
• 1階から最上階までそういう区間だけで構成できればいい
• DP
• ある区間がよい区間かどうか
• パターン1 よい区間同士の和
• パターン2 自分自身よい区間
• パターン2の判定。自分自身よい区間と仮定して矛盾があれば良くない
• 各人のぼる階数は固定される(x階)
• そういう風にできるかを判定
• 乗る人とx階上で降りる人の情報をみる
• 情報が揃っていて一致してないならアウト
• 乗る人のみ分かる場合、その人がおかしな解で降りていたらアウト
• 逆もしかり
• 1Fから最上階まではよい区間ですか？

感想

Bの添え字ミスで大幅なタイムロス。冷え。痛い。あるいはCも手が出る範囲だったのに