AB2完灰コーダー
言われてみれば確かにそうだな、みたいなことで考えが凝り固まっていていつもC問題が解けません。皆さんは先に行っててください。私はもう……いえ、後で必ず追い付きますので。
公式解説の言い換え
要点は3つ。
- ‘A’だけに注目し、それを並び替えれば自動的に’B’も求まるので’A’をどうするかだけ考えればよい。
- 文字列Sの最終形は”AB”か”BA”が続く並びしかない。
- 隣り合った文字を並び替える操作も’A’だけに注目すれば、’A’を一つずつ動かすことと言い換えることができ、そのコストは’A’のindexを+1するか-1することになる。
であれば、’A’を特定の位置に動かすコストを奇数及び偶数番目の2通りの場合で考えて、その最小値が答えですね、という感じ。
特に探索する必要はない問題なので、人によっては簡単に350点を取れたかもしれませんね。私はできませんでした。（半ギレ）
※制約上、2Nは最大100万となり、文字列Sの如何によっては答えが231を超える可能性があるので注意。
終わり
公式解説もよく読んで数学仕草に慣れといたほうがいいなと思いました。
どことどこが対応する書き方をしてるのかが分かってないと、問題文を理解するだけで時間が過ぎていく……。D問題とか夢のまた夢だよぉ
あと最初に思い付いた解法が間違ってるとパニックに陥りがちなのを直したい。
コメント