memo46

競プロの精進記録その他。

HUPC2020 参加記

3日間すべて参加しました。

1日目

今年ICPCで組む予定のチームUHISHIRO(suta siro53 kiyoshi0205)で出ました。

コンテスト内容

  • まず僕がAをさっと通す
  • sutaが「あ～これimos2回やるやつだ」と言いながら通す
  • この間、僕がDを読み終わり考え始める。sutaがEを読む
  • しばらくしてkiyoshi0205が「あ、Cギャグですね」といいながら1ペナで通す
  • Eを読み終わったsutaとDを考えると、なんかすべての点を通るようにうまく直線を引いた時に3つ以上あったら無理じゃねみたいな話になる。
  • kiyoshi0205もCを通した後に合流し、すべての点を通るように2つの直線をうまく引いたとき、2直線が平行じゃないとまずいねというところまで考察でき、後はその直線が引けるかどうかの判定をどうやって高速にやるかを詰めることになる。
  • しばらく議論するとkiyoshi0205が詰め切れたらしい、聞いてると計算量も大丈夫そうなので実装してもらう
  • Eをsutaから概要を聞いて考える。ワーシャルフロイドして辺を張り直すと2部グラフがいくつかできる感じになることに気づく。ここで勝ちを確信する（ここが悪夢の始まり）
  • 2部グラフを塗って、数の少ない方を足していく解法を僕が実装するが9ケース目で落ちる。実装を見てもらうが別におかしいところは見当たらない...　ここで暗雲が漂い始める。
  • kiyoshi0205がDを通したので問題概要と考察を共有すると「あってそう」と言われる。実装ミスも見当たらないので3人でコーナーケースを見つける旅に出る。
  • 残り30～40分ぐらいでkiyoshi0205がコーナー発見、嘘が発覚。なんやかんや3人で議論して最小点被覆ですねという話になって僕が実装を再開。
  • なんかバグる（←？？？？？？？？？？？？？？？？？？）ドチャクソ焦ってしまったぼくはkiyoshi0205に泣きついて交代してもらう。Eが通る（本当にごめんなさい）
  • Fを考察するも時間が足りず終了

結果

5完28位。Eで嘘に走ってなければ+1完できたかも... 大戦犯...

f:id:bakamono1357:20200916224903p:plain

2日目

これもチームUHISHIROで出ました。

コンテスト内容

  • 僕がAを読む。「多倍長整数か？？？」「いやごめんなんでもないわ」→AC
  • 面倒そうなBをsutaが書いてる間にCで詰まってそうなkiyoshi0205の様子をチラ見する。「行列累乗なんだけど行列どう作ろう...」と言っていたがこれはkiyoshi0205にやってもらうべきじゃないやつっぽいので、僕に任せてもらいkiyoshi0205には後ろの問題を見てもらうことに
  • sutaがBをAC。ほどなくして僕がCをAC。
  • kiyoshiがDはできそうなんだけどよくわからないという。僕もsutaもDを見るがパッとはわからん...
  • このときDGM？が解かれていた気がする、Gを僕が読んだので概要を伝えると、ダブリングだとkiyoshi0205がいうので即実装してもらう
  • Gが通らない
  • Gが通らない
  • Gが通らない
  • この辺からやばくね？みたいな感じになる。僕がDを整理してしばらくすると、kiyoshiが「これどっかでみたぞ」「PG BATTLEで実は貪欲でいけるやつだ」→調べると本当にほとんど同じ問題 sutaが貪欲を書いて証明:AC
  • kiyoshi0205がMを見ると、「Grundy数か」といい、なんやかんやで1人で詰めてAC。（すごい）
  • sutaがJ解けそうらしい、多少思い違いがあったらしいけどすぐに考察を修正してAC（すごい2）
  • ここらへんでチームの雰囲気が明るくなる(俺何もしてないけど)。Gのコーナーを探そうという気持ちになる。実装方針を聞きながらソースコードを追っているとオーバーフローを発見したので指摘、すぐにkiyoshiが修正→AC
  • 7完して安心するけどライバルの早稲田2チームに勝つためにIを全力で考察する。なんか基底変換をしていけばいけそうだけど、線形代数を忘れすぎて詰めきれず時間切れ...

結果

7完28位。give usとyamad_as_a_serviceは8完してるので完敗... 僕が完全にお荷物になってしまった、精進しよう... f:id:bakamono1357:20200916230602p:plain

3日目

kiyoshi0205は参加できないらしいので1人早稲田競プロslackでメンバーを募集すると、yamadさんが入ってくれることに... チームmouko_tanmen(yamad, siro53, suta)で参加しました。

コンテスト内容

  • まず僕がAを読む。なにこれ難しくね？？？→Bを読んでました...　すぐにAC
  • yamadさんがCを詰めたらしいので書いてもらう。この間僕はなるべくすべての問題に目を通して、簡単な問題を探すことに
  • sutaがBを考えるがかなり厳しそう、とりあえず出た解法を出すもWA
  • とりあえずDEFIJMぐらいを読む。Mの概要を共有し、自分はIを考える。しばらくするとyamadさんがM解けたらしい、このタイミングでIが解けたので解法を共有するとそっちの方が軽いのでまとめて書いてもらう。
  • Iが通る。
  • Mが書けたそうだが若干TLが怪しいらしい。yamadさん「(submissionを見ながら)ありがとうありがとうありがとうありがとうありがとうありがとうありがとうありがとうありがとうありがとう」→TLE
  • これで通らんわけがない、と少し改善してまた提出。yamadさん「(submissionを見ながら)ありがとうありがとうありがとうありがとうありがとうありがとうありがとうありがとうありがとうありがとう」→TLE
  • unordered_mapが重そうなので、3進数は適当に変換すれば配列で持てませんか→修正してもらい、AC
  • この間にBの実験コードを僕が紙コーディングしてsutaに渡す、sutaが書き上げて実験したところ場合分けがちょっと足りなかったらしい。全員でありがとうと合唱しながら提出するとAC！めっちゃ盛り上がる
  • この間に僕がFを少し考えていて、現時点での方針を共有。なんかランレングス圧縮的な考え方だったきがする（だいぶ的外れ...）（実は誤読してたんですけどね）
  • yamadさんがEを考えるも、どうしてもキツいらしい。（実は誤読(正確には途中で問題文が変わった)してたんですけどね2）
  • sutaがGを読んでいたのでyamadさんに共有するとDPなんじゃないかみたいな話になる。しばらくyamadさんが1人でGを詰める。
  • 僕とsutaはFを詰めることになった。とりあえずPC空いてるし小さいケースを全探索するコードを僕が実装、バグらせる(え？)
  • この時思いついたら提出しちゃえみたいな感じだったので現時点での考察でFを提出→WA
  • 全探索コードのバグが直る。なんか小さいケースだけ全探索すればいいんじゃね→WA
  • ここでyamadさんに「隣り合うマスが異なる色じゃないと操作できないんじゃないの？」と言われ、誤読発覚。全探索コードを治すと、今までの考察が白紙に戻りかなり絶望する。
  • yamadさんがこの間にGを詰めきれたらしく、実装してAC。Fを通すぞという気持ちになる
  • 頑張って不変量を探そうみたいな話になる、suta「なんか出現回数の偶奇でうまくいけないかなぁ」これを聞いて僕が2点swapができるんじゃないかと気づく。2点swapができるなら出現回数を合わせられるならYesじゃないか？みたいな話を2人に共有してみると、そうじゃん！！！証明：ACという感じになり、s==tのコーナーは最初に弾いてもらうようによしなにsutaが実装するとAC、ここマジで一番声出た
  • Ramen_as_a_ServiceがEを通してるのでyamadさんがEを再考する、ここでyamadさんの現時点での考察を聞くとsutaが誤読に気づく。なんか途中で問題文が変わってたらしい。yamadさんは解けそうだが時間が足りるか怪しいとのこと。
  • 僕とsutaでJを考察するが、手も足も出ない。EもWAが取れず、コンテスト終了。

結果

7完24位。 f:id:bakamono1357:20200916233046p:plain

感想

どのセットも内容が濃くて、非常に勉強になるしモチベーションも上がりました。 オンラインでの開催でしたが、まるでオンサイトで参加してるかのような緊張感で取り組めました。 作問者の方々ならびにHUPC運営の方々、本当にありがとうございました。お疲れさまでした。