ABC237 参加記録
コンテスト中AC:A〜E
Eは嘘解法(Cも若干そうでしたが)だったので、ここでは省略します。
C - kasaka
先頭から連続しているaの個数をhead、末尾から連続しているaの個数をtailとします。
先頭に付け加えるのに必要な個数は、tail - headです。この分だけ付け加えて回文かどうかを判定することで答えを得られます。
参加記録を書くにあたって、実装を見直したところ、何故か末尾の方が少なかった場合に、末尾にもaを追加する実装になっていました(嘘解法でした)。ただ、付け加える個数をtail - headのままにしていたのでACとなっていました。
提出コードは、正しい解法で書き直したものです。
提出コード
D - LR insertion
双方向連結リストにより、挿入操作をでできます。
:数列において、の後にある整数
:数列において、の前にある整数
但し、前または後に何もなければ-1とします。
各挿入操作は以下のようになります。
の場合
- iの前はi-1なので、
- i-1の後ろはiとなるので、
- i-1の後ろにあったものがiの後ろとなるので、
- i-1の後ろに整数xがある場合()、xの前はiとなるので、
の場合
- i-1の前はiとなるので、
- iの後ろはi-1となるので、
- i-1の前にあったものがiの前となるので、
- i-1の前に整数xがある場合()、xの後ろはiとなるので、
答えの列は、を辿って先頭まで行き、を辿って末尾まで行くことで、得ることができます。
提出コード