Google code jam 2020 qual 参加記
Google社が主催する国際的プログラミングコンテストの予選を突破しました！
はじめに
1~4問目を解き、68pts.でした。
Google code jamとは、毎年開催されているGoogle社によるプログラミングコンテストです。 コンテスト全体は複数のラウンドからなり、勝ち上がることで様々な賞品や賞金を手にすることができます。
今年度の大まかなスケジュールは tatyam.hatenablog.com
より詳細なスケジュールや過去のコンテストなどは codingcompetitions.withgoogle.com
この辺りをご覧ください。
Tシャツゲットは人数が限られてくるため現実的に難しい場合もありますが、お祭り感覚で去年から参加しています。
今年は謎にやる気があり通過ボーダー+αで問題を解いたので解法を知るしておこうかと思います。
問題
Vestigium (7pts)
今年の記念すべき1問目です。
1 ~ N の数字からなるN×N行列が与えられる。
・対角線上の数字の和 ( = Vestigium / trace )
・重複した数字を持つ行および列の数
を出力せよ。
2 ≤ N ≤ 100
制約が小さいので対角線、各列、各行をそれぞれ見ていけばよいです。オーダーはO(N2)。
重複を探す際は、2 2 3 3 などの列で2回分数えないように適宜breakします。
解答
import math import sys def getN(): return int(input()) def getList(): return list(map(int, input().split())) def solve(): n = getN() mat = [] for i in range(n): mat.append(getList()) k = 0 for i in range(n): k += mat[i][i] r = 0 for i in range(n): # print(r) app = [0 for i in range(n+1)] for j in range(n): num = mat[i][j] if app[num]: r += 1 break app[num] += 1 c = 0 for i in range(n): app = [0 for i in range(n+1)] for j in range(n): num = mat[j][i] if app[num]: c += 1 break app[num] += 1 return k, r, c def main(): cases = getN() for case in range(cases): k, r, c = solve() print("Case #{}: {} {} {}".format(case+1, k, r, c)) if __name__ == "__main__": main()
Nesting Depth (5pts, 11pts)
1-9の数字からなる文字列が与えられる。
開きおよび閉じ括弧 "(" , ")" を適切に挿入して以下の条件を満たす文字列を構成したい。
・括弧の開閉における整合性が取れている。
・それぞれの数字は、それを囲っている括弧ペアの数と等しい。
・上二つを満たすうち、最短のもの。
1 ≤ |S| ≤ 100
貪欲に構成することができます。
まだ閉じられていない括弧の数(これが現在の深さ)を記録しながら左から順に数字を読んでいき、読んだ数字と深さが等しくなるように括弧の閉じ開きを追加して調整します。
実装によっては最後に括弧の閉じ忘れが生まれてしまうので注意しましょう。
解答
import math import sys # input = sys.stdin.buffer.readline def getN(): return int(input()) def getList(): return list(map(int, input().split())) def solve(): s = input().strip() ans = "" stack = 0 for c in s: nc = int(c) if stack <= nc: ans += ("(" * (nc - stack)) ans += c else: ans += (")" * (stack - nc)) ans += c stack = nc ans += (")" * stack) return ans def main(): cases = getN() for case in range(cases): ans = solve() print("Case #{}: {}".format(case+1, ans)) if __name__ == "__main__": main()
Parenting Partnering Returns (7pts, 12pts)
この場には二人の子供がいて、開始時刻Sと終了時刻Eで表されるNこのアクティビティが用意されている。
子供が取り組めるアクティビティは一つずつで、期間が重複する二つのアクティビティを一人で行うことはできない。
アクティビティを適切に二人に割り振ることで、すべてを行うことができるか？可能であればその割り振りも出力する。
0 ≤ Si < Ei ≤ 24 × 60
2 ≤ N ≤ 10 (7pts.)
2 ≤ N ≤ 1000 (12pts.)
全てのアクティビティをこなすことが目標なので、まず一番最初に始まるものどちらかに割り振る。次に早く始まるものがやってきた時点で、手の空いている子供がいればその子に渡す。
これの繰り返しによって線形時間でシミュレーションを行うことができます。二人とも手がふさがっている時にアクティビティがやってきたら終了。
実装上はそれぞれが最後に取り組んだアクティビティの終了時間を配列などで持っておけばOKです。
入力を開始時間でソートする必要があるので全体のオーダーはO(NlogN)。復元のためにソート前のインデックスを保持しておくのを忘れずに。
解答
import math import sys def getN(): return int(input()) def getList(): return list(map(int, input().split())) def solve(): n = getN() ans = "" cend = 0 jend = 0 sch = [] for i in range(n): sch.append(getList() + [i]) sch.sort() ans = ["" for i in range(n)] for st, en, idx in sch: if st >= cend: ans[idx] = "C" cend = en elif st >= jend: ans[idx] = "J" jend = en else: return "IMPOSSIBLE" return "".join(ans) def main(): cases = getN() for case in range(cases): ans = solve() print("Case #{}: {}".format(case+1, ans)) if __name__ == "__main__": main()
ここまでで予選通過です！
ESAb ATAd (1pts, 9pts, 16pts)
長さBのビット列を復元したい。あなたは1つのクエリで任意のビットの状態(1/0)を知ることができる。
ただし、あなたが10回クエリを投げるごとに以下のうちいずれかの変化が起きる。
・すべてのビットが反転する
・ビット列全体が左右反転して鏡写しになる
・ビット反転および左右反転の両方が起こる
・元の状態が保たれる
4つの変化は等確率で起こり、前回の変化とは独立である。150回までのクエリの中でビット列が確定したら、その時点における答えを出力せよ。ただし、回答クエリは変化が起こるまでの10回のクエリのうち1つとしてカウントされない。
B = 10 (1pts.)
B = 20 (9pts.)
B = 100 (16pts.)
インタラクティブ問題です。
B = 10の場合であれば変化が起こる前にすべてのビットを特定できるので問題ありません。
B = 20, 100 の場合は状態変化を避けることができないので変化が起きるごとに「今4種類のうちどの状態にいるのか」を何とかして把握しないと過去の質問クエリが無駄になってしまいます。
そこで左右反転という条件を鑑みて、左右両端から同じ位置(1と20, 2と19, .... )にあるビットペアに着目します。
それぞれのペアは同種か異種に分別でき、以下のような状態を取ります。
| 同種 | 異種 | |
|---|---|---|
| ORG(例) | (0, 0) | (0, 1) |
| REV | (0, 0) | (1, 0) |
| MIR | (1, 1) | (1, 0) |
| REV + MIR | (1, 1) | (0, 1) |
よってそれぞれのペアは独立に考えることができてかつ2種類しか状態がないことがわかります。 10個のクエリを
- 同種状態確定のクエリ1
- 異種状態確定のクエリ2
- 新情報獲得のためのクエリ3 ~ 10
とすることで今の状態を確認しながらビット列を得ることができます。150回の質問クエリでB = 100にも十分間に合います。
解答
import math import sys def getN(): return int(input()) def getList(): return list(map(int, input().split())) def flprint(cont): print(cont) sys.stdout.flush() def solve10(): ans = "" for i in range(10): flprint(i+1) ans += input().strip() flprint(ans) if input().strip() == "N": sys.exit() return def setvalue(value, status): if status: return value else: if value == 0: return 1 else: return 0 def make_answer(ans1, ans2, status): ans1 = [setvalue(v, status[d]) for v, d in ans1] ans2 = [setvalue(v, status[d]) for v, d in ans2] ans2.reverse() flprint("".join(list(map(str, (ans1+ans2))))) res = input().strip() if res == "N": sys.exit() return def solve(B): appear = [0, 0] base = [-1, -1] status = [True, True] current_pos = 1 ans1 = [] ans2 = [] for chunk in range(20): # print(ans1) # print(ans2) # print(status) if current_pos > B // 2: make_answer(ans1, ans2, status) return # validation step 1 if appear[0] == 0: flprint(1) _ = getN() else: flprint(appear[0]) status[0] = (getN() == base[0]) # validation step 2 if appear[1] == 0: flprint(1) _ = getN() else: flprint(appear[1]) status[1] = (getN() == base[1]) for i in range(4): if current_pos > B // 2: make_answer(ans1, ans2, status) return flprint(current_pos) num1 = getN() flprint(B - current_pos + 1) num2 = getN() isdiff = int(1 - (num1 == num2)) if appear[isdiff] == 0: appear[isdiff] = current_pos base[isdiff] = num1 ans1.append([num1, isdiff]) ans2.append([num2, isdiff]) else: ans1.append([setvalue(num1, status[isdiff]), isdiff]) ans2.append([setvalue(num2, status[isdiff]), isdiff]) current_pos += 1 def main(): t,b = getList() if b == 10: for _ in range(t): solve10() else: for _ in range(t): solve(b) if __name__ == "__main__": main()
Indicium (7pts, 25pts)
解けません！教えてください
N, K が与えられる。
ナンプレのように各行各列に重複する数字のないN×N行列で(これをLatin squareという)、
左上から右下への対角線成分の和がLであるものを構成せよ。
2 ≤ N ≤ 5 (7pts.)
2 ≤ N ≤ 50 (25pts.)
2時間くらい考えたところで普通に難しいという情報を得て諦めてしまいました。 Latin square - Wikipedia から
1行目および1列目が 1, 2, 3, ... , NであるLatin squareを"reduced"といい、
すべてのLatin squareはreducedな状態からの行または列の置換で構成できる
とのことだったので何とか使えないかと思ったのですが... ギブアップです。
余談
出力およびUI
2回目なのでまあ、ご愛嬌という感じです。
注意力の鬼なので、なんと出力形式に依るWAを1回も出さずに済みました。
Round1からはペナルティも重要な要素なので、このまま行きたいですね。
インタラクティブ問題
GCJではほぼ必修科目であり、かつなかなかの障壁です。
2年目にしてようやくinteractive_runnerおよびtesting_toolの使い方を理解しました。
python interactive_runner.py python testing_tool.py 0 -- ./my_binary
とドキュメントに書いてあったので脳死で
python interactive_runner.py python testing_tool.py 0 -- gcj2020quald.py
と入力し、詰んでいました。
--の後には実行可能ファイルを引数として渡す必要があるので、正しくは
python interactive_runner.py python testing_tool.py 0 -- python gcj2020quald.py
です。
この記事に救われました。Round1以降も参考にします。
インタラクティブ問題は「厳密に着目する命令の実行回数を評価できる」といういい側面もあると思うのですが、なかなか慣れてないだけに難しいですね。
おわりに
ここまで読んでいただきありがとうございます。
今年は来年の雪辱を果たしてなんとかRound1突破を目指したいと思います。
