b_JAG夏合宿2024 参加記

初めに

セキュリティ・キャンプ全国大会の参加記は？→12月に出します (自分で決めた)締め切りを破ってすみません...

追記: 卒論激ヤバで出せる気がしません すみません

Spinning-akabeko(Abeshi2002, zawatin, CleyL)で参加。

私は電波を受け取りながら考察する役割を担っています。

JAG夏合宿

ICPC Asia Regionalの模擬を実ジャッジ環境使って回してくれるイベント

他二人(Abeshi2002, zawatin)は去年にチームLuzhiledFunClubで参加していた(はず)で、私だけ初めての参加

Day1

過去のICPCの過去問セット

分担してみた感じHがよくある形すぎるのでそのまま実装。片方を軸にいい感じにソートして、もう片方の値をFenwick Tree2つ持って計算するだけ

実装奪ったタイミングで気付いたが、C++触るのが国内予選以来だったので約3ヶ月ぶり

サンプルが一致したので提出するがWA。案の定実装バグらせた

ペアプロしてなんとかバグ部分を見つけたが、非本質過ぎて本当に辛かった

Kを渡されたので考察。一生Dilworth言ってた気がする

zawatinがE解けたので実装に移ってもらう

zawa「分散って割り算使う?」

CleyL「多分使う(適当)」

数分後

zawa「サンプルが合わない」

CleyL「大きい？小さい？」

zawa「小さい」

CleyL「じゃあ分散の部分で割らないとどうなる？」

zawa「サンプル一致した」

CleyL「草」

あとから問題文を見返したらちゃんとその部分の式が書いてあった(もちろん割ってなかった) ごめんなさい

Kが隣接リストの要領でシミュレーションできるとAbeshiが言ったので、考察確認して問題ないことを確認。そのまま実装

Aこれ絶対LCにある 私はissueを追ってた でも考察知らん状態になってた

部分問題はMergeSortTreeで解けるんですねーって教えてもらって、MergeSortTreeを知らなかったので教えてもらう。その方向性で考察していたが、どう考えても要素が多すぎて終わりだろみたいな気分

Kが通ったのでとりあえずAの実装してもらう abeshiと一緒にBの考察

円の3/4の中にある点の個数はそのまま計算できる(計算できるという事実はAbeshiが理解しているので聞かなかった)

のこりは四角形で邪魔されている部分だが、適当に書くと小さい扇型が作れる場合と、マジでよくわからない異常図形が作られる場合に場合分け出来る。異常図形を説明するのに時間がかかった(軸が変わっているから円にはならないことの共有を忘れていた)ところは反省。

異常図形の中に含まれる点の個数も求められるということを聞いたのでそのまま実装に移ってもらう。間に合わずタイムアップ。

終了後:

同室の人にハイパーロボットを布教する悪い大人になっていた。

談話室でボドゲをやった。

周りの人が強いし盛り上げ上手だったから手加減とか何も考えず遊べた。久しぶりにゲームは楽しいものであると感じた気がする。

Day2

有志セット この日から手書きスプレットシートを用意して誰がどの問題を認知しているかの共有を出来るようにした。

他のチームの人達がぬいぐるみとかマスコットを用意していて、アイコンじゃなくてリアルに存在するものなんだという気持ちになっていた。

スタートのタイミングでA-Dを読む。

Aがあまりにも典型の(私は即解けないけどzawatinなら即解いてくれるという信頼がある)問題だったので解いてもらう。解いてくれたので結果オーライ。

Bを見ていると普通に遅延セグ木で解けるのでは？という適当考察が浮かぶ。

Cは明らかにAGCの1000点以上の問題みたいな形をしていたので避ける。Dは解けそうじゃない？って思ったので説明をするが、何も考察浮かばないのでそのまま放置。

Aが通ったのでzawatinにBの説明をする。 結果的に私の解法は嘘だったが、別ルートでちゃんと解いてくれた 私の存在意義消えてない？

Bを渡す代わりにGを渡される こういう問題苦手なんだが？って主張したけどこのチームで多分一番出来るので大人しく見る。

Abeshiと考えながら適当な考察が浮かんで、Bが通ったのでGを書く WA

適当に実装問題を交代しながらWAの原因調べてると、普通にAbeshiの言っていた主張を実装できていないことが発覚 考察自体はあっていた。一から書き直してAC。

abeshiとKについて考察する。L/x以上R/x以下の値はL以上R以下のどれかの値を割ることが出来るという一般的な主張だけして、O(K)で解けますねーって言ってたらクエリ問題だった そっから何も言ってないんだけど平方分割で解けるって言ってくれたのでそのままGoする。ACしたので良し。

Mの考察に移ったら普通にギャグ問題(捻ると解ける問題の意)であることに気付く。一番大きい値だけ選ぶのは反例があることもきちんと証明できたし、3番目に大きい値をでかい要素として選んでも最大値は叩き出せないという証明までできたのでかなり理想的に解けた。

zawatinに2番目に大きい値/ある値を持たないgcdを持てるSegment Treeって作れる？って聞いたら作れるって返ってきたのでそのまま実装してもらう。アルゴリズムやデータ構造をブラックボックスとして扱って考察するとかなり頭を回しやすいが、諸刃の剣であることも事実(zawatin、Abeshiが居ないと成り立たない)。いつもありがとうございます

考察部分の一番大きいコーナーケースを出した割に全部同じ値が入るケースを失念してた。 諸刃の剣が壊れた例

zawatinに実装してもらう間にFの考察の手伝い。Abeshiの考察がなんとなく正しそうなのと問題自体をあまり理解できていなかったためそのまま一人で考察回してもらったほうが良さそうと判断。とりあえずぬいぐるみの代わりをした。

ぬいぐるみになりながらIを見る。これ確かClarで無向グラフって説明が出てたよなと思い出しながら、とりあえずどんなルートを通ってコストがちゃんと平方数になるようになるかを考える。

Mが通ったので、Iに対して明らかに二部グラフみたいに頂点集合を分離させると嬉しいので頂点を集合にしていい感じに分離できなかったら0、いい感じに分離できたらその集合の計算値が答えみたいな主張をしたら理解できない目をされる。

このいい感じの説明にかなり手間取る。フローの最小カットとかグラフの分割だよなーって言いながらそこら辺の用語を適当に扱っていると更に混乱させてしまう。 それはそうなので本当に反省

30分位会話して私の考察の70%程度が伝わったのと、その理解でも問題自体は解ける状態になってるように見えたのでそのまま実装してもらう。

結果サンプルは揃った。コーナーケースを全く考えてない激ヤバ実装ではー？って思ってたら普通にACした。多分コーナーケースなかったんだと思う。

これ以上は時間を考慮して解けなさそうなので終了。

この集団の中で6位は流石にびっくりしたけど、よくよく考えると私のレートが一番低いので、私基準でチームの基準を測るのはやめようという気分になった。

まあ多分このセットだったらSkyblaze(今年度の弊学最強チーム)にも勝てそう

終了後:

懇親会は不参加。体力が保たなそうだなーと思ったので不参加にチェックしたが、意外とそんなことはなかった。(その代わり終了後にどっと疲れが来る)

洗濯で800円失って洗濯した気分になったり風呂入ってたりしていたら懇親会の終了時刻が過ぎていたので時間が過ぎるのは早い。

この日も談話室でボドゲをした。将棋をわからないなりに見ているうちに、気がついたらスマホに詰将棋のアプリが入っていた。

Day3

ABが簡単って言ってたのでAを読む 英語が読めなくてなにこれ？ってなる(its healthのitsの部分を兵士と誤読する、二次元空間にプロットするなどをしていた 英語が下手)

ここらへんで今日の調子が最悪だな？と気づく まあ頑張る

zawatinからAB両方解けてるという話が出る 実装任せる

解けそうな問題を雑に見る Iは解けそうじゃね？みたいな雰囲気が出ていたので、問題概要を伝える(ちなみにsquirrelは亀と言った)

問題概要を伝えたあとめちゃくちゃ誤読、脱読していることに気づくが、どうやら誤差っぽくてそのまま実装してもらったら FA 風船を初めて見た。

その後Kの問題概要を伝える。データ構造だろうなーって言いながら適当に考察をしてもらった。あとから考えるとここは私がやるべきだった。(Fをやっていたので)

その間にAbeshiがDの実験終わらせてたので、数列を確認したらどうせこれ簡単な式になるだろって思ったので適当に式変形させる。実装してもらう。

ここらへんEとHしか見てなかった。どっちも解けない。

Eに関しては15パズルとか言ったり

1111

2223

3332

は解けないけど

1111

2223

2333

は解けるとか意味不明な発言をしていた時点でお察し。

順位表見たらどっちも解かれてなかったので本当に時間を無駄にした。

時間がないのでFを手伝う。2進数の加算にSegment Treeのlogつけるの厳しくねー？って話をbitset高速化することでそのlogがwordsizeで消えるので実質O(N^2)とか言ってたらbitsetを使えない(今まで一度もbitset高速化をしたことがない) 終わった

このタイミングでzawatinがK解けたと言ったので交代。間に合わず終了。

苦手セットといったらそれまでだけど、どの問題ももうちょっとやりようあったなーというのが感想。というかEはともかくHからはすぐに撤退すべきだった。

反省

基本的なC++コードを書けるようにする

ただ強いコードは私の領分じゃないのでチームメイトに任せる (考察担当なので)

Segment Treeやdijkstra程度までは書けるようにしておく

C++の標準ライブラリの知識くらいは持っておく

考察軸を増やせるようにする

私はアルゴリズムの使える条件、使った結果をカードの効果のように認識している。day2のMやIはそこら辺の知識をちゃんと持っていたから考察ができたが、day3のEとかは知識をカードの形に落とし込めていなかったから解けなかった問題という印象を受けている。

とりあえず実装はしなくていいから高難易度の問題を見る→解説を見るの訓練をやっていこうと思う。変な方向に頭が固まらないようにだけ気をつける。