GCJ 2022 Round 1B 問題概要 & 解法メモ

結果

Pancake Deque

https://codingcompetitions.withgoogle.com/codejam/round/000000000087711b/0000000000acd59d

問題概要

• 長さ N のパンケーキの美味しさの列が与えられる
• N 人にひとつずつパンケーキを渡す
  • 渡せるパンケーキは deque の要領で、列の左端 or 列の右端のみ
• i 番目の人は次の条件を満たすときだけ食事代を支払う
  • i 番目の人に渡すパンケーキの美味しさを d とする
  • 1 番目, 2 番目, ..., i - 1 番目の人に渡したパンケーキの美味しさがどれも d 以下である
• 渡すパンケーキの順番を工夫して食事代を支払う人数を最大化

解法

「いままで渡したパンケーキの美味しさの最大値」を最小にすることを考えると
毎回、左端と右端のパンケーキで美味しさが小さいほうを選ぶ、とすればよさそうです。

たとえば N = 7 で各パンケーキの美味しさが 1 4 1 4 2 1 3 のとき、次の順にパンケーキが減っていくことになります。

O(N)

1 4 1 4 2 1 3
1 4 1 4 2 1
1 4 1 4 2
  4 1 4 2
  4 1 4
  4 1
    1
    

Controlled Inflation

https://codingcompetitions.withgoogle.com/codejam/round/000000000087711b/0000000000accfdb

問題概要

• N 人の人が P 個ずつ品物を持っている
• 各品物には適切な空気圧がある
• はじめ、空気入れの圧力は 0
• 一度ボタンを押すと空気入れの圧力を +1, -1 できる
• 空気入れの圧力を、品物に合った圧力にできればその品物に空気を入れられる
• 空気入れを使えるのは 1 番目の人, 2 番目の人, ..., N 番目の人 の順
• それぞれの人が持つ P 個の品物に空気を入れる順番を工夫してボタンを押す回数を最小化

解法

i 番目の人が空気を入れたい品物を空気圧の順にソートしておき X[i][1], X[i][2], ..., X[i][P] とします。

dp[i][j]: i 番目の人まで空気を入れ終わって、空気入れの圧力が X[i][j] (最後に空気を入れたのが j 個目の品物) のときのボタンを押した最小回数

(i, j) からの遷移は (i + 1, 1), (i + 1, 2), ..., (i + 1, P) の P 通りあります。
(i, j) → (i + 1, k) の遷移では、空気入れの圧力の変化として次のふたつのみを考えればよいです。

• X[i][j] → X[i + 1][1] → X[i + 1][P] → X[i + 1][k]
• X[i][j] → X[i + 1][P] → X[i + 1][1] → X[i + 1][k]

dp[N][*] の最小値が答えになります。

O(NP^2)

実は、公式解説によると、i 番目の人が空気を入れ終わったときの空気入れの圧力は X[i][1] or X[i][P] のみを考えればよいため、計算量が O(NP) に落ちます。

ASeDatAb

https://codingcompetitions.withgoogle.com/codejam/round/000000000087711b/0000000000acd29b

問題概要

• インタラクティブ問題
• ジャッジは初め 8bit の値 X を自由に決める
  • この値は秘密で競技者のプログラムからは見えない
• 一度のクエリで、同じく 8bit の値 V をジャッジに送信できる
• ジャッジは次の手順で X を置き換えて popcount(X) を返す
  • 好きな回数 V を巡回シフトする
  • X を (X xor V) で置き換える
• 300 回以下のクエリで X = 0 (つまり popcount(X) = 0) にせよ

解法

Test Set 1 のみ解きました。

Test Set 1 の制約:

• ジャッジは最初の X をランダムに決める
• ジャッジは (クエリごと独立に) ランダムな回数だけ V を巡回シフトする

X を 0 にするためには、少なくとも popcount(V) = popcount(X) である必要があります。
そのような V をランダムに作ってジャッジに送信、とすると合計クエリ回数が 300 回以内に収まりました。(よくわかってない)