Google Code Jam 2019 Qualification Round に参加したよ
GCJ予選に参加してきました。AB満点で41点でした。予選通過です。
GCJ予選のルール
- 全4問。
- それぞれの問題はいくつかの小課題に分かれている。
- それぞれの小課題には「点数」「Visible か Hidden か」が決まっている。
- Visible: 採点結果がコンテスト中に通知される
- Hidden: 採点結果はコンテスト中に通知されない
- 100点中30点をとれば予選通過。
- コンテストは27時間開催される。
問題
ネタバレ防止のため、最初に全ての問題文を載せてからAとBの解法を載せます。
A - Foregone Solution
問題文(意訳)
以下の問題がT個与えられるので、全て答えよ。
1つ以上の桁に4を含む自然数Nが与えられる(例: N=4, 434, 4444)。どの桁にも4を含まない自然数の組(A, B)の中で、
N==A+Bを満たす物の1つを答えよ。
サンプル
- N=4のとき、(A, B)=(1, 3)
- N=434のとき、(A, B)=(232, 202)
制約
全テストセット
1<=T<=100- 実行時間制限: 10 sec
- メモリ制限: 1 GB
Test set 1 (Visible, 6 pts)
1<N<10^5
Test set 2 (Visible, 10 pts)
1<N<10^9
Test set 3 (Hidden, 1 pt)
1<N<10^100
B - You Can Go Your Own Way
問題文(意訳)
以下の問題がT個与えられるので、全て答えよ。
南北方向Nマス、東西方向Nマスで構成された平面がある。
はじめに、Lydiaが南への移動と東への移動を繰り返して、北西の角のマスから南東の角のマスまで動いた。あなたは、Lydiaの移動方法と1度も重ならないようにして、同じように南への移動と東への移動を繰り返し、北西の角のマスから南東の角のマスまで動きたい。具体的には、
Lydiaの移動ルートに「マスAから隣接するマスBへの移動」が含まれるとき、あなたは「マスAから隣接するマスBへの移動」をすることはできない。しかし、あなたは「マスAから隣接するマスCへの移動」をすることはできる。
平面のサイズN、Lydiaの移動ルートを表す文字列P(南への移動は
S、東への移動はEで表される)が与えられるので、あなたの移動ルートを表す文字列yを1つ答えよ。
サンプル
GCJ公式の図を参照(Lydiaは青、あなたのルートはオレンジです)。
このとき、N=5, L=“EESSSESE”, y=“SEEESSES”である。
制約
全テストセット
1<=T<=100- 実行時間制限: 15 sec
- メモリ制限: 1 GB
- Lydiaが北西の角のマスから南東の角のマスまで動くことは保証される。すなわち、Pには文字
SがN-1個、文字EがN-1個含まれる。
Test set 1 (Visible, 5 pts)
2<=N<=10
Test set 2 (Visible, 9 pts)
2<=N<=1000
Test set 3 (Hidden, 10 pts)
- 最大10個のテストケースで
2<=N<=50000 - それ以外のテストケースで
2<=N<=10000
C - Cryptopangrams
問題文(意訳)
以下の問題がT個与えられるので、全て答えよ。
pangramと呼ばれる、26種のアルファベット全てを少なくとも1回用いて作られた特殊な文字列がある(例: “the quick brown fox jumps over the lazy dog”)。あるpangramを、以下の手順で数列として暗号化した。
- Nを決める。
- N以下の素数を26個決める。
- 26個の素数を昇順にソートする。
- 最小の素数に
A、次の素数にB、...最大の素数にZを割り当てる。- pangramを用意し、文字を全て大文字にして、空白を削除する。これを平文とする。
- 手順4で構成した文字と素数の対応に従って、平文を数列に変換する。便宜上、この数列を
p[]とする。- 暗号数列
c[]を、c[i]=p[i]*p[i+1]を満たすようにして構築する。c[]が暗号化されたpangramの数列である。要素の個数はLである。N, Lと、L個の暗号数列の要素が与えられるので、暗号数列を復号し、もとのpangramを出力せよ。
サンプル
例としてGCJを暗号化する(注: この文字列はpangramではない)。
'C'→5, 'G'→17, 'J'→29 と対応している場合、
p[0]==17, p[1]==5, p[2]==29
であり、
c[0]==17*5==85, c[1]==5*29==145
である。
制約
全テストセット
1<=T<=100- 実行時間制限: 20 sec
- メモリ制限: 1 GB
25<=L<=100- 復号するとpangramになることが保証されている
Test set 1 (Visible, 10 pts)
101<=N<=10000
Test set 2 (Hidden, 15 pts)
101<=N<=10^100
D - Dat Bae
問題文(意訳)
以下の問題がT個与えられるので、全て答えよ。
これはインタラクティブ問題である。
ID 0,ID 1,...ID N-1 を与えられたコンピュータがN台ある。これらのコンピュータにN桁のビット列を与えると、戻り値として、与えたビット列と同じN桁のビット列が返ってくる。
しかし、B台のコンピュータが壊れてしまったため、戻り値がN-B桁しか返ってこない。この戻り値は、与えられたビット列から、壊れたコンピュータのIDに対応する桁を削除したものである。具体的には、
N=5, B=2, ID 0とID 3 のコンピュータが壊れているとき、
01101を与えると111が返ってくる00110を与えると010が返ってくる01010を与えると100が返ってくる11010を与えると100が返ってくるあなたは、コンピュータに対してN桁のビット列を最大F回送信することにより、どのコンピュータが壊れているかを調べたい。
はじめに、整数N, B, Fが与えられる。その後、あなたは、コンピュータに対して、次のクエリを最大F回送ることができる。
- N桁のビット列を送信する。不正な入力である場合は
-1が与えられる。そうでなければ、N-B桁のビット列で構成された戻り値が与えられる。また、どのコンピュータが壊れているかわかった場合、次のクエリを1回だけ送ることができる。
- 壊れているコンピュータのIDを、空白区切りでB個送信する。間違っている場合は
-1が与えられる。正解している場合は1が与えられ、次のテストケースのジャッジが始まる(もしくはACになる)。
制約
全テストセット
1<=T<=100- 実行時間制限: 20 sec
- メモリ制限: 1 GB
2<=N<=10241<=B<=min(15, N-1)
Test set 1 (Visible, 14 pts)
F==10
Test set 2 (Hidden, 20 pts)
F==5
解法
A - Foregone Solution
Test set 1
方針
O(N)が間に合うので、A=i, B=N-iとして全探索すればよい。
数nを1桁ごとにstd::vectorの要素として追加するライブラリがあれば、4が使われているかの判定はすぐにできる。なかったら作る。
AtCoder基準の体感難易度
ライブラリがあれば200点
Test set 2
例としてN=434を考える。
各桁に4または0以外の数が出現しない自然数Sと、各桁に4が出現しない自然数Tのうち、N==S+Tを満たすような組を求める(この場合、S=404, T=30。この組はNを一桁ずつ確認することで求められる)。
そして、A=S/2+T, B=S/2にすれば良い。なぜならば、
- 明らかに
A+B==Nである - Bの各桁は2か0のいずれかである
- S/2の各桁は2か0のいずれかであり、Tを足したときに桁の繰り上がりは発生しない
からである。
これによりO(Nの桁数)で求められる。
AtCoder基準の体感難易度
300点上位〜400点下位
Test set 3
Test set 2 の操作は、N,A,Bを文字列として考えたときに、
- N中のそれぞれの文字cに対して
c=='4'ならA+='2' , B+='2'c!='4'ならA+=c , B+='0'
- Bの最初の方で連続している無駄な
0を削除する
という操作をすることと等しい。
文字列化することでオーバーフローの心配がなくなった。
AtCoder基準の体感難易度
300点上位〜400点下位 実装はset 2 よりも楽
B - You Can Go Your Own Way
Test set 1, 2
略。3を解きに行ったほうがわかりやすいので
Test set 3
方針
Lydiaが南に動いたら自分は東に、Lydiaが東に動いたら自分は南に動けば良い。
こうすることで二人の移動ルートが「北西の角と南東の角を結んだ対角線に対して対称」になる。ルートが直交することはあっても重なることはないのでAC。O(N)。
AtCoder基準の体感難易度
300点。体感ではAより楽
C - Cryptopangrams
解けてないです ごめんなさい
Test set 1 は素数列挙してゴリ押し因数分解するだけなはずなんだけどなぁ…
D - Dat Bae
あまり考えてないです ごめんなさい
二分探索をうまく使えば解けそうな気がしました
