JAG夏合宿2019 Day1 参加記
2019/9/14に行われたJAG夏合宿2019 Day1にチームEldoradoとして参加しました。
チームメンバーは、ニクロー、まほろば、NOSS
Day1
コンテスト
コンテストリンク:https://onlinejudge.u-aizu.ac.jp/beta/room.html#JAGSummerCamp19Day1
Aをまほろば、Bをニクロー、Cを僕が読む。
CはN個の区間で領域全体をカバーする問題。最小数は解いたことがあったので後半を考える。何個まで取り除けるか考えると区間の重なりが少ないところがネックになるのでこれはimos法で解けそう。一応メンバーに解法を確認してもらい了解を得る。
(00:12) A問題 AC
ニクローさんがBの実装に入る。 途中でBの嘘が発覚したらしいので僕がCの実装に交代する。
Cの実装がバグる。+-の符号が逆だったり比較すべき値が違ったりで申し訳なかった… 後ろでBの修正が終わっているようなので急いで直す。
(00:45) C問題 AC
(00:54) B問題 AC
Dは有向グラフを作ると閉路がいくつかできるので、各閉路の周期を調べてすべてが昇順になるような回数を求めればよさそう。蟻本を開くと連立線形合同式の解を求める方法が載っているのでこれは解けました。
Cで実装に自信が無くなってしまったのでまほろば君に書いてもらう。
Dの考察の間にニクローさんが問題を読み進めていたので概要を聞く。比較的解けそうなのはEとJらしかった。
(02:06) D問題 AC
Eは無限増殖が可能か判定する問題。無限増殖がない条件を整理すると、任意の経路をたどって戻ってきたときの倍率が1であることがわかった。適当な根からdfsをしてすでに訪れた頂点へは倍率1で戻っているか確認すれば解けそう。問題は倍率が最大10900000になるのでやばい。 logをとることを思いつく。とりあえず書くとサンプルが合うので投げる。でも誤差怖いなあ...
(02:53) E問題 WA
それなりのケースが通っているのでやっぱり誤差がやばそう。long double にしたりEPSの値を小さくしたりして調整する。
(03:37) E問題 WA
なにも解決策が思いつかない。いったんEを諦めてJをみんなで考察する。
最大値はM-連結成分の個数なので簡単。問題は最小値でコマを頂点とする最大独立集合が解ければいいのだが不可能なので困った。
行き詰っているとまほろば君が「フロー...?」とつぶやいたのでよく見ると2部マッチングとわかる。蟻本の二部マッチングを写してもらうとサンプルが合ったので提出。
(04:10) J問題 AC
Eの解決法として複数MODをとればいいのではと思いつく。とりあえず5個MODを用意してlogと併用して判定に利用する。
(04:39) E問題 WA
テストケースがすすんだので誤差の問題だとわかる。よくわからないので109以上の素数を100個くらい列挙して埋め込む。
(04:50) E問題 TLE
流石に多すぎたので50個に減らす。
(04:52) E問題 WA
？？？
このときはテストケース強すぎではと思った。これだけやってだめならMODガチャだね、とコンテスト終了まで粘った。が、ACはできませんでした。
感想・反省
EのEPSを1e-14から1e-5に緩くしたら通った。むしろlogないほうが良かったらしい。少数誤差を甘く見過ぎました...
全体としては解ける問題を解けているので悪くはなかったと思います。
