パ研合宿2021 参加記
はじめに
パソコン力を高めるの会主催のパ研合宿2021(これ正しいのか未だに分かってない)に参加してきました！
これまではPakenとKCLCの共同運営という形を取っていたため、KCLC内募集で参加できていましたが、今年は 私が運営募集に気付かなかったため KCLC部員には外部枠で申し込んでもらうことになってしまいました。すまん！
昨年度と比べイベント量が倍になり、宿泊もできたので大満足でした。実質運営長の oliver さんありがとう...
参加記ということで時系列順に色々書いていきます
2021年11月
部員から今年のパ研合宿はどうなる的な質問を貰ったのでパ研の人々のツイートを見てみたところ、議論が死んでるという旨の話があったため若干心配になりました。
2022年2月
パ研公式から外部参加者募集のツイートがされたため、そういえば運営って募集されてた？と思い Discord を漁っているとこんなものを発見しました。時すでに遅し
1日目
起床に成功 やったね
南武線を使って分倍河原まで行き、そこで昼食(マック)を取ろうとしたところ、なんと昼マックは 10:30 からとのこと。仕方がないので駅周辺を散策していたら高倉塚古墳という古墳を発見したのでそこまで行ってきました。
無事昼食を取り終え北野に向かうと、おすみーくんが既に到着し待機していました。
運営陣っぽい人々が揃ったところで、その時に居た 10 人程でバスに乗りセミナーハウスへ向かいました(クソデカスーツケース×10, 軽くテロだったと思います)。
野猿峠からセミナーハウスへ向かう最中、kaage さんが「この辺の景色よく見ておいた方が良いよ」的なことを言っていました。Freedom, 一体何が起こるんだ…
UTPC
zeta7532, to_omoT222, SotaUN, nasubi24, soraie の 5 人でチーム「チーム名ver.2.0(最終版).xlsx(自動回復済み) 」を組み参加しました(深夜テンションで提案した名前が採用されてしまった...)
E,I,J,M を頑張って考察していましたが、結局通せたのは M のみでした(zeta くんの (1-q) を掛けるという発想が無ければ解けてなかった)。高難易度力が、足りない！
夕食
昨年の記憶を頼りに同部屋の AndrewK くんと NatsubiSogan くんを探し出します。人の顔、覚えられん！
ご飯美味しかったです。欲を言えばもうちょっと量が欲しかった
開会式
あのビ太郎の素材、どこにあるんだ...
私はここで運営長がぺんぎんさんだということを知りました。
講義1
E8 さんの講義を聞きました。双子スライド、情報がスッと入ってくる感じがしてすごい あのデザイン何処で身につけたんでしょうか
同じスライドをツイートしたらしいので後日 Twitter を見たら 2000 いいね取っててびっくりしました。E8 さん、そういえば凄い人だったな... になりました
夜
スーツケース開く場所、どこ
一人人数の関係で移動していたので、端のベッドの前を使いました。これ想定何だろう
はいらが「他の部屋員みんな作業してる～」とやってきました。かわいかった
どうやら 211, もとい最悪部屋は大盛況だったらしいですね 一日くらい混ざっとけば良かったになってます
2日目
朝
無事 7:00 に起床できました 偉すぎ
朝食はバイキングでした。大体のものを一人分くらい取っていたら腹がはち切れそうになりました。普段朝食を適当に済ませているとこういうことになるんですね。
Speedrun
パ研合宿1つ目の競技 Speedrun に参加しました。ABC の早解きパートは割と得意な方だったので最も自信があったのですが...
J の DP を死ぬほどバグらせた上に、K で括弧列を木にしたいnaanから進展がなかったため、9 完 2500 点・全体 35 位・オンサイト内 17 位という結果に終わりました。悲しい
Freedom
Freedom, 所謂お誕生日コンテストです。コンテストの前から Writer 陣よりとてもコンテストとは思えない発言・注意事項の数々が飛び交っていましたが、蓋を開けてみるとそこには想像以上に Freedom な問題群がありました。
【オンサイト問題】マラソン問題（物理）... 一回やりました。セミナーハウス、アップダウンがすごいですね
kaAngea 2・同校angya ... 知識で解けるものしか分かりませんでした。解説で右クリックすると Google レンズで検索できることを初めて知りました。
ビンゴで遊ぼっ！... 1 ライン BINGO 講師陣が 180 取ってたので良い攻略法があるのかと思いきや正攻法でした すごい
宿題と魔法少女 ... 小一の学習指導要領を調べたのはこれが初めてです。
絵しりとり ... インダス文明、反則です
字短ゲーム・くそなぞなぞ2022 ... 天才パズル、むずい！
コスパ ... "C コードゴルフ" で色々調べましたがたどり着かず
Simple A⋛B Problem ... 問題の本質に終了 5 分前に気付きました
スーパー猫の日 ... 17:32 に鳴り響く複数のアラーム それアリなのか...
逆翻訳・Obsolete-ESP・奇数優位 ... 理不尽を問題にしたらこうなるんですね
Obsolete-Empty ... 画像のプロパティ、典型らしいですね すごい
お誕生日コンテスト典型 90, 待ってます
講義2
noimi さんによる彩色多項式の講義でした。彩色数の話辺りまではついていけていましたが、NBC が出てきた辺りから頭が爆発してしまった...
一見非自明な変換が成立するの、理解できたらおもしろそうでした。
ゆっくり見返そうと思います。
夜
某プリンセスがコネクトしてリダイブするアニメの最終話を見てました。 いい最終回だった
3日目
朝
アラームかけてちゃんと 7:00 に起きられたのに何故か二度寝して 7:50 に起床しました。絶起したかと思い食堂に向かうとまだ参加者の半分も居ませんでした。競プロerは朝に弱い
2日目の反省を活かし、サラダの量を減らしコーンフレークを付けたところ、またまた腹がはち切れそうになりました。(腹の中で膨らむ食べ物の代名詞のようなものなので、それはそう)
レク
コンテスト開始の午前九時、周りを見渡してもチームメイトがいません。Discord でメッセージを送りステータスを確認するとオフラインだったため、仕方なく1人コーディングを開始します。
レクのために用意されたオンラインジャッジ上で他チームと殴り合いました。ジャッジや対戦の即時ビジュアライズができるジャッジを 2 週間で作れるの、凄すぎ...？になりました。開発力を高めるの会
私のチームは「自機・敵機とリンゴの位置で適当な評価関数を作り、可能な手のうち最も良いものを選ぶ」という手法を取りました。改善されたことを確信して投げると反復横跳びしかしない AI が爆誕するということを 10 回ほどやらかしましたが、何とかまともに対戦できるものが完成。
最終的に全体 10/22 位 まで順位を上げることができました。
ジャッジの裏をつくことに成功したチームが優勝してたのはおもしろポイントでした。Freedom 2日目
そしてどうやらチームメイト含む約3名は12時前に起きたようです。良質な睡眠、大事。
講義3
3日目の講義は square さんによるランダムに関する講義でした。
競プロでランダムというと、ヒューリスティックコンテストで焼きなまし山登りエトセトラをやるとき か、アルゴでテストケースが弱いことを願って乱択を書くとき などが思いつきますが、アルゴでもまともな使い方が存在したんですね。双子節(？)もおもしろかったです。
パ研杯
遂にメインイベントです。今年も大量の部分点とマラソンがあるとのことで、楽しみにしていました。
配点が 5 分前だか 10 分前だかに公開された (1-3-5-6-7-8-8-8) ので、ある程度ムーブを固めておきました。(6 まで頑張る＆部分点取りに行く)
ここからは経過時間毎に
0:01 A問題 AC (100点)
何処かに実際の講師陣のスケジュールが存在しているかと思いましたが存在していませんでしたね。
0:04 B 問題 AC (400点)
面倒くさかったので X Y 両方試す&にぶたんで解きました。
0:15 C 問題 小課題 1 (500点)
よくあるループの検出っぽかったのでいい感じに下 m 桁を表現できるものを探すと mod 10m があったのでこれで実装。小課題 3 が賢いことできないと解けなさそうだったので、とりあえず小課題 2 まで通そうとしましたが何故か WA を貰いました。悲しい
沼りそうだったので一旦パスします。
0:32 D 問題 小課題 1 (550点)
数分考察してみましたがサッパリだったので、とりあえず自明な小課題 1 を通しました。
0:53 E 問題 WA&TLE (550点)
小課題 1 を色々乗せたセグ木上のにぶたんで解こうとしましたが、定数倍が重かった上に log の 2 乗が掛かってしまい TLE。しかも想定していない WA までついてきました。とりあえずパス。
1:04 C 問題 AC (950点)
試しに m=16 でループ長を調べてみたところ、愚直が余裕で間に合うことが分かりました(最初から実験を、しよう！)。これを実装し、見事 AC 。
1:26 D 問題 AC (1500点)
先程ちょっと考察してサッパリだったため、一手ずつ考察を進めていきました。具体的には、「十中八九 DP なので、どういう状態だったら嬉しいか・どういった配列・条件・遷移だったら正しく求められるか」を考えました。
すると、
- B で昇順ソート
- dp1[i] = (選んだ B_i の和) = i のときの、(選んだ B_i の和) - (選んだ A_i の和) の最大値 (0 <= i <= T)
dp2[i] = (選んだ B_i の和) > T , (選んだ A_i の和) = i のときの 、(A が解いた問題数) - (B が解いた問題数) (0 <= i <= T)
となるような、配列 dp1, dp2 を定める - いい感じに遷移すると、dp2 の最大値が答え
という解法を思いつきました。
これを実装し投げると、見事 AC 。
ここまで綺麗に考察でき正解に辿り着ける問題は初めてでした。今回の問題の中で一番好きです。(運営陣によるとこの原案が出たのは数日前だったらしい ギリギリ)
1:35 F 問題 小課題 1 (1520点)
小課題 2 以降は何も分からなかったので自明な 1 を投げました。
この後また E に粘着しますが、小課題 3 でセグ木を 4 本作る案など訳の分からないものが出てきたのでまたもやパス。
2:17 G 問題 小課題 2 (1670点)
開始 2 時間くらいまでずっと頂点を 1 度ずつ通るだと思っていました。なんで？("巡回セールスマン 補題" とかで調べたりしてました)
辺を 1 度ずつに読み換えると、小課題 2 が自明だと分かります。
Python の defaultdict を使って通しました。
2:45 G 問題 小課題 1&2 (1870点)
小課題 1 では二乗が許容されているため、各 (l, r) について O(log N) 程度で判定ができれば良いということになります。
各頂点の次数が全て偶数なら条件を満たしそうなので、hash でその時点において次数が奇数である頂点の集合を管理してみます。サンプルを試してみると 3 で落ちたのでよく見てみると、連結でないときに壊れるようです。
そこで UF で連結判定をして提出してみると、小課題 2 で 1 ケースだけ爆発しているケースがあったため、小課題毎の条件分岐を逆にして回避し通しました。
E に戻って考察していましたが、進展はなくコンテストは終了。
結果
100-300-500-600-0-20-350-0 の 1870 点で全体 28 位・オンサイト内 11 位でした。
高難易度力はそこまで自信がなかったので予想以上に取れて嬉しかったです。
Deathgame
運営が Deathgame などといった迷言も生まれたこのコンテストですが、私は R2 敗退という結果でした。R2-B でロリハをバグらせたのが敗因です。悔しい～
双子が R3 唯二(？) の AC を取ってました。すごい。
夜
最終夜だしワイワイやりたい！今後あんまり出ないだろうしオンサイト SRM もやりたい！などと思っていたのですが...
寝落ちしました...(悲しい！)
4日目
朝
今日はちゃんと 7:00 に起きました。寝落ち効果
昨晩寝落ちして入れなかったので朝風呂に入りました。八王子の朝寒すぎませんか
運営は二日連続絶起したらしいですね。 お疲れ様です。
やることもないので講堂でのんびりしていました。
講義 4
tatyam さんによる木の色々の講義でした。
直径からそれ以外を垂らすっていう発想、今までしたことがありませんでした。これ使えば格段に解きやすくなる問題かなりありそう
それと HLD もそろそろライブラリ化しなきゃなぁ... になりました。
講義前か後か忘れましたが、tatyam さんが IOI2018 で作られた IA ちゃんのクリアファイルを配ってました。はじめ IA ちゃんのことを IOI のキャラクターか何か(JOI のビ太郎のような)だと思っていたのですが、あのボーカロイドの IA ちゃんでした。どうやら IOI2018 を日本でやった時に IA×ONE のライブがあったらしいですね。 すごい
LT大会
数学や開発やFreedomやIOIの様々な話を聞けました。よく使われる単語攻撃、賢い。
スライド無し LT をしていた人が数人いましたが、彼らみたいな話を組み立てる能力、欲しい～と思いながら聞いてました。
閉会式
パ研杯銀賞(オンサイト内 6~12 位)を頂きました。嬉しい～
この後新宿方面に遊びに行ったグループがあったらしいですが、私は体力の限界を迎え家に直行していました。翌日息絶える覚悟で遊びに行けば良かったですね。
おわりに
4 日間あっという間でした。楽しい時間は早く過ぎると言いますが、まさにその通り
来年は恐らく運営として参加すると思います。KCLC枠復活させたいし
原案も余るほど考えときます。原案の数だけ日数増えたりしないかな～
最後に...
oliver さんをはじめとした運営陣の方々ありがとうございました！！！
楽しかったです！！
