GCJ 2018
概要
- Google Code Jamに出ました
- Round2敗退
- 反省点等のメモ書きが多少
経過
- Practiceは何もわからず（存在忘れており）パス
- Qual Round (通過条件:25Pt)
- ABcD 80Pt / 100Pt
- #900 / 24584 通過
- Round1A (通過条件:\#1500以内)
- a 9Pt
- #3467 / 5172 敗退
- Round1B (通過条件:\#1500以内)
- A 25Pt
- #1158 / 4811 通過
- Round1C (通過条件:\#1500以内)
- 不参加（Bで通過している為）
- Round2 (通過条件:\#1000以内)
- AB 41Pt
- #1208 敗退
詳細
以下テストケース数はTとしておきます
印象に残った問題を載せていきます
全部はめんどい…
Qual Round
Go Gopher!
インタラクティブ問題
問題文
のグリッドがあり、１マスずつ座標を指定して(i,j)として渡すと
[i-1,i+1][j-1,j+1]のマスを塗ったという報告が返ってくる（９マスは等確率で選ばれる）
入力として与えられるAマスを超える長方形を1000回以内に塗りつぶせ
制約
small:
large:
考察
同じマスを指定し続けると3*3の９マスを埋めるのに期待値上２５.4回ほどかかる
3 * (3 * k) >= Aとなるようにひたすら３マスずつ指定するマスを動かすと
A = 200の場合 207 = 23 * 9より 23 * 25.4 = 586回ほどで期待値的には終わる
…が、乱数酷いと永遠に終わらないわけでSubmit繰り返せという辺りがなかなか
確かに何回もWAになることはないんだろうけども
Cubic UFO
(0,0,0)に中心を持つ各辺１,xy,yz,xz平面に平行な面を持つ立方体に回転行列をかけてz = -1平面への射影の面積を入力の値S通りにしなさい
制約
small:
large:
考察
とりあえずx軸からz軸の方向に45°傾けるとちょうど面積がになってそこからいくらかy軸からz軸の方向に傾けると面積が
になる角が存在しそう（実際存在する）
ということでsmallケースとlargeケースで場合分け
いずれも角度を二分探索
十分高速に動作して終了
ちなみに立方体ABCD-EFGHのz平面への射影が極大になるのは正三角形AC(F,G)がz平面に水平になる角なんだとか
Round1B
Rounding Error
問題
分数を％にする
このとき小数点を四捨五入すると元の分数の和が１にも関わらず和が100%にならない場合がある
ex: 1/6 + 1/6 + 1/6 + 1/6 + 1/6 + 1/6 = 17% * 6 = 102%
アンケートがあり、回答を集計中で、回答者はN人、集計済みがK人おり、K人をそれぞれ数列Aに分けてある
残りのN-K人によって最大で分数を％にした時の和が何％になるかを出力せよ
ex: N=6, K=4, A={3,1}の場合{3,1,1,1}や{4,1,1}の場合に101%
制約
, 10sec
large:
[tex: K
Round2
Graceful Chainsaw Jugglers
問題
ピエロにチェーンソーを持たせてパフォーマンスをさせる
チェーンソーは2色ありR,Bとして各色のチェーンソーの数が与えられる
ピエロはそれぞれ違う数の組み合わせのチェーンソーを持たせられる
最大で何人同時にピエロにパフォーマンスさせられるか
ex: R = 4, B = 5の場合
(R,B) = (0,1)(0,3)(1,0)(2,0)(1,1)の5人のピエロが同時にパフォーマンス出来る これが最大（他にも最大の答えはある）
制約
, 25sec
large:
考察
前処理DPをすれば1テストケースに対してO(1)で回答できるのでギリギリO(RBRB)の愚直DPが通りそう
dp[R][B]として
もたせうる(i,j)組み合わせ全てに対して
dp[R+i][B+j] = max(dp[R+i][B+j],dp[R][B]+1)とする
前進するとダブるので後退更新すればO(RBRB)
愚直に実装するとTLEで、R
Costume Change
問題
N*N人が正方形に並んでいる
服の種類が-N,...,-1,1,...,Nあり、同じ列と同じ行に同じ服がいないようにしたい
元の服の種類が行列で与えられるので最小の服変更人数を出力せよ
考察
できなかった
貪欲は通らず
解説で種類ごとに行と列の二部グラフを作り、最大独立集合の要素数をN*Nから引いたのが答えと知って唖然
フローに対する典型力が足りませんでした
