2019/4/3に行われた部内コンテストの解説です。

コンテストのリンク(https://onlinejudge.u-aizu.ac.jp/beta/room.html#YNUCPC_046)

A問題

https://onlinejudge.u-aizu.ac.jp/problems/0019

概要

$N$ の階乗を求めよ。

• $1 \le N \le 20$

解説

ループ文を使って $1$ から順にかけていけばよいです。$N$ が大きいと32bit整数に収まらないのでlong long intを使うことに注意してください。

B問題

https://onlinejudge.u-aizu.ac.jp/problems/0130

概要

列車の巡回記録が与えられる。列車の編成を求めよ。

解説

車掌の移動のシミュレーションができればこの問題は解くことができます。
方法としては車掌の現在位置を保持しておき、まだ訪れていない車両に移動しときにはそこに新たな車両を追加します。車両は列車の先頭と末尾の両方に追加される可能性があることに注意します。
c++では

• list
• deque
• 十分に長い配列

などを使って実装できます。

C問題

https://onlinejudge.u-aizu.ac.jp/problems/3028

概要

$N$ 個のボールがあり、各ボールには色と価値が決められている。色は色 $1$ から色 $C$ まで $C$ 種類あり、色 $i$ のボールは $l_i$ まで選ぶことができる。全体でボールを高々 $M$ 個まで選ぶとき、得られる価値の合計の最大値を求めよ。

• $1 \le M \le N \le 10^5$
• $1 \le C \le 10^5$
• $1 \le l_i \le N$

解説

ボールは貪欲に価値の大きいものから選ぶのが最適です。よって価値の大きさでソートしておき、大きいものから選択していけばよいです。ただし、色の個数制限でとれないものはスキップします。

計算量は $O(N \log N)$ です。

D問題

https://onlinejudge.u-aizu.ac.jp/problems/0348

概要

$1$ から $13$ までの数が書かれた $13$ 枚のカードを使って「7並べ」をします。対戦は2人で行い、初期手札は $6$ 枚ずつで行います。
お互いが最適に行動したとき先手が勝利できるか判定せよ。

解説

まず、勝利したときの状態を考えてみます。手札がすべて場に置かれているはずなので手札のうち最小の数を $f_{min}$ 最大の数を $f_{max}$ とすると、少なくとも $f_{min}$ から $f_{max}$ までのすべての数が場に出ていることになります。すなわち勝利条件は、「場に出ている数の最小値が $f_{min}$ 以下かつ最大値が $f_{max}$ 以上」と言えます。この条件を先に満たしたほうが勝者です。

次にゲームの状態としてどのようなパターンが有り得るのか考えます。場に出せるカードは連続でないといけないので「 $l$ 以上 $r$ 以下のすべての数が出ていてそれ以外は出ていない」という風に表すことができます。つまり区間的に表せます。
ゲームの状態を表すためには

• 場の最小値
• 場の最大値
• 手番はどちらか

という情報があればよいです。これでゲームの状態を完全に再現できます。

ゲーム状態が一致すればそこから最適に行動したときの結果ももちろん一致します。このゲームのパターンの総数は十分小さいので網羅することが可能です。あとは現在の状態から勝利できる状態へ遷移できるかを探索していけばよいです。

よってメモ化再帰によってこの問題は解くことができます。

$memo[i][l][r] =$ 手番が $i$ (先手/後手を01で表す) で場の数が $l$ 以上 $r$ 以下のとき勝利できるか、とします。
遷移は左に置く場合は $memo[(i+1)%2][l-1][r]$ 、右に置く場合は $memo[(i+1)%2][l][r+1]$ になります。遷移先に自分が勝利できる状態があればそれを選べばいいので勝利、そうでない場合は負けと決まります。最終的に求める値は $memo[先手][7][7]$ です。

E問題

https://onlinejudge.u-aizu.ac.jp/problems/0648

概要

$N$ 点の美術品があり、 $i$ 番目の美術品の大きさは $A_i$ 、価値は $B_i$ である。これらの中からいくつかの美術品を選び、それらの大きさの最大値を $A_{max}$ 、最小値を $A_{min}$ 、価値の合計を $S$ とする。このとき $S - ( A_{max} - A_{min} )$ を最大化せよ。

• $1 \le N \le 5*10^5$
• $1 \le A_i \le 10^{15}$
• $1 \le B_i \le 10^9$

解説

$A_{max}$ と $A_{min}$ が固定されているとします。すると大きさが $A_{min} \le A' \le A_{max}$ であるような美術品はすべて選ぶのが最適であることがわかります。なので美術品を $A_i$ でソートしておき、価値の累積和をとっておくことで $S$ を高速に求められるようになります。以後、美術品は $A_i$ で昇順にソートされているとします。

$sum[i] =$ $i$ 番目までの美術品の価値の総和、とします。
これを用いて式を変形すると $i \ge j$ として次のようになります。

$$ S - (A_i - A_j) = ( sum[i] - sum[j-1] ) - (A_i - A_j) \\ ~ = (sum[i] - A_i) - (sum[j-1] - A_j) $$

式を $i$ と $j$ の式に分離することができました。

$(iに関する式) - (jに関する式)$ の形をしているので $(iに関する式)$ を最大化しつつ $(jに関する式)$ を最小化すればよさそうです。ここで $i$ を固定すれば $j$ は $i \ge j$ より $i$ 以下で $sum[j-1] - A_j$ が最小のものを選べばよいです。

以上より、$i$ を $0$ から順に見ていき、そのたび選ぶべき $j$ を更新していけば各 $i$ について最適解が得られます。これらの中の最大値が答えになります。この計算量は $O(N)$ です。

全体の計算量はソートがボトルネックになり $O(N \log N)$ になります。

F問題

https://onlinejudge.u-aizu.ac.jp/problems/2608

概要

$N$ 頂点 $M$ 辺の連結な無向グラフが与えられる。頂点 $u,v$ 間に辺を追加したとき $s$ から $t$ への最短経路の長さが $1$ だけ小さくなるような $u,v$ の組の個数を求めよ。

• $2 \le N \le 10^5$
• $1 \le M \le 3*10^5$

解説

辺を追加して最短経路が短くなるということは新たな最短経路は必ず辺 $(u,v)$ を通るはずです。すなわち経路は $s \to u \to v \to t$ となるはずです。ここで $u \to v$ は距離 $1$ ですから元の最短経路の長さを $X$ とすると $s \to u$ と $v \to t$ の距離の和は $X-2$ であれば条件を満たします。 $s \to u$ の距離を $i$ から順に変化させれば求めるべき組の個数は次のように表せます。

$$ \sum_{i=0}^{X-2} (sからの最短距離がiである頂点の個数)*(tからの最短距離がX-2-iである頂点の個数) $$

ある始点からの最短距離はダイクストラ法で求めることができるのでこの問題を解くことができます。

計算量は $O(M \log N + N)$ です。

コメント

新入生の方が1人見学に来てくれました。次回の活動からは新歓の本番になるので競プロの魅力をうまく伝えられたらなと思います。