ARMERIA

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

九州大学プログラミングコンテスト2018 参加記録&解説(A~F)

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

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

f:id:betrue12:20181020180500p:plain

A - QUPC

A - QUPC

解法

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

ACコード

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

B - Tapu & Tapi

RubyB - Tapu & Tapi

解法

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

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

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

ACコード

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

C - Ito Campus

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

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

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

「ここが始点となる、合計が0である区間はいくつあるか?」を求めるには、同じことを右からやればよいです。

これらを求め、いもす法で「その要素を含んでいる区間がいくつあるか」を復元し、その最大値を合計が0の総区間数から引いてやれば答えが求められます。

ACコード

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

F - Team Making

F - Team Making

解法

 N がとても小さいので、bitDPなどの解法が使えそうです。「 N 人のうち集合  S に属する人を使ってできるグループの分け方」を  dp\lbrack S\rbrack とするDPをします。

 dp\lbrack S\rbrack を求める際に、 S に含まれている人からグループを1つ作る方法を考えます。そのグループを  T とすると、 dp\lbrack S - T\rbrack を使って遷移を計算することができます。

ただしグループの取り方全てを考えてしまうと、同じ分け方を何度も数えてしまうので、そうならないようにルールを決めます。具体的には、「 S に含まれる人のうち番号の若い人は必ず使う」というルールです。常にこのルールを守っていけば、同じ分け方を何度も数えることはありません。

 S に含まれる人のうち一番若い番号を  i とすると、作られるグループは

  •  i 1人だけのグループ( O(1) 個)
  •  i とあと1人のグループで、レート条件を満たすもの( O(N) 個)
  •  i とあと2人のグループで、レート条件を満たすもの( O(N^{2}) 個)

で、集合1つにつき  O(N^{2}) で遷移を計算できます。

全体計算量が  O(N^{2} \times 2^{N}) となり、単純計算で  18^{2} \times 2^{18} = 84934656 です。億を超えていないので、1つ1つの計算が軽ければ間に合います。

ACコード

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

ソートしておくと少しだけ枝刈りができたり、各レートから予め  K を引いておくと平均が  K 以下かどうかの判定が楽だったり、ちょっとしたテクニックはあります。