TSG LIVE! 3 day 2 ライブ競技プログラミング write up

TSG LIVE! 3 day 2 早朝プログラミング競技プログラミングに参加しました。

write upを書くぞ〜という気持ちで書きます write upってこういうのなんですか どっちかというと競技プログラミング系の不明瞭参加記のほうに近い

Day 1 - 開始直前

Google Code Jam Round 2 に出る 0完 冷えすぎる 風呂に入って寝る

起床 絶起やんけ 朝食を食べて向かう

到着 優秀なので集合時間に間に合う

地下着 わいわい 提出は1人しかしてはいけないらしいのでCoiL氏とざっくり分業の相談をする ← レギュレーション思ってたのと違ったっぽい(違ったっぽいので)

競技開始

開始して問題を読む とりあえずsubmissionするか!ということで縦にW回横にH回動くやつをする HとW逆だったらしいけどまあこのテストケースやったらうまくいってるしええやろ!w

提出すると1072点、意外と点数のスケールが小さいことがわかる(10:05:41)

アルゴ脳なので一瞬でDPが思いつく 実況で2行持つ全探索とか言われていた 違います

dp : vector<vector> として、dp[i][j][k] := i行j列まで来たときkが作れる <=> 1 とすると、dp[i][j] = (dp[i - 1][j] | dp[i][j - 1]) >> n[i][j] となるので計算量がO(HW Σn)程度 H,W <= 30, -6000 <= Σn <= 6000なので余裕でDPによる全探索が可能(bitsetで定数倍 /64も乗るし) 実行時間 10^-1 s オーダーくらいじゃないですかね 知らんけど なんで H,W <= 100じゃないんやろなあ〜(ヘラヘラ) いや実況でビジュアライザが点になるからって言われてたやんけ

これが大きいケースでうまくいくのはそれはそうで、例えば30x30の最短路は58 C 29 = 30067266499541040通りあって、値域が-6000から6000なのでさすがに-1,0,1のやつは存在することがとんでもなく期待される 10x10だと48620通りあって値域が-1000から1000なので 盤面がランダムなら中央付近の期待値爆上がりなので(正規分布に近似されていく)そこそこ期待できる 5x5だと70通りを-500から500 まあそれなりに 知らんけど

提出するとINF点 あれ???→左右間違えて盤外に出ていた 修正して提出すると71点 勝ったなガハハ!w(10:47:42)

CoiL氏が全探索が書けたらしいのでマージする しようと思ったらお互いグローバルに無限にものがあって困っちゃったのでnamespace CoiL{}とnamespace Naan{}で囲む 別にイキってnamespaceをつけたわけではないんじゃ

マージしたコードを投げると3x3がやばいスコアになっている これは乱数ガチャやろ〜と思って大量になげる

どうにもおかしい(最初の最短路全探索より悪いのしか出ない)ので全探索こわれてないかということになる 二人で修正にとりかかる 自分は一から書く時間とCoiL氏のコードを読み解く時間もなかったので手で全列挙をする おねえさんの問題を3x6まで全列挙した経験が生きる!!!!! 実際3列の場合はフロンティア法の状態がたかだか5個なので一瞬で列挙が可能 なので一瞬で列挙した

書いて投げる 57点でわいわい(11:11:32)

5x5も全列挙するか〜という気持ちになるけど8512通りは頭がこわれる上フロンティア法の状態が無限個あって禿げた もはやコード修正の時間はなさそう †偶然†持っていたまちカドまぞく(1-4巻,伊藤いづも,芳文社)をPCの前にお供えしていい乱数を引けるように祈祷して提出する 乱数乞いに成功して36点(11:17:05) 残り1分切ったし優勝では?→優勝

競技終了

優勝して気が大きくなる インタビューに答える LIVEのアーカイブを見ると想定した1/100倍くらいしか声が伝わっていなくておっぱげた

CoiL氏の功績があんまり実況側に伝わっていなさそうで悲しかった バグは入出力高速化の位置が原因でnaanがコードをマージするときに埋め込んだっぽい 申し訳なさすぎて申し訳のNASAofNASAになった そこ修正したら16点くらい出た これマジ? 反省した

駒場に+200点!実質グリフィンドール(ほんまか) いやーなんだかんだ言って実質アルゴみたいなアプローチができたので楽しかった 次の駒場祭ではもっと貢献していきてえなあ俺もなあ

いろいろ終了後

帰り道新ABCに出た なんとか全完した やったぜ。 アルゴ最高〜〜〜 次回のTSG LIVE! ライブ競技プログラミングはアルゴとマラソンの2回開催ってマジ? マジじゃないです

RUPC2019 参加記 Day 0 - 3

たのしかった

Day 0

寝ようと思ったら気がついたら起きていた こたつがめが滋賀に来た

↑これは名古屋だね

Day 1

歯医者に行く 敗北者…? 取り消せよ…! 最後に全力でフロスされて歯ァガタガタ言わされてしまった

到着してしまう こたつとエンカ!w

自己紹介フェーズでいづみちはるさんがこたつを名乗っていてウケた beetさんが「AtCoderのレーティングがたぶん会場で1位です」みたいなことを言っていて怖くなってしまう それ以外は忘れてしまった 悲しい

randomに組むか〜wと思っていたらなんとくじでbeetさんと当たる かてません

drogskolさん beetさんと組んでチーム名をrupc_ukuku09にする うっくっくwwwwwwえいえいえt(←いずらいt)

drogskolさんがABCを、beetさんと自分でDEFGを担当しようということになる

ここからコンテスト

Dを読むと構築なので担当したい気持ちになる

drogskolさんがABを通してくれている間にDとか構築インタラクティブやしにぶたんやろ〜とヘラヘラしながらbeetさんに無を持っていくと無であることを指摘される

無を有にするうちにAとBが通っているので有を実装すると通る ここまで32分くらい

drogskolさんが実験をして天才になってCを通していた beetさんが一瞬でEを通していた こわいなあ(50分)

その間にFとGを読んでGは苦手だなあ やめるか!wという気持ちになってFを考えておく 絶対値なので大小関係を考えるをすると大小関係の変動しない交換は意味がないことがわかる

beetさんにGが「燃やす埋める」っぽいと言われるが燃やす埋めるを解いたことがなく フローで解けるらしい くらいの理解しかなかったため相槌を打つオタクと化してしまう

同色罰金がうくだけど二部グラフなので頂点反転!wをしてもうまくいかない 終わってから聞いたんですが電球を頂点にすると破滅するらしい 悲しいね

悲しいのでFを考察する わからんわからんと言いながらa[i],i,a[j],jの大小関係実質12通りを書き下すと、a[i]とiの間 と a[j]とjの間 が重なっていないものはswapするべきで 得られるスコアは2つの区間の距離の2倍っぽいことがわかる

貪欲以外のアプローチが思いつかなかったので証明のない貪欲を書く monoidであることをbeetさんが気づくのでbeetさんのセグメント木ライブラリに乗せて殴る→サンプルは合うのにWA

適当に自明assertを入れることを提案するとREする えらかった がんばって直すと通る 159分

残り時間はGがわからず いやー燃やす埋めるに見えるけど 実はDPか?とか言っているとコンテストが終了していた

コンテストここまで

オンサイト1位と2位は組んでたチームだから実質1位!ガハハw まあ3位なんですが

D問題なかなか自分の実装がよさそうだったのでイキる やめようね! ビットごとにめっちゃ辺を張る実装もすこなんや

懇親会で渾身の懇親をする 実はほとんど知っていた人としか話してないね コミュ障なので

olpheくんとか自分とか「どうやったら競プロうまくなれますか」
beetさん「4000問解くと、実力が上がるので安定して、レートがこんなふうになることがなくなります(手を大きく上下させる)」
うしさん「?(机に寝ていた状態から起き上がる)」

↑これすき

懇親会後ゲーセン勢に合流してmaimaiをする いづみちはるさん音ゲーが上手すぎないか 帰ろうとしたら終電ギリギリアウトでこわれてしまった Day 1終了

終電に温情で乗せてもらったので勝ち

Day 2

へのkと不明瞭にいちゃつく けんちょん olphe ナン でrupc_olnanchonとしてチームを組んでおいた

わたてん9話を見た ノアちゃんがガチめいてきた 星野みやこに変身セットあたりで目覚めましたねクォレハ… まあひなたちゃん優しいからね、仕方ないね

問題数13問でおっぱげた

olpheくんがA ナンがB けんちょんさんがCをまず読んで残りはよしなにすることになる

ここからコンテスト

olpheくんがAを爆速で通す 1分

Bがシミュレーションに見えたのでシミュレーションを書いてしまう Sample 4を手元で実行して禿げる 算数をしないといけない気持ちになりけんちょんさんのCの実装を優先してもらう けんちょんさんがCを通す 14分

算数をしようと思ったところ算数が苦手だったので泣いてしまった 諦めて別の問題をすることを決意

けんちょんさんがGを考えていて逆型ゲームに誤読しているっぽかった(最後の1本を食べきった人の負け に見えていそうだった)ので誤読を指摘する Gが通る 27分

(ほとんど関わっていなかったけどFの考察がこのへんで進んでいたらしい)

ここからが本当の地獄!

olpheくんを尻目に面白そうなL問題を考える すぐに原始根→離散対数→gcd (575)では?と言う 実装をしてもらって投げるとTLEしてしまう だめであることに気づくのに無限時間かかってしまった

Bをolpheくんが通す プロ 堅実 114分

けんちょんさんがHを通す 昨日見た燃やす埋めるらしい なるほどなあ ところで問題を読んでいません

並行してolpheと二人でIを考える 考えていると天から「逆順に見なさい」という声が聞こえるので逆順に見るといいなあとなる

2q d + A (0 <= A < 2q)の形が適当に作れるので上端と下端を生やすと判定がすぐにできる

満たすAについて適当をするとサンプルが合う WAが出るんですが自明assertをするとREでおっぱげる オーバーフローなどを直すと通る 197分

Dが冷静になるとただのDPなので書く デバッグ出力こわれるから高さを小さくしていたらWAになって踊った AC 225分

Eをみんなで考える olpheが思いついた感じだったので書く 実はほとんど寝ていたのでJとLを考えるマンになってしまう

Jが区間スケジューリングっぽいというのは最初の方にolpheから聞いていたので物理パートの方針ガチャをするとn回目でいい感じになる 受験物理の経験が生きたな(確信) 放物線はy=ax(T-x)なのでここのaを出す v=(vx, vy)として出した式と比較してvをaで表す 最小は1/Tっぽい 45°だなあ 最高

Eが通ったのでけんちょんさんがLをほげしていくのと並行してJを実装する 手が止まったらもう片方が奪う感じで目まぐるしく実装する人が入れ替わっていた

Jの実装が完了するがSampleが合わねえ おわり とりあえず投げる 当然WAなんですが

コンテストここまで

おもむろにJのソートを逆順にすると通ってキレる

オンサイト7位 悪くはないんですが主観的冷えというものがあり Lも通したかったなあ 負けです

懇親会で渾身の食事をする 複数のよっぱらいが存在していて面白くなった これが†人生†や

懇親会の卓で500点以下の問題を作問して投げる遊びをする 自分も1問いい感じの300-400が生やせたのでヨシ beetさんが作問能力も高いことがわかりかてませんの意を強くした

懇親会後ゲーセンでmaimaiをする こたつがめとマッチング!w

帰ろうとしたら終電1本前でこわれてしまった Day 2終了

Day 3

こたつへのナンでチームを組むことにしていた

2人して絶起をする

3人して遅刻をする

会場へ向かう途中にbeetさんのツイートを見る

包除数え上げが出るのか〜(うく)

こたつが最遅だったのでチーム名をRUPC_Burningkotatsuにした こたつがめもやした

へのがA ナンがB こたつがCを読むことに

ここからコンテスト

へのkがAを通す rupc_H_E_N_T_A_Iに僅差で負けたらしい 悲しいね

自分がわからなくてこたつがCの方針が立ったらしいので実装してもらう

へのkにBの問題概要を伝えていたらこたつが読んでいたのがBであったことが発覚 何? まあBが一瞬で方針が立つのはこたつの異常能力な気がするのでそれが起きてよかった へのと一緒にCを読むとSampleがすべてを教えてくれるのでわかる どちらも通る 15分

Dをへのkが実装する そのうちにEFGを読もうとするがEは苦手なタイプの文字列なので無理だねとなる Fを読むと受験数学の勘がまず個数を固定しなさいと言ってくるので個数を固定する すると自明な包除の式が立つ(ここで脳内でbeetさんの方角を向いて礼拝した)ので綺麗にしたいなあとなってこたつに見せる するとこたつのおかげで冷静になってこのまま計算してもたかだかO(N2)じゃーんとなって終わる ホワイトボードを見るとhomu_aishiteruなる文字列がFの下に書かれていて泣いてしまった いや20分ってなんやねん

Dが通ったのでFを実装すると当然通る やったぜ。 39分→46分

その間にへのとこたつがEの考察を詰めていた Manacharとか使ったんじゃないかなあ しらんけど 線形とか回文とか言っていたけど結局ロリハで殴ったらしい なるほどなあ 待っていると通る 67分!!!!

悠々とGを考察し始めると思いつかなくて禿げる

いろいろなことを考える cycleの種類は上から見て1周するか1周しないかだなあとなる 1つ繋げるみたいなことを考え始める

Gに到達して30分ほどで27状態くらいを持つDPを思いつくが破滅なのでやめたくなる しかし重い腰をあげて実装に取りかかる(この頃には上下しながら1周するcycleの存在が頭から消えてしまっている)

地獄だなあと思いながら書く へのkとナンの2人で独立に書く←これはなに 二人ともSample 1は通るけど2が合わないね

へのkが上下しながら1周するcycleの存在を思い出して実装する 自分は忘れたまま悲しくなっていた

コンテストここまで

つらすぎて朝青龍になる まあオンサイト2位だし多少はね?

地獄DPを実装しきることができるタイプのベテランになりたいね 素直に反省です いや地獄DPが本質じゃなくて考察が抜けていたんですが

解説ののち解散になった

ボウリングまではついていくことに決めた

funcsr もやし先輩 くちもちとくらさん きゅうりさん Pulmnさんで昼食を食べに行く バスで駅まで行くが来た道を戻る

ちょうど15時くらいで飲食店が次々と閉まる 残った選択肢がすいていそうな得々うどんか混んでいるにぼ次郎でにぼ次郎を選んだ

にぼ三郎を頼んで完飲をした おいしかった オタク必ずしも完飲をしないことを学んだ

ボウリングに行った 申し込み用紙に「ナン」と書いたら名前を「ナニ」と間違えられて泣いた

きゅうりさんとくちもちとくらさんがお上手 funcsrとナンが無だった かなしいね

ボウリングから帰って参加記を書く ブログがなかったのではてなブログに登録する

とりあえず記事内で言及している人に読んでもらってから公開するお気持ちになる Day 3 終了

感想

楽しかった 問題が良質だった Day 2, 3の"あと一問"が解きたかった...(いやDay 2はほんまお前お前)

来年も申し込みTLEしない限り行こうと思います 他の大学オンサイトとかも行ければ行く いやよく考えたら遠いな 破滅してしまった

おまけ

去年の参加記書いてないね 長いイベントだなあ(詠嘆)