2019/3/20に行われた部内コンテストに出題された問題の概要と解説です

コンテストのリンクはこちら

A問題

$N$人の友人とパーティをします。$C$人はケーキを持ってきており$i$番目の友人が持っていたケーキの数は$p_i$個です。全員で均等にケーキを分け私は優先的に$1$切れもらえるとき、いくつのケーキをもらえるか求めよ。

$p_i$の総和を$N+1$で割った値の切り上げが答え。

B問題

概要

$N$以下の素数$p,q$のうち$p+q$が素数となるような$(p,q)$の組の個数を求めよ。

• $1 \le N \le 10^7$

解説

$p,q$がともに奇数であるとき、奇数+奇数=偶数のため素数であることはありません。
よって奇数+偶数しかありえないため$2$は必ず用います。
$2$を固定して片側を全探索すればよいです。

計算量は $O(N \log \log N)$

C問題

概要

長さ$N$の数列$a$に対して$2$つの要素を交換する命令が$Q$個与えられる。最初に数列が昇順になるのは何回目の命令か求めよ。

• $2 \le N \le 3*10^5$
• $1 \le a_i \le 10^9$
• $1 \le Q \le 3*10^5$

解説

昇順になった状態は一意に定まるためこれを事前に求めておきます。
ソート済の数列と元の数列の同じ位置を比較して、異なるものが$0$個になったとき昇順になったと判定できます。
命令後に変化するのは$2$要素のみのため毎回この差分のみを計算すればよいです。

計算量は $O(N \log N + Q)$

補足:おそらく $O(N + Q)$ でも解けますが実装がやや面倒そうです。

D問題

概要

文字列$S$が与えられる。$S$が猫の鳴き声か判定したい。猫の鳴き声は次のように定義される。

• 空文字列"“は猫の鳴き声
• X,Yが猫の鳴き声ならば、’m'+X+‘e’+Y+‘w’は猫の鳴き声
• 以上で定義されるものだけが猫の鳴き声

$S$が猫の鳴き声ならば"Cat"そうでなければ"Rabbit"と出力せよ。

• $1 ≦ |S| ≦ 500$
• $S$は’m’,‘e’,‘w’のみを含む

解説

$S$の部分文字列が猫の鳴き声のとき、そこを空文字列に置き換えても$S$が猫の鳴き声かどうかは変わりません。なので$S$の猫の鳴き声の部分を消去していって簡単に判定できるものまで小さくすればよいです。つまり、消去していって最終的な状態が"mew"になっていれば猫の鳴き声です。

消すときは’m’+X+‘e’+Y+‘w’を守るように、“mmewe"を"me"に、“emeww"を"ew"に置換するようにします。

BNFで表されるものは木構造をしているので再帰的な方法でも解けます。

E問題

概要

$N$枚の紙があり、$i$番目の紙をスキャンするのにかかる時間は$T_i$である。3台のスキャナーを並列に使用したとき、すべての紙をスキャンするのにかかる時間を最小化せよ。

• $1 \le N \le 50$
• $1 \le T_i \le 50$

解説

1番目の紙から順に割り振っていくことを考えてみます。ある時点で区切ったときそれまでどう割り振ったかはその後どう割り振れるかに影響しないのでDPができそうです。なのでそれぞれのスキャナーにどれだけ仕事を割り振ったかを持てばよさそうです。

「$dp[i][x][y][z]$=$i$番目の紙まで見てそれぞれのスキャナーに$x,y,z$分の仕事を割り振ることが可能か」と置きます。$dp[N][x][y][z]$で可能なもののうち、$max(x,y,z)$の最小値が答えです。
問題は$x,y,z$がどれほどの大きさになるかです。最大ケース $N=50,T_i=50(i=1,2,…,N)$ を考えるとこの解は$850(= \lceil 50 / 3 \rceil * 50)$なので少なくとも解はこれ以下です。

しかし、$50*(850)^3$は計算量が大きすぎます。そのため工夫が必要です。

$x,y,z$の関係を見ると $\sum T_i = x + y + z$ が成り立つので $z = \sum T_i - x - y$ より $x,y$ で$z$を復元できます。よって$z$は省略することができます。すると最大でも$50*(850)^2$に落ちるのでこれは間に合います。

$dp[0][0][0] = true$ 遷移は$dp[i][x][y] = true$のとき

$dp[i+1][x+T_i][y] = true \\ ~ dp[i+1][x][y+T_i] = true$

です。

計算量は $O (N* (\sum T_i)^2)$ になります。

F問題

概要

本国の首都から姫のいる町まで冷凍された血液を届ける。血液は最大$M$分間冷凍しなくても無事である。冷凍しないで1分輸送するごとに無事な残り時間は$1$分減る。冷凍施設のある町では$1$分冷凍するごとに無事な残り時間が$1$分回復する。

血液の冷凍状態を保ったまま輸送するときの首都から姫のいる町への最短時間を求めよ。

• $2 \le N \le 100$
• $1 \le M \le 100$
• 多重辺、自己ループはない

ただし$N$は町の数、$M$は再冷凍を行うまでの制限時間を表す。

解説

グラフの最短経路問題ですが、冷凍時間の制約があるため単純には解けません。
そこでグラフを拡張します。$d[i][j]$を頂点$i$に冷凍残り時間$j$で到達するときの最短時間とすると、頂点$u$から$v$へ時間$T$かけて移動するとき

$d[v][j-T] = min(d[v][j-T], d[u][j] + T)$

というような遷移が考えられます。また、再冷凍可能な町では

$d[i][j+1] = min(d[i][j+1], d[i][j] + 1)$

という遷移ができます。これはダイクストラ法などで解が求められます。

計算量はダイクストラ法で $O(KM \log NM)$

コメント

B: 意外と偶奇性に気づきにくいです。
C: 1回の命令で変化するものが少ないことに注目します。
D: 構文解析。( )系問題の発展です。
E: DPですが、変数を減らす工夫が必要なので難しいです。
F: 拡張ダイクストラの典型です。

by NOSS