ARMERIA

放置していたけど更新再開、Rubyと競技プログラミングの話が中心になっていく予定です

AtCoder ARC098 参加記録

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

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

f:id:betrue12:20180528205015p:plain

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

C - Attention

C - Attention

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

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

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

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

そのため、

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

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

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

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

Submission #2562967 - AtCoder Regular Contest 098

D - Xor Sum 2

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

E - Range Minimum Queries

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

では、2番目と Q+1 番目の差は解の候補になるか?と考えたときに、必ずしもそうでないことが分かります。最小の値を2番目にしようと思うと、1番目の値を「避けて」区間を選び続けなければなりません。そうなると、孤立して選べない数が出てきます。

一般化すると、 i 番目を最小にしたいならば、i-1 番目までの数を全て避けて区間を選び続けなければならない ということになります。最小値を固定すると考えやすくなり、制約もまあまあ小さめなので、最小値を固定して全部試そうと思い至ります。

「避けなければいけない値」で数列は分割され、それらをまたがるように範囲を選ぶことはできません。部分列それぞれからいくつ値を取れるかは、例としては以下のようになります。式で書くと (部分列長)-K+1 個(負になるときは取れない)です。

f:id:betrue12:20180528235029j:plain

ここまでは想定解法と同じです。…で、ここで私が始めたのは最大値の二分探索です。

Submission #2569443 - AtCoder Regular Contest 098

確かに最大値に単調性はある。計算の答えは(きっと)正しい。計算オーダーも O(N^{2}\log N) でいける…と思いましたが、さすがに無駄が多すぎましたね。

というわけで、コンテスト後に想定解法である「分割された列をソートして小さいほうから取れるだけ取る」方法を実装しました。

最初は分割された列たちをどう管理するのかイメージが付きませんでしたが、実装のやり方として2通り思い付き、それぞれ書いてみました。

まずは、実際には列を分割「しない」方法です。分断箇所をフラグで管理しておき、数列を普通に最初から見ていきます。分断箇所に当たった時点で、そこまでの部分列を処理します。最後に「番兵」を置かないとバグります。

Submission #2573110 - AtCoder Regular Contest 098

次に、実際に列を分割「する」方法です。列を1つずつ見ていって、分割箇所を探してそこで列を分けます。たくさんの列の中から分割箇所を見つけるのは一見大変そうですが、見る要素の数は合計で結局 N 個なので大丈夫です。ただRubyの場合は配列の破壊的操作を上手く使わないと結局遅くなりそうです。

Submission #2573193 - AtCoder Regular Contest 098

さいごに

以上3問、私なりの思考と実装方針をまとめてみました。

CD速解きができたのでパフォーマンスは良かったですが、逆にたっぷり時間をかけてEが通らなかったのは悔しいですね。しばらくは「ARC/AGCで3完する」が毎回の目標になりそうです。