Mister雑記

競プロやります。

MisterのJAG夏合宿2019参加記

The atama 3人でJAG(ACM-ICPC OB/OGの会)が主催する夏合宿に参加してきました。

目次

Day 1

The atamaの集合は早い

初日は集合場所がオリンピックセンター(以降オリセン)だったので、万全を期してThe atamaは一旦合流してから行くことに。 結果全員が時間通りに集合して、11:00にオリセンに着いた。全員揃った時刻ではFAだった気がする。

Day1の貢献は少ない

その後人がぞろぞろと会場入りして、Day1のコンテストが始まった。 以降(謎の)守秘義務により、メンバー名を僕、S、Oで表すこととする。

コンテストリンク

  • いつも通りA問題をS、B問題をO、C問題を僕が読む
  • B問題をOが実装→AC
  • A問題をSが実装→AC
  • C問題の考察が終わる
    • セグ木が要るので慣れているOに実装を投げる→AC
  • D問題に考察を集中
    • サイクルに分解して中国剰余定理を使えば解けるね
    • 似た問題を見たことがあるということでSが実装→AC
  • Jが解かれているので考察する
    • 最大マッチングと連結成分じゃん
    • ライブラリ担当?のOが実装→AC
  • 実装中に僕がE問題を考察
    • 積を距離としたときBFSとかで矛盾を調べれば解ける
    • 素因数分解とか考えたが、計算量が削れない
  • SとOがH問題を考察
    • 「どの行にあるかは分かる」というところまでは来た
    • しかしそこから先が詰められず
  • 少し解かれているG問題とかを考えたが微塵も分からない
  • 再びE問題に考察を集中
    • とりあえず対数でOが実装→WA
    • S「ハッシュ的な方法でなんとかならない?」→MODを取るもWA
    • 非連結なケースで死ぬことに気づき修正→AC
      • ちなみにコンテスト後に対数のを修正して投げたが通らなかった
  • K問題が畳み込みで解けることに気づく
    • 僕「誰かFFT持ってますか?」S「いいえ」O「いいえ」 おしまい
    • 僕がうろ覚えで実装を試みるも、できるはずもなく終了

結果ABCDEJの15位(オンサイトは多分10位)。以下反省点。

  • 僕が実装をしなかった
  • 全員が全問題を読むべきだった
  • FFTくらい用意しておくべきだった
  • Eの考察に時間がかかりすぎた

振り返るとABCDEJを2:30くらいで片付けて、せめてK問題までは通したかったという印象。OがLi-Chao木を持っていたのでI問題もワンチャンあったかもしれない。

何にせよ実力不足、特に速度不足を痛感する結果となった。

314の夜は長い

コンテスト後は夕飯を除いてほとんど自由時間。談話室でボドゲに混ざらせていただいたりした。

なお僕が割り振られた314号室はTwitterでよく見る顔ぶれで、さらに何人か訪問者が来て結局2:00まで起きていた。ワイワイできてとても楽しかった。

Day2

夏合宿の朝食は遠い

7:00 - 9:00が朝食の時間なのだが、宿泊者が数百人いるのに食堂が1つしかないので非常に混む。というわけで早起きして6:55に食堂に着いたのだが、それでも結局10分待たされた。

ちなみにDay3はそれを踏まえて6:45に向かったところ、並んではいたが1回目の波で入ることができた。

Day2の精進は足りない

その後しばらく部屋で寝て、Day2のコンテストが始まった。

コンテストリンク

  • 難易度順がランダムということで、FA狙いで各位バラバラに問題を読むことに
  • 僕がE問題から読み始める
    • 面倒そうな式だな→いやギャグやんけこれ→AC
    • 5分ACで全体2位だったが、FAとは2分差だった
  • J問題がいけそうになったので僕が実装
    • サンプルで嘘であることに気がついて悲しくなる
  • SとOがA問題を考察
    • Sが実装→AC
  • 僕がD問題、SがJ問題、OがI問題を考察
  • D問題の解法が分かるも、計算量がヤバい
    • しばらく考えていたが、計算量の見積もりミスに気づく
    • 僕が実装→AC
  • I問題の考察が終わる
    • Oに実装をしてもらう
    • 大きいケースは良いが、小さいケースのシミュレートが大変
    • ジャッジがバグっているという情報が入るが、とりあえず投げておく
  • SがJ問題の解となる式を導出する
    • しかしこれの計算量がどうしても減らせない
    • 見積もり的にコンテスト中には間に合わないが、とりあえず埋め込みを走らせる
  • 他の問題も何も分からず、時間だけが過ぎていく
  • I問題のリジャッジが行われるもWA
    • コードを印刷するも何もミスは見当たらない
    • 大きいケースを走らせると、infという出力が出る
    • 累乗関数が名前衝突を起こしていることが発覚→AC
      • 3人のコーディングスタイルの違いが災いの元だった
  • 終了数分前にF問題が一般マッチングに帰着できることに気づいて終了

結果ADEIの20位(オンサイトで多分13位)。I問題のジャッジがバグってなければもっと上だったと思うが、それにしても悲しい結果だった。

反省点は「コーディングスタイルの違いがバラバラだった」くらいで、他の問題は現状どうしようもないという感覚が強い。シンプルに実力不足を痛感した。

懇親会の飯は多い

コンテスト後諸々を経て、19:00から懇親会が始まった。

とはいえ根本的にコミュ障なので、あまり人脈が広げられず悲しかった。それでも初めて話した人もいて楽しかった。

あと飯が競プロ関係のものが多かった。以下は哀愁漂うカツサンドくん。

懇親会後、風呂から部屋に戻るとこたつがめくんがABCのコードゴルフをしていた。僕はABCに参加する予定はなかったので観戦していたが、AtCoderのコーディングエリアにコードをベタ書きする様は見ていて圧巻だった。コンテスト全体でもちゃんと全完していて凄いなぁとなった。

ちなみにこの日の夜もなんやかんや1:30まで起きていた。人はなぜ。

Day3

Day3の嘘は怖い

部屋でダラダラしていたらチェックアウトがビリになっていた。全員とっくに出る準備はできていたんです。

それはさておきDay3のコンテストが始まった。

コンテストリンク

  • やや変則的だがSがテンプレを書きつつ僕がA問題を考察することに
    • 解けたので解法をSに伝える→AC
  • 実装中に僕がB問題を考察する
    • 順番は前後しないから二分探索だなとなる
    • greater or equal to」の「or equal to」を見逃して1WA→AC
  • 諸事情でPCが使えない時間があり、B問題の実装待ち中にSとC問題を考察する
    • 往復回数は区間グラフの彩色問題で、これは離散数学演習でやったため解ける
    • 最後の週が面倒だが、それを詰め切る前にPCが使えるようになって後は任せる
    • 詰め切れたらしくOが実装→AC
  • D問題が構築なのでThe atamaのatamaことSが取り組む
    • X = 0とA ^ O = Xが無理ということが分かる
    • Xのbitが全部1の場合に構築ができる
    • 他の場合も帰着できるかと思ったができなくて終了
  • E問題は見た感じフローっぽいのでグラフを考える
    • 流量下限を課すことでグラフが完成する(嘘)
    • 僕が最小費用流を実装をする間Oにグラフの構築を頼む
    • 実装が終わるもなんか上手くいかない
    • どうすれば直るのかよく分からないままコンテストが終わった
  • 後で聞いた話だが、終盤SはJ問題(これも構築)を考察していた
    • Nが奇数の場合が無理であることは分かっていた
    • Nが偶数の場合、N頂点の完全グラフを完全マッチングに分解できれば解けていた
    • コンテスト後に調べたら構築方法が出てきた。

結局ABCの20位(オンサイトで多分12位)。コンテスト後無力感に包まれていた。 なお他の問題もちゃんと読んでいて、合間合間で考察をしていたが全く分からなかった。

コンテスト後にhenoくんにE問題のフローが嘘であることを指摘してもらった。 そしてD問題はアドホック構築ではなく2-SATが想定解だった。僕たちの3時間は一体......。

万豚記の閉店は早い

そんなこんなで3日間に渡る合宿は終わりを告げた。 JAGの皆さん、writer陣の皆さん、本当にありがとうございました。 正直なところ、夏休みの頭にやってほしかった。

ちなみに合宿中に何度か「近くにある万豚記という店の炒飯が旨い」とOに熱弁されていたので、帰りにThe atama3人で寄ることにした。