はじめに
こんにちはebi_flyです。JAG夏合宿に参加していました。コンテストは3日ともnoya2くんとshobonくんとICPCチームであるAMATSUKAZEで出ました。
day1 (韓国国内予選2022)
初動でテンプレートを書きました。
Aでshobonくんが「すみません、WAになるので見てください」と言ったので問題文を見ると、いくつかの重りをつかってある重さを作るのに必要な重りの個数の最小値なので、dpだなとなりました。shobonくんに「dpでやってますか？」聞くと、「dpでやっていて、左右に重りが乗せれるのもちゃんと考慮しています」と言いました。なんか良さそうだなとなったが一生WAだったのでう～んと言っていると補足資料に軽い方しか重りをのせれないと書いてあり、え～～～と言いながら直すと通りました。
Jを見てこれはbitsetで高速化だろ～とか適当言いながらコネコネしていたらnoya2くんから「Kは時間毎に使える辺が変わって各時間に使える辺は高々1本のときの1からNまでの距離なのでDPでできます」と言われたので実装して提出するとWAが出て焦っていると、補足資料に双方向に移動できますと書かれているので直すと通りました。（え？）
その後Jを見て、できることが少なすぎると困っているとshobonくんから「Gは簡単じゃないですか」と言われたので読むと、確かに3次元のdpをすればよいなとなりました。それを伝えると「最適な行動をどうすればよいかわからなくないですか」と言われたので「再帰で実装して最適な手を選んでいけばよさそうです」というと理解してもらえたようで実装してもらいました。ほどなくして通りました。
Jを見ているとshobonくんから「x座標毎に見て、各x座標に属する点の数が多いものと少ないものに分類してガチャガチャやるとできそう」と言われて確かにとなったので実装してもらいました。点の数が多い同士はbitsetのANDとpopcountで行い、点の数が小さい同士はmapに2点を入れて判定、小さいものと大きいものは小さいほうのを見て同じy座標のものがあるかを見て行き同じy座標のものがあるようなyの個数を求めることで答えを計算しました。ブロックサイズを適当にいじったりmapをソート+二分探索にしたりなどの定数倍高速化しても通らないので困っていると、2次元配列の各配列ではなく全体をソートしていたことに気づきなおすと通りました。
最終的にはnoya2くんが色々通してくれて7完7位でした。ペナが終わりの量だったので明日は減らしたいねと言いday1のコンテストは終了しました。
day1 (コンテスト以外)
コンテストが終わると、部屋の鍵が渡されご飯を食べに行きました。帰り際にnoshi91さんとnoya2くんで売店に行きday1-Bが難読であったことを話したりその解法を聞き確かにな～となりました。
部屋に着くと、同室の人と自己紹介をしたり雑談をしてお風呂に行きました。同室に出身高校が同じ人が居て少し盛り上がったりもしました。
ABCに部屋で参加し、Fが最後の5分くらいでやっとあってなんとか6完しました。絶対あってるよ～とコードを見返すとLNFとしないといけないところをINFとしていてバカ～～～となりました。
day2 (有志セット)
今日はペナをださないぞと意気込みました。
最初にテンプレートを書き、Dを考えているとnoya2くんから「多分K解けるんで解いてください」と言われたので見ていると a->b->cのa->bと行ったときをdpとは別の配列で管理すればできそうだなと思い書くとWAが返ってきたので印刷してデバッグしました。
デバッグの間、Dを書いてもらっていて重実装だったのでパソコンが使えず目デバッグでKをデバッグしていたので「もう間違っているところないです」状態になりました。DをFAで通りすげ～となりパソコンが空いたのでshobonくんが適当なケースを試すと明らかに壊れていました。a->b->cという制約とa->b->dという制約を別で管理していたためa->b->cの遷移ができてしまっていたのでそれをなおすと通りました。
その後Jの実験コードを書いてもらったりしましたが光明が見えず6完6位でした。自分はKしかできず、カスみたいなペナも出したので非常に申し訳なかったです。
day2 (コンテスト以外)
day1より早めに夕食とお風呂を済ませたので、 ARCまで寝ました。ARCはBでカスみたいな嘘に1時間くらい固執して、正しい考察ができた後も実装がハチャメチャになってしまい-58してしまいました。その後同室のtokusakuraiさんにデバッグを手伝ってもらいなんとかBを通し談話室に行くとwriterのchineristさんとtesterのpotato167が居たので問題について喋りました。そこでCが競プロチックでC行った方がよかったのではと言われて、考察まで終えた問題を飛ばす勇気はないよ～となりました。
今回のARCの反省としては、バグったなら目デバッグではなくすぐにランダムチェッカーを書くことや後ろの問題に目を通すことをすべきということになりました。
その後東工大の人々と深夜徘徊をし、外国の方に道を聞かれたがしどろもどろに答えてしまい反省するなどしました。potato167がめっちゃ落ち込んでいました。
day3 (JAGセット)
例によってテンプレートを書き、IJKを眺めました。すぐには考察が進まず、IJどちらも自明なdpを立て眺めることをしました。するとIはそもそもdp配列を持たなくても最適な値をどんどん更新していけることに気づき、書きました。怖かったので、ランダムチェッカーと自明な2乗のdpを書きまわすと落ちたのでひっくり返っていると場合分けをミスしていたり忘れていたりしていたので直しました。するとランダムチェッカーで落ちなくなったので出すと通りました。ARCの反省が活きていて偉いぜ。
その後Jを見て、shobonくんに「自明と言われたdpがよくわかりません」と言われたので説明すると同意を得られ、考察をすることにしました。すると移動してできた文字の文字長は必要ない情報であることがわかり状態数を減らせました。具体的には
これは、遷移が で状態数が なので間に合うなとなり実装しました。実装中にfor文ではDAG順に更新できないことに気づき急いで01bfsに書き直しました。するとサンプルがあったので出すと通りました。
その後はHを見て、Trieを構築するとprefixがまとまるのでその木で探索ができればよいということになりLCP Arrayを使ってガチャガチャやるとできるなとなりましたがガチャガチャ部分が複雑すぎて嫌な気持ちになりました。
CでFPSの式がたったらしいのでそれを眺めて高速に計算できないか検討しましたが、平方分割で5secにしかならず頭を抱えていました。
こんなに通されているのは流石におかしいだろとなりましたが通せず5完11位になりました。
Hをもっと考察してハッシュをTrieに乗せるともっと楽になることに気づかないとダメだったな～とか実装をガっとやる能力が必要だとなりました。
day3 (コンテスト以外)
tonosamaの人々に夕食どうですかと誘ってもらったので、東工大の人々と夕食に行きました（すでに帰ってしまった人もいました）。新宿の中華に行きました。適当にお粥 + 油淋鶏を頼んだのですが、他の人たちはチャーハン + 麺類 + 油淋鶏というわがままセットを頼んでいました。データ構造の話もできて楽しい夕食でした。
最後に
夏合宿を開いてくれたJAGの皆様には大感謝です。とても楽しむことができました。夏合宿で交流した方も、そうでない方も横浜でまた会いましょう。
自分の競プロでの弱い部分を認識できたので横浜までに克服して横浜では勝てるように頑張りたいです。
3日間ありがとうございました。
