見出し画像

競プロ参戦記 #28 「白黒経路とカードゲーム」 | エイシング 2019 [ABCD]

あけましておめでとうございます。今年初参加の AtCoder です。着手した問題の考察を書いていきます。


AISing Programming Contest 2019 / エイシング プログラミング コンテスト 2019

問題リスト: https://atcoder.jp/contests/aising2019/tasks


A - Bulletin Board

問題概要: N*N の盤面に H*W の長方形を配置する方法は何通りか


考察: 長方形の左上隅の座標 (y, x) としてありうる場合の数を求めればいいです。これは y の場合の数と x の場合の数の積になります。

y が満たすべき条件は 0 ≤ y かつ y + H ≤ N 、つまり 0 ≤ y < N+1-H です。だから y は (N+1-H) 通り。同様に x は (N+1*W) 通りです。

筆者の解答[AC]: https://atcoder.jp/contests/aising2019/submissions/3987876


B - Contests

問題概要: 数列 P が与えられる。A 以下の要素1つと、(A+1) 以上 B 以下の要素1つと、(B+1) 以上の要素1つを選んで組にできる。最大で何個の組ができるか


考察: 具体的な選び方は考えなくていいのがポイント。A 以下であるものの個数、 (A+1) 以上 B 以下であるものの個数、 (B+1) 以上であるものの個数を数えます。これらの最小値が答えです。


筆者の解答 [AC] : https://atcoder.jp/contests/aising2019/submissions/3987707


C - Alternating Path

問題概要: 白または黒のマスからなる H*W の盤面がある。白のマスと黒のマスのペアで、白黒経路が存在するものの個数を求めよ。ただし白黒経路とは、通るマスの色が白、黒、白、黒、と交互になっているものをいう。


考察: H, W ≤ 400 なので O((H * W)^2) 時間の解法は間に合いません。半分全列挙が頭をよぎりましたがダメだと思います。


単純な例として、盤面が完全にチェッカー模様になっている (白や黒が隣接しない) ケースを考えました。この盤面では、どの白マスからどの黒マスへも白黒経路で移動できることが分かります。

白白や黒黒で隣接しているマスの境界線は、その上を白黒経路で通ることはできないことに気づきました。その境界線に沿って盤面を切断して、それぞれの区画の内側だけ考えればいいです。

区画の内側には白白や黒黒で隣接する部分はないので、上記のチェッカー盤面と同様に、あらゆるペアが白黒経路でつながっています。白の個数と黒の個数の積が答え。全体の答えはその総和です。


次に実装です。盤面を上述の区画ごとに分類するのは DFS を使って、いわゆる「2部グラフの判定」と同じ要領でできます。すなわち、いずれかのマスから始めて、白と黒が隣接する境界を通ってなるべく多くのマスを踏みに行きます。これによって踏めたマスは、最初のマスと同じ区画に属すことが分かります。

踏めるマスがなくなったら、まだ踏んでいないマスを探して、同じことをします。盤面全体を踏んだら終わりです。全体としては O(H * W)。

筆者の解答 [AC]: https://atcoder.jp/contests/aising2019/submissions/3987560


D - Nearest Card Game

問題概要: 整数が書かれたカードが N 枚ある。x の値が Q 通り与えられるので、そのそれぞれについて、以下のゲームを行ったときに高橋くんが取るカードの値の総和を求めよ。

高橋くんと青木くんが交互にカードを取る。高橋くんは、残っているカードのうち値が最大のものをとる。青木くんは、残っているカードの中で x との差が最小であるもの (複数あるときは値が最小の1つ) をとる。


考察: N,Q ≤ 10^5 なので、普通にゲーム進行をシミュレーションする O(N * Q) 時間の解法はダメです。

値が x 以上のカードがすべて取られた後、高橋くんと青木くんはどちらも最大のカードを順番に取るようになります。このとき高橋くんが取るカードの総和は累積和を使えば O(1) で分かります。そのため、ゲームの序盤に2人が取るカードが分かればいいです。

具体例をやっていくと、ゲームの序盤で高橋くんが取りたいカードと、青木くんが取るカードは重ならないことに気づきました。取るカードが重ならないというのは、カードの値が大きい数枚を実際に高橋くんが取り、x との差が近い同じ枚数のカードを青木くんが取る、ということです。

しかも、 **x の値が小さければ小さいほど、重ならない手数は長い** ことが分かります。青木くんが取るカードの範囲が、高橋くんが取るカードの範囲から遠くなるからです。例えば x = a で2人がそれぞれ t 枚のカードを重なりなく取ったとしたら、 x = a-1 でも2人は少なくとも t 枚のカードを重なりなく取ります。

x の値を降順に並べて、前のクエリーで計算した結果 (t の値、つまり高橋くんと青木くんが取るカードの範囲) を再利用すれば、全体として O(N + Q log Q) 時間で解けることが分かります。


ここからの実装も大変ですが、省略します。

筆者の解答 [AC]: https://atcoder.jp/contests/aising2019/submissions/3991207


その他: 公式の解説は二分探索を使う解法のようです。どっちにしても実装は大変だと思います。


おわりに

D 完でした。レートが 1582 → 1635 (+53) に変わって、ついに青になりました!

この記事が気に入ったらサポートをしてみませんか?