QualのWriteUp R1AのWriteUp R1BのWriteUp R1CのWriteUp R2のWriteUp 結果 0完をしてしまった．悲しいのであまり言及しません．また来年．
数学のみをしないで欲しい 読解 A: いきなり難しそうだけど… B: 全部に入れたら勝てないか C: 読めません． D: はい絶対難しい 重そうなセットに見えたのでABに絞る．
A: New Elements: Part 1 なにを勘違いしたのか，C or Jが無限に大きい場合のみを考えてしまった．なので答えが1か2になって当然WA．
B: Pottery Lottery とりあえず全部に100を入れたらめちゃくちゃ負けた．最小が複数あると干渉してダメなことにここで気付く． 透視に1ターンはかかり過ぎな気がするので投票に専念する． いくつかの花瓶を投票で潰して残りに100を入れた． 3個残しが190/250くらい出て，いけそう缶． 残ってる花瓶同士で干渉している？ 潰す花瓶が多いとあまり潰れないし，少ないと干渉するし難しい． とりあえず全部に100を入れておけば，干渉のみに気を使えて良さそう． 残りに傾斜が付くように投票するもむしろ下がる． 透視して最小を確認しても下がる． 最大風速で210/250ぐらい出た． 順位表を見るとやっぱり重いので，ひたすらパラメータをいじる． 最後までこれ． 明日からもおブスファッション 正直最初に目を通した時点で無理だと感じた．解いたことのないタイプの問題しかない．これは本当にプログラミングコンテストですか．
とはいえ上位はちゃんと通しているので完全に精進不足．R1Cの験を担いで直前にゲームをしてはいけなかった．
Humble Storeで無料配布中なのでぜひ．まだ途中．まあまあ面白いのだがメトロイドヴァニアの既プレイにOriとHollow Knightがあるので…
QualのWriteUp R1AのWriteUp R1BのWriteUp R1CのWriteUp R2のWriteUp 結果 AB2完60pt．414th．なんかstraightforwardでした．ゲームを直前までしてたのがよかったのかも．
A: Robot Programming Strategy 概略 手順のわかっているジャンケンマンがたくさんいるので，全員にワンコインで勝てる「対ジャンケンマンロボ」を作ろう．
雑感 今残っているジャンケンマン全部に，勝ちまたはあいこが出せればいい．実装ゲー．
今気付いたけど googol って $10^{100}$ じゃん．血の気が引いた．翻訳に投げたのをそのまま読んで10100を書いている．実際には1手で1台倒すはずだからこんなにループはいらないし，むしろ $A$ が大きかったらTLEだった．昨日のAGCもそうだが，よく嘘をついてしまう．
[展開する] B: Power Arrangers 概略 {A,B,C,D,E}の順列 $120$ セットが1列に並んでいる．はずだったが1セット抜けているらしい．何回かの質問でどのセットが抜けているかを特定しよう．
雑感 最初に各セットの先頭を質問すると候補が1/5に減って，残りの各セットの2番目を質問すると候補が1/4に減って…．これはAを解いてたら自然な流れだと思う．
そう思うからこそ，Largeの質問回数を計算してたまげる． $$ 150 \geq 148 = 119 + 23 + 5 + 1 = 119 + \left( \dfrac{120}{5} - 1 \right) + \left( \dfrac{24}{4} - 1 \right) + \left( \dfrac{6}{3} - 1 \right) $$
QualのWriteUp R1AのWriteUp R1BのWriteUp R1CのWriteUp R2のWriteUp 結果 Ac2完41pt．1815th．1811st．やっぱりちょっと上がりますね．Round1Cに進出．
A: Manhattan Crepe Cart 概略 より多くの人が向かう交差点の場所を特定しよう．
雑感 $(x,y)$ にいる人が $+x$ 方向を向いているなら交差点の候補は $(x’,y’) (x+1 \leq x’ \leq Q, 0 \leq y’ \leq Q)$
点の候補が $x,y$ について独立なので別々に求めることが出来る．集計はimos法が楽か．何故か配列を4つ用意してさらに添字ミスで1WA．
[展開する] B: Draupnir 概略 X-day ringはX日で倍に増える．$d$ 日目のリングの総数を質問できるので，0日目での各リングの数を求めよう．
雑感 $W = 2$ って何．Smallであれば連立1次方程式を解くだけでいいのでネットに実装を探しに行く．Python+ガウスの消去法が見つかったので慣れないながらもやる．手元では合ったのにWAした．辛い．
Editorialにあった実装．
[展開する] C: Fair Fight 概略 $$ \left| \max _ {l \leq i \leq r} {c[i]} - \max _ {l \leq j \leq r} {d[j]} \right| \leq K $$
QualのWriteUp R1AのWriteUp R1BのWriteUp R1CのWriteUp R2のWriteUp 結果 aC2完45pt．1500人通過で1584th1567th(何故か上がった)でした．まさかペナ差で落ちるとは…
A: Pylons 概略 $R\times C$のグリッドを後述するルールで動く駒がある．重複することなく全てのマスを踏めるならば，その動き方を示せ．
ルール 移動前の座標を $(r,c)$ ，移動後の座標を $(r’,c’)$ とする．以下のいずれにも該当してはいけない．
$r = r’$ $c = c’$ $r - c = r’ - c’$ $r + c = r’ + c’$ 雑感 全探索しかわからない．最初はSmallすらも落ちたが，1解に到達した時点で強制終了させたらなんとか通った．Largeはまったくわからない．桃色大戦ぱいろんは昔やってましたね．
[展開する] B: Golf Gophers 概略 風車の羽根の枚数を毎晩いじって，ゴルフ場に棲むGopherの数を推定しよう．
雑感 残り30分を切ったころに読み始めた．インタラクティブで絶望．この時点で2完なのでSmallだけでもとりたい気持ち．SmallはGopherの数が少ないので，雑でも行けると思って書き始めたがTLE．風車は回らず，Qualのツケが回ってきた．今考えれば中国剰余だなあという感じ．みんなのGOLFは4を昔やってましたね．
C: Alien Rhyme 概略 与えられた単語からrhymeできるもの同士をペアにしたとき，最大何組ペアが出来るか．ただし同じ位置でのrhymeはありえんライムなのでやってはいけません．
雑感 後ろから見て共通する部分で木を作った．これを「trie木」と言うらしい．深さが1進むと，その位置でrhymeするペアを1組作れるので，作れるペアの数を返り値で管理してDFSした．共通部分が長いとペアの数が単語数を超えるので，きちんとminを取らないといけない．substrしまくったので計算量が不安だったがなんとかLargeも通った．バイオ41は昔やってましたね．
[展開する] 感想 あとの2回で通る気がしません．繰り上げとか，なさらないんですか？
バイオ4空耳 完全版 — YouTube
[return]
QualのWriteUp R1AのWriteUp R1BのWriteUp R1CのWriteUp R2のWriteUp 結果 AB2完41ptで通過した．CDも解くつもりでいたが，Cで多倍長整数が必要なことに気付いてやる気を無くした．Round1以降に多倍長が出たらこの人はどうするつもりなのだろうか．
A: Foregone Solution 概略 正整数 $N$ が渡されるので $N=A+B$ となるように分割する．ただし $A,B$ は正整数で $4$ を含んではならない．
$N$ には1つ以上 $4$ が含まれる．
雑感 読みやすくて助かる．桁ごとに見て，$4$ を $2+2$ に分解すればよさそう．この出力形式誰が得するんだ．
[展開する] B: You Can Go Your Own Way 概略 正方形のグリッドを左上から右下に動く人がいる．この人と経路を共有しないように左上から右下に向かうにはどう動けばいいか．
雑感 即座に反転が思いついたがなぜか解法から外してしまった．まったく意味がわからない．結局場合分けをして解いた．結構重くなってしまった．
左上から出る向きと右下に入る向きが違うとき 図のように端を通る．
左上から出る向きと右下に入る向きが同じとき 鳩の巣原理から，同一方向に2連続で動くことがあるので，そこを狙って1回だけ交わる．図だと赤点を狙い撃ちしている．
[展開する] 感想 通過するだけなら意外と簡単だった．「Google Code Jam 2019 - Qualification Round通過 」って字面だけ見たら激強に見えるな．Googleすごい．実際に強いと言えるのはTシャツを貰ってからだと思っているので，そこまでは頑張りたい．調べたら残りの参加者は27610人らしい．1000/27610…