九州大学プログラミングコンテスト2018　参加記録＆解説（A～F）

九州大学プログラミングコンテスト2018 - AtCoder

6完で31位でした。正答数は良い感じですが、色々バグらせました…

f:id:betrue12:20181020180500p:plain

A - QUPC

解法

$ans = 4N + 2010$ を計算すればよいです。

ACコード

Submission #3436129 - 九州大学プログラミングコンテスト2018

B - Tapu & Tapi

（Ruby）B - Tapu & Tapi

解法

値が大きい方の硬貨から見ていきます。

100円玉が偶数の場合、それを普通に分ければよいです。もし奇数の場合は、余った100円玉の相手になるように、小さい硬貨から100円を借りてこなければいけません。

10円玉についても同様にします。最終的に1円玉が足りて、かつ偶数であればよいです。

ACコード

（Ruby）Submission #3436312 - 九州大学プログラミングコンテスト2018

C - Ito Campus

解法の流れとしては、まずイノシシまで $X$ 歩以内に到達可能な点を求めます。その後、うしくんさんがそれらの点を避けてゴールにたどり着く最小距離を求めます。これらはともにBFSで求めることができます。

まずイノシシについて考えます。「イノシシまで $X$ 歩」とはつまり「イノシシから $X$ 歩」であるため、イノシシをBFSの始点とします。イノシシは複数頭いるため、BFSを複数の始点から開始する必要があります。といっても、最初にキューに入れる点を複数にすればそれでOKです。

同時並行で探索が進み、あちこちが更新されていくので少し違和感があるかもしれません。イメージとしては、1つの始点から探索を広げるのではなく、「距離が0の点（始点）を設定する」→「その隣を見て、距離が1の点を確定させる」→「その隣を見て、距離が2の点を確定させる」…という全体の流れを意識するといいと思います。

イノシシの処理ができたら、イノシシまで $X$ 歩以内の点を通行不可扱いにして、うしくんさんのBFSをやります。

ACコード

（C++）Submission #3437495 - 九州大学プログラミングコンテスト2018

このコードでは、イノシシまでの最短距離を全て計算してしまい、うしくんさんの移動の際にその距離を参照しています。実際に必要なのは「 $X$ 歩以内かどうか」の情報だけなので、これを true/false のフラグで管理する、 $X$ 歩以内の場所を # で埋める、などの実装も可能です。

D - Novelist

解法

「時刻 $t$ に王都にいる（依頼を開始できる）状態であるとき、それまでに完了した依頼の最大数」を $dp\lbrack t \rbrack$ とします。初期状態は $dp\lbrack 0 \rbrack = 0$ です。

時刻 $t$ に王都にいて、それ以降に王都で受けられる依頼を受けることを考えます。そのときの動きとして、次のようなものが考えられます。

f:id:betrue12:20181020190939p:plain

依頼をこなしたあと、戻りの依頼が存在しない場合、合計で $dp\lbrack t \rbrack + 1$ 個の依頼をこなして依頼終了となる。
依頼を2つこなして王都に戻ってこられる場合、帰りの依頼の終了時刻を $t^{\prime}$ として、 $dp\lbrack t^{\prime} + 1 \rbrack \leftarrow \max(dp\lbrack t^{\prime} + 1 \rbrack, dp\lbrack t \rbrack + 2)$ とすることができる。

また、もちろん「時刻 $t$ に依頼を受けない」という選択もできます。その場合は次の時刻に持ち越されるため、 $dp\lbrack t + 1 \rbrack \leftarrow \max(dp\lbrack t + 1 \rbrack, dp\lbrack t \rbrack)$ となります。

このような「配るDP」をすることで解を求めることができますが…時刻は $10^{9}$ オーダーで普通に扱うことはできないので、座標圧縮をします。王都を基準にしたDPを考えているため、王都から受けられる依頼の開始時刻、つまり $A_{i}$ を座標点として採用します。

DPの遷移においては

王都から依頼を受けて都市 $X$ に到着後、都市 $X$ で受けられる依頼のうち最も早いものはどれか
その依頼を受けて王都に戻ってきたあと、次に王都で依頼を受けられる最も早い時刻はいつか

が必要になりますが、これらはともに二分探索を使って求めることができます。

最終的な解は $dp\lbrack \infty \rbrack$ とは限らず、王都以外の都市で依頼を終えることもあるため、遷移の中で逐次更新をしていくとよいです。

ACコード

（C++）Submission #3438131 - 九州大学プログラミングコンテスト2018

終了後、区間スケジューリングとして見ると楽だという話を見てなるほどと思いました。あまりやっていることは変わりませんが、明示的な座標圧縮も必要ないですし、そちらのほうが楽かもしれません…

E - Treeone

解法

各 $A_{i}$ について、「 $A_{i}$ を含む区間で、合計が0になるものはいくつあるか」を求めます。その数が最も大きい要素の値を変更するのが最適です。変更する際に他の区間に影響を与えてしまわないか心配ですが、5000兆とかの極端な数に変更しておけば他の区間の合計を0にしてしまうことはありません。

ということで、「 $A_{i}$ を含む区間で、合計が0になるものはいくつあるか」の求め方ですが…区間がいくつかあり、各要素について「その要素を含んでいる区間がいくつあるか」というものを求めたいので、いもす法が使えそうです。ただ、合計が0になる区間は最大で $O(N^{2})$ 個あり、これをバラバラに扱っていると間に合いません。

いもす法は、（インデックスのとり方にもよりますが）区間ごとに始点の位置に+1して、終点の次の位置に-1して、最後に累積和を取る方法です。そのため、各位置について「ここが始点となる区間はいくつあるか？」「ここが終点となる区間はいくつあるか？」を求めることができれば、+1/-1の計算をまとめてすることができます。

「ここが終点となる、合計が0である区間はいくつあるか？」を求めるには、左から累積和を求めていけばよいです。お馴染みの「Zero-Sum Ranges」です。

f:id:betrue12:20181020195935p:plain