ARMERIA

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

codeFlyer(オープンコンテスト) 参加記録

codeFlyer (bitFlyer Programming Contest)オープンコンテスト - AtCoder

codeFlyer 本選」のほうは、予選突破した参加者のみで行われるオンサイトコンテスト。オープンコンテストは、それと同じタイミングで同じ問題を解けるオンラインコンテストです。

オンサイトはやっぱり狭き門なので、オンラインで開催してくれるのはとてもありがたいです。

そして結果はABCFの4完、オープンコンテスト3位でした!

f:id:betrue12:20180630214549p:plain

これがratedだったらなーと少しだけ思いますが、それでも嬉しいです。Fを通せたのがとても大きい。

というわけで解けた4問を振り返っていきます。

A - 値札

A - 値札

10で何回割れるかを全部数えて、その最小値が答えです。整数を10で割る代わりに、文字列として処理して末尾の0の数を数えてもいいです。

ACコード:Submission #2758182 - codeFlyer (bitFlyer Programming Contest)オープンコンテスト

B - 交通費

B - 交通費

データに対して大量のクエリを処理する問題は、前計算 → クエリを効率的に処理 が王道パターンです。全クエリを毎回真面目に計算すると  O(NQ) 10^{10} くらいになりTLEします。

とはいえ、何を前計算すればよいかの見当を付けるため、まずはクエリの処理方法を考えてみます。

クエリ  C D が与えられた時、参加者の家の位置  X を横軸に取ると、交通費(縦軸)は以下のようなグラフになります。

f:id:betrue12:20180630220207p:plain

このため、 X_{i} たちを次の4つにグループ分けできます*1

  1.  X_{i} \lt C - D である  X_{i} に対しては、交通費は  D 。個数が分かれば(個数) ×  D でまとめて計算できる。
  2.  C - D \le X_{i} \lt C である  X_{i} に対しては、交通費は  C - X_{i}
  3.  C \le X_{i} \lt C + D である  X_{i} に対しては、交通費は  X_{i} - C
  4.  C + D \le X_{i} である  X_{i} に対しては、交通費は  D 。個数が分かれば(個数) ×  D でまとめて計算できる。

というわけで、以下の2つのことができれば交通費の総和が効率的に求められます。

  • 1~4それぞれの範囲の境界となる  X_{i} を効率的に求める。境界が分かれば、範囲内の要素の個数も求められる。
  • 範囲2, 3の交通費の総和を効率的に求める。

境界を求めることは二分探索で効率的にできます。1回あたり  O(\log N) なのでクエリごとに行っても大丈夫でしょう。

次に2, 3の交通費総和です。3の式で考えてみます*2

交通費の総和は  \sum (X_{i} - C) = \sum X_{i} - nC です。ここで  \sum は範囲内の  X_{i} それぞれについて加算することを示し、  n はその要素数です。要素数の計算は、二分探索で解決済みです。

 \sum X_{i} は、ある範囲内の連続する要素の和になっています。これは累積和を事前に求めておくことで高速に計算できます。具体的には  S_{i} = X_{1} + ... + X_{i} を事前に求めておけば、  X_{x} + ... + X_{y} = S_{y} - S_{x-1} で計算可能です。

これで全ての計算を効率的に出来る方法が揃ったので、実装すれば解けます。

これらを図に描き足してみました。文章と図、分かりやすいほうで理解していただければと思います。

f:id:betrue12:20180630221845p:plain

ACコード:Submission #2758650 - codeFlyer (bitFlyer Programming Contest)オープンコンテスト

C - 部分文字列と括弧

C - 部分文字列と括弧

「括弧の対応が取れている文字列」は、AtCoderの過去問でもいくつか出題されている題材ですが、

  • ( を+1、) を-1として累積和*3を取った時に、
    • 最後にちょうど0になる
    • 途中で一度も負の値にならない

を満たすものとして考えることができます。途中で負の値になるものというのは、例えば )( みたいなやつです。

求めるのが「区間の数」ということでしゃくとり法を考えたくなりますが、残念ながら単調性が成り立ちません。

どう考えるかですが、「最初から計算した累積和」を折れ線グラフとして図示してみると、見通しがよくなります。

f:id:betrue12:20180630223820p:plain

過去に出現した「そこまでの累積和が同じ点」を始点とすれば、「最後にちょうど0になる」の条件を満たせます。これを数えるには、「累積が  X になった点の数」を配列やmapなどで管理しておけばよいです。

「途中で一度でも負にならない」のほうの条件は、「区間内に、始点&終点の累積和を下回っているところがない」となります。これをどう実装すればいいか考えてみます。

f:id:betrue12:20180630224829p:plain

( によって+1されて累積和が  X になったとすると、それより前の点は累積和  X で揃える区間の始点として使うことはできません。そのため、一度「累積が  X になった点の数」をリセットして数え直します。

以上の内容を実装すれば解けます。hash[0] = 1 を書きそこねると文字列の一番最初から始まるパターンを数え漏らすので注意しましょう。(1敗)

ACコード:Submission #2759109 - codeFlyer (bitFlyer Programming Contest)オープンコンテスト

F - 配信パズル

F - 配信パズル

間の2問を飛ばして何でFが解けているんだって感じですが…実は過去問に類題があるので、それを覚えていると難易度が下がります。

F - Flip and Rectangles

詳しくはこの問題の解説を参照していただきたいのですが、「行または列の色反転を繰り返すことで、全体を同じ色にできる」ことと「全ての2×2成分について、その中に含まれる黒マスが偶数個である」ことが同値になります。

「2×2成分」は、その中心にある交差点*4と対応付けることができます。解説にならい、周囲の黒マスが奇数個である交差点を「悪い交差点」と呼びます。

さて、各クエリごとに行う操作は

  1. 前回配信された盤面と差分が1マスだけの盤面が配信されてくる
  2. 最大1回、盤面の中の長方形領域を指定し、領域中の全てのマスの白黒を反転させることができる
  3. 行または列の色反転を好きなだけ行うことができる

です。最後に目的を達成できるかどうか、逆から考えてみましょう。

操作3によって全マスを同じ色にできる条件は先ほど示した通りなので、

  • 操作3の開始時点で、悪い交差点が0個であればよい

です。そのため、操作2によって悪い交差点を0個にできる条件について考えます。

f:id:betrue12:20180630231737p:plain

「長方形領域を指定し、領域中の全てのマスの白黒を反転」することで、その四隅(外周を除く)にある交差点の「周囲の黒マスの偶奇」が変化します。それ以外の交差点は、周囲のマスで反転するものが偶数個なのでそのままです。

これを考慮すると、操作2によって悪い交差点を0個にできる条件は、

  • 悪い交差点が0個
  • 悪い交差点が1個。どこでもよい
  • 悪い交差点が2個で、縦または横に並んでいる
  • 悪い交差点が4個で、長方形を作るように並んでいる

のいずれかです。

ここまでくればあと一息です。各盤面について「悪い交差点」を列挙すればよいのですが、全部の交差点を毎回計算していると間に合いません。

配信される盤面は「前回との差分は1マスだけ」ということに着目します。1マスだけ反転することで、影響を受ける交差点は周りの最大4つです。

f:id:betrue12:20180630232630p:plain

そのため、その1マスの周囲の交差点について、悪い交差点かどうかを反転させればよいです。これで計算量を抑えられます。

まとめると、以下のような解き方になります。

  1. 最初の盤面について悪い交差点を列挙する。
  2. 悪い交差点を0個にできる条件に応じてYes/Noを判定する。
  3. 次の盤面で反転している1マスについて、その周囲の交差点(最大4つ)が悪い交差点かどうかを反転させる。
  4. 悪い交差点を0個にできる条件に応じてYes/Noを判定する。
  5. 以降、繰り返し。

ACコード:Submission #2759805 - codeFlyer (bitFlyer Programming Contest)オープンコンテスト

このコードはC++です。「Flip and Rectangles」の方でもRubyだと前計算だけでTLEした経験があり、絶対間に合わないと踏んで最初からC++で書きました。まだ速い書き方に慣れてなくて制限時間もギリギリなのですが、通ってよかったです。

おわりに

解けた問題だけの解説ということでちょっといびつな感じになりましたが、どれもなかなか解説しがいのある問題でした…。

この記事の作成時点ではまだ公式解説が公開されていないので、少しでも理解の助けになれば幸いです。

明日はABC/ARCがあります!ratedコンテストでも良い成績を残していきたいですね。こちらも頑張りましょう。

脚注

*1:等号はどちらにあっても構いませんが、ダブって数えないように注意。

*2:2は符号を反転させたものなので、同じ方法でできます。

*3:プログラマ的に言うと、「ネストの深さ」として理解すると分かりやすいかもしれません。

*4:辺の交点のうち外周に含まれないものを「交差点」と呼んでいます。