hogecoder

tsutaj 競技プログラミングの記録

ACPC 2018 参加記

勉強会参加記

会津大学プログラミング合宿 2018 に参加しました。ACPC は実は初参加です。

0 日目

JAG に行っていたので東京にいた。TIke さんと seica さんと ferin さんと olphe さんでボドゲカフェに行ってあそんだ。ワイナリーはワイン農家をやめた者が勝つゲームだった (いやプレイングが悪かったのもあると思うけど)

その後夕食を食べに行ったが seica ちゃんが限界をしていておもしろかった。夕食後解散になったが実は宿を取っておらず (は？) 東京駅近くで適当に発見したネカフェに泊まった。これがまた結構あたりを引いて、ネカフェなのに完全に個室だしコインランドリーはあるしシャワーも追加料金なしで使えてとてもよかった。次に東京行くときはまたお世話になります。

1 日目

東京からバスで会津に移動。会津に着いてバスから降りた瞬間 olphe さんと waku 君に遭遇したので一緒に会津大学まで歩く。けっこうあるくね

この日のチームはランダムに決めていただきました。pachicobue さん、tubuann さん、moritaoy さんと 4 人でチームを組みました。自分は C の篩書くやつと E の虚無 DP と B の戦犯を担当しました。(制約をよく読まずに、積分するみたいなミスリードをしてしまい多大な迷惑をおかけしました・・・)

解説聞いたら E は貪欲でも解けるらしいんですが貪欲が世界一苦手なのでしょうがないね。あと不可能が 2 〜 3 問あっておもしろかった

この日の懇親会は中止でしたが、宿が近い人たち 10 人くらいで集まって中華料理屋行って魔女ラーメンを食べてきた (魔女なので (いいえ))

2 日目

5 時間の会津セット、この日は事前にチームを組んでいて、drken さんと TIke さんと一緒に出ました。

自分は D を担当したんですが FA が取れなくてかなしいね。あと G は結構悩んだのですが場合分けすれば簡単に解けてしまい、場合分け力のなさをかんじた。あとは TIke さんとペアプロしたりしなかったり、一緒に考察したりしなかったりしてました。後ろの問題はほぼ drken さんが通していました (流石すぎる・・・)

†懇親会† ではお酒が無限に出るのでもちろんビールをたくさん飲んだんですが、体の許容量が有限だったので破滅しました。記念撮影から記憶が全くなくて気づいたら宿の和室で寝てました。ご迷惑をおかけしました・・・

3 日目

なんか普通におきられたので大学に行った。この日はコンテストの運営でした。やはりコンテスト開始 2 時間前に会場入りする作戦はかなり有効で、今回もちょうどよく準備を終わらせることができました。

特に大きなミスもなくコンテストが無事終わったので、とてもよかった！ (ただ、G が既出なのはすいませんでした・・・)

終わった後は TIke さんと ｼﾝﾔｶﾄｰ さんと Noimin さんとカラオケに行きました。みんな仕上がってた。次の機会までにまた練習しとくか〜

この日は引き続き会津に泊まることにしていて、まだ行ったことがなかった富士の湯に行った。あれは最高だったね、至急札幌にもつくってほしい

その後帰ろうとしたんですが道中にボウリング場を発見したので 2 時間投げてきてしまった、温泉の後にボウリングをすると汗をかくのでオススメしません (それはそう)

4 日目

適当に観光をした。

あとこの日の宿は郡山で取っていたので郡山まで移動した。爆睡しすぎて駅員に起こされた (もうしわけない)

宿に着いた後に CODE FESTIVAL 予選 A がありましたが、解ける数え上げがたくさん出たので通過した。いえい

5 日目

空港まで移動して、飛行機で新千歳へ。まだ新千歳空港のフードコードが復活していなくてかなしい・・・

そんなこんなで帰宅

作問について

気づいたら自分が作った問題がセットの半分以上を占めていました。RUPC で簡単めにしたらやたら解かれたのでちょっと難しくしましたがそれでもやたら解かれました。合宿のレベルがあがっているのを感じますね。

B 問題

北大の B 問題は難しい説、そろそろ定着しそう (ア

あるデータ構造で管理するとクエリ O(1) で処理できて嬉しいです。他にも想定解はあったのですが、クエリ平方分割は完全に想定外でした。

正直なんでこの問題が生えたのかよくわかってません。生えるときは生えるんですよね、作問って・・・

E 問題

5 秒くらいで適当に思いついた問題です。分かる人にとっては解法まで一本道でいけると思いますが、コーナーケースにひっかからないように気をつける必要があります。実際、コーナーで引っかかった人は多かったようです。

F 問題

最初思いついた問題文が解法を隠しきれていなくてアレだったので、頑張って問題設定を考えた結果こうなりました。それなりに隠せたのではないかと自負していますが、隠しすぎて想定解通りに通してくれた人がほとんどいませんでした (ア

G 問題

ありがちな問題設定なので事前にかぶっていないかどうかこちらでも調べていたのですが、どうやら既出だったようです。すみません・・・。 コンテスト中に beet さんからこの問題の解説記事の印刷クエリが飛んできてすべてを察した

元々は unique でない数え上げをさせるつもりでした。ちなみに unique でない場合についても、真面目にやれば O(|S|^2) で、若干手を抜いてデータ構造に頼っても O(|S|^{2} \log^{2} |S|) くらいになります。興味があれば考えてみてください。

総括

合宿は楽しみながら圧倒的成長できる最高コンテンツですね (再確認)

来年もいくぞー！！！