AtCoder ARC098 参加記録

復習を兼ねて、参加記録をなるべく書くようにしたいなと思います。

結果は2完・17分台で270位でした。Eとずっと格闘してましたが結局通せませんでした…。パフォーマンスは1861。

f:id:betrue12:20180528205015p:plain

解けたCDと解けなかったEを、1問ずつ振り返ります。解法だけではなく思考の過程を書いていくので少し冗長かもしれませんが、公式解説にない情報をちょっとでも付与できたらと思っているので、参考になる部分があれば幸いです。

C - Attention

似たような過去問をたくさん解いていると直感で 累積和 またはそれに似た解法が思い浮かぶかもしれませんが、少し丁寧に書きます。

誰かがリーダーになったときに、他の人が向きを変えるかどうかは、その2人の位置関係で決まります。

そのため例えば、西から1番目の人がリーダーになろうが、2番目の人がリーダーになろうが、彼らより東にいる他の人達にとってはどうでもいいです。どっちがリーダーになっても、リーダーは自分より西側にいるので。

さらに一般化すると、 リーダーを $i$ 番目の人から $i+1$ 番目の人に変更することは、その2人以外の人にとってはどうでもいい ということが分かります。

そのため、

1番目の人がリーダーになった時の、向きを変える人数を調べる
リーダーを2番目の人に変更する。1番目の人はリーダーでなくなるので、向きを変える必要がある場合は+1。2番目の人はリーダーになるので、さっき向きを変えていた場合は-1。
これを端まで繰り返す。

で、全てのパターンを試せます。累積和というよりは、リーダーを変更した時の差分を見て効率的に計算、という感じですね。

もちろん、「 $i$ 人目より左にいて左を向いている人数」と「 $j$ 人目より右にいて右を向いている人数」を累積和で事前に全部計算しておけば、リーダーを決めた際に向きを変える人数が一発で求められるので、それでも良いです。2つの方法で、やっていることは結局あまり変わりません。

本番中にACしたコードが以下です。

Submission #2562967 - AtCoder Regular Contest 098

D - Xor Sum 2

この問題は以前出題されたXor Sumの続編であり、前作がABC範囲としては非常に難しい問題だったため、タイトルを見てヒィッと思いました。ただ前作よりも難易度は低く、前作の知識も使えたのでイメージほど苦戦はしませんでした。

具体的には、(xorでの総和) $\le$ (+での総和) という知識が役に立ちました。これは、「xorは+の繰り上がりを無視したものと同じ」と思うと理解しやすいと思います。そして、繰り上がりが1度でもあると両者の値は一致しなくなります。

そこから、「 値が一致しない状態からさらに範囲を広げてもダメ 」という発想に至り、しゃくとり法にたどり着きました。本番中のACコードは以下です。

Submission #2564362 - AtCoder Regular Contest 098

ところでこの「値が一致」判定、私は単純にxorと+を独立に計算して == で比較していました。この方法の他に、「繰り上がりが起こるのは両方のビットが1のとき」という性質から & を使って判定しているコードもありました。比較していませんが、多分 & のほうが速いんじゃないかと思います。

あとは地味な補足ですが、しゃくとり法って「右端を進めて区間に入れる」処理と「左端を進めて区間から除く」処理が必要なんですよね。だいたいこれらは逆演算になるので、今回は「xorの逆演算って何？」って知識が必要です（答えはxorです）。基礎知識だと言う人も多そうですが、初めて考える人には思い付きづらいかもしれません。あると便利な知識です。

しゃくとり法についての解説は是非こちらをお読みください！素晴らしい記事です。

しゃくとり法 (尺取り法) の解説と、それを用いる問題のまとめ

E - Range Minimum Queries

本番中に通せなかった問題。タイトルに釣られてRMQのセグメント木使えないかなとか考えましたが（単純）、最初の取っ掛かりとして 小さい方から見て1番目と $Q$ 番目の差は必ず解の候補になる というところから考えました。一番小さいものから順に取っていくことは、数列の配置によらずできるからです。