ARMERIA

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

codeFlyer予選 参加記録

codeFlyer (bitFlyer Programming Contest) - AtCoder

初めて参加した企業コンテスト。結果は30分台3完で159位でした。

f:id:betrue12:20180603102618p:plain

企業コンテストは変わった問題が出たり配点基準がいつもと違ったり…という話を聞いていましたが、今回は普通だったと思います。ABC/ARCでも出そうな問題。

解けたA~Cと、解こうとして解けなかったDを振り返っていきます。

A - 本選参加者数

A - 本選参加者数

 A 人以下でかつ  B 人の倍数となる最大の人数を求める問題。

  •  A 人から  B 人で割った余り(あぶれる人)を切り捨てる と考えると、 A - A%B
  •  A 人から  B 人の組がいくつできるかを求めて  B 倍する と考えると、 A/B * B

など何通りか書き方がありますが、最初に思い付いたものを素直に書いてしまえばいいと思います。(サンプルはもちろん通しましょう)

ACコード:Submission #2596471 - codeFlyer (bitFlyer Programming Contest)

B - 洋菓子店

B - 洋菓子店

問題文をよく読んで、その通りの動きをコードにすると解けます。解説書くのが難しいですね…

ACコード:Submission #2597462 - codeFlyer (bitFlyer Programming Contest)

C - 徒歩圏内

この問題からちょっと詳しく振り返ってみたいと思います。

C - 徒歩圏内

数直線上に点がたくさんあるので、以下のような位置関係になっている3点のトリオを数え上げてください、という問題。数式で書くと  i \lt j \lt k かつ  X_{k} - X_{j} \le D, X_{j} - X_{i} \le D, X_{k} - X_{i} \gt D をすべて満たすものです。

f:id:betrue12:20180603110024j:plain

愚直解は3点のトリオを全て調べる  O(N^{3}) です。当然間に合いません。

各点は数直線上に座標順に並んでいるので、 「距離が  D 以下であるか」には単調性があります 。二分探索やしゃくとり法が使えそうです。全ての点それぞれに対して「右側にある距離  D 以下の点の数」を求めることは、しゃくとり法を使うと  O(N) でできます。もちろん左側も同様です。

f:id:betrue12:20180603113609j:plain

そのため、例えば3点のうち左側の2点を固定してしまえば、前計算したしゃくとりの結果を使って条件を満たす右側の1点の範囲がすぐに計算できます。これで  O(N^{2}) に落ちますが…入力サイズが  N \le 10^{5} なのでそれでも間に合いません。まだ落とす必要があります。

元の条件をそのまま考えて  O(N^{2}) 未満に落とすのはかなり難しそうだと思い、「 いくつかの場合分けに分割して、足し算する 」や「 少し広い条件を考えて、余計なぶんを引く 」のような、条件の変形ができないか考えてみます。

ここで 3点の組を数え上げるときに、真ん中を固定すると楽 ということを思い出します。この考え方は、以下の問題からの類推でした。

C - Snuke Festival

真ん中を固定すると、左右それぞれにある「距離  D 以下の点の数」は前計算したしゃくとりの結果を使えます。それらを掛け算すると、真ん中を  J に固定したときの  X_{k} - X_{J} \le D, X_{J} - X_{i} \le D を満たすトリオの数になります。全ての「真ん中の点」についてこれを足し算すれば、「答えに近いもの」が求まります。これがそのまま答えにならない理由は、もう1つの条件である  X_{k} - X_{i} \gt D が考慮できてないからです。

というわけで、上記のうち  X_{k} - X_{i} \gt D を満たさないもの、つまり3点全てが距離  D に含まれているものを数えて引き算します。これは、左端を固定した時に「右側にある距離  D 以内の点」から2個を選べばよくて、これもしゃくとりの前計算が使えます。

これで答えが計算できます。振り返ってみると、いくつかのテクニックの組み合わせが要求される問題だったなと思います。ABC/ARC-D 400点でも、このくらいは出そうですね。

  • 1次元上の点がソートされている時、距離には単調性があるので、しゃくとり法を使う(二分探索でも可です)
  • 数え上げの条件が扱いにくい場合、少し広い条件を考えて、余計なぶんを引く(これの発展が「包除」ですね)
  • 3点のトリオを、真ん中を固定して数え上げる

ACコード:Submission #2599368 - codeFlyer (bitFlyer Programming Contest)

※余談ですが、(現時点での)公式解説の書き出しにミスがあるのでご注意ください。公式解説の書き方を真似つつ修正するなら、以下が正しいと思います。

  1.  i \lt j \lt k かつ  X_{k} - X_{i} \le D を満たす  (i, j, k) の個数  A
  2.  i \lt j \lt k かつ  X_{j} - X_{i} \le D, X_{k} - X_{j} \le D を満たす  (i, j, k) の個数  B

答え: B - A

D - ハンコ

D - ハンコ

数え上げの問題。公式解説とは少しだけ違った解き方をしています。

最大サイズだと紙には  HW = 10^{18} 個のマスがあるため、1個ずつ数えていては間に合いません。何とかして、まとめて数える必要があります。

ハンコの中のあるマスが黒であるとき、その黒マスによって塗られる領域は以下のようになります。四隅の赤がハンコのサイズです。

f:id:betrue12:20180606201143p:plain

例えば、真ん中あたりの領域は1つ黒があっただけで全部塗られてしまいます。これはまとめられそうです。

上下左右の領域(赤いところを除く)もまとめられそうです。例えば左側の領域を考えると、ハンコを紙左端に沿って上下に動かしたときに「ハンコの中で一番左にある黒マス」が縦線を引きます。そこから右側は全て塗られます。上下左右、それぞれ同様です。

ということで、紙の領域を以下のように分けて考えます。

f:id:betrue12:20180606202240p:plain

  • A領域:四隅でハンコがあまり届かない場所なので、ちょっと数えにくい。
  • B領域:左端と右端。それぞれ、ハンコのうち最も左にある黒マスと、最も右にある黒マスを考えればいい。それよりも内側のマスは全部塗られる。
  • C領域:上端と下端。B領域と同じ考え方ができる。
  • D領域:真ん中。ハンコに1つでも黒マスがあれば全て塗られる。

上図は、  H, W がともに十分大きい時の分け方です。例えば W 2M 以下の場合は、下図のようにC領域とD領域は潰れます。

f:id:betrue12:20180606202535p:plain

 H, W がともに小さいと、B領域も潰れてA領域だけになります。このあたりは場合分けが必要です。

さて最後に残ったA領域ですが、最大サイズは  2N \times 2M = 4 \times 10^{6} です。できれば  O(NM) 以下で計算したいところです。

領域内のマスが最終的に黒マスになる条件は、ハンコの黒マスが作る長方形のうちいずれか1つ以上に含まれていることです。

f:id:betrue12:20180606203911p:plain

このように長方形がたくさんあって、各座標点が長方形に属しているかどうかや、その個数などを求めたい。そんな時に役立つのが「いもす法」です。

https://imoz.jp/algorithms/imos_method.html

上記のページで丁寧に解説されていますが、二次元の理解はなかなか難しいんじゃないかと思います。自分なりの理解を表した図を描いてみました。

f:id:betrue12:20180606210307p:plain

この方法を使えば、長方形を「4つの点」として考えることができます。全ての長方形について4点を取り終わったあと、まとめて累積和を取ることで、長方形領域の重ね合わせが効率的に計算できます。

これでA領域も計算できるので、全ての領域の黒マスが計算できました。

本番中は処理速度ゆえのTLEが取れずに結局通せませんでしたが、細かい書き方を改善することでACすることができました。

ACコード:Submission #2605290 - codeFlyer (bitFlyer Programming Contest)

なお、公式解説では大まかな考え方は同じですが、図のB~D領域を縦横それぞれ1マスに圧縮し、二次元いもす法を行った後に引き伸ばす、という方針になっています。