NOSSの雑記

主に競プロでやったことを書きます。

JAG夏合宿2019 Day2,Day3 参加記

ICPC 参加記

JAG夏合宿2019にチームEldoradoとして参加しました。
チームメンバーは、ニクロー、まほろば、NOSS

Day1の記事はこちら

Day2

朝が早いのでちょっと眠たい。同室みんなで朝食を食べに行きました。

コンテスト

コンテストリンク:https://onlinejudge.u-aizu.ac.jp/beta/room.html#JAGSummerCamp19Day2

まずBを読むと明らかにフローなので始点と終点が複数のフローで解けるのかなと思う。
まほろば君とAについて話して方針が固まったので実装をやってもらう。

(00:20) A AC

いまのところ解けている問題がないのでとりあえずBの最大流を蟻本を写経して投げる、がWA。
よく考えると致命的なケースがみつかったので断念する。ちゃんと考察をするべきですね…

順位表を見るとEが大量に解かれているのでメンバーに読んでもらう。やばそうな見た目をしているがよく読むとギャグらしい。

(00:57) E AC

Dの概要を聞く。生存である集合の部分集合に死亡であるものがあるとき不可能なのでこの場合を除く。なるべく小さい死亡の集合を見つけたいので1つずつbitを下ろして確認すればよさそう。

(01:19) D AC

ここから険しい時間が続く。

  • F 一般マッチングのライブラリがあれば解ける！持っていません...

  • G 直線上の問題ならABCの問題にあったけど円環上は？

  • J お互いに相手の根本を削るのが最善なので数列の最小値が問題になる。n乗和の式で表せるところまで進めたけどこれは求められないな...

順位表を眺めるとIが比較的通されているのでよく考察してみる。きちんと場合分けをすると割とキレイな性質があることがわかったのでこれは解けそうとなる。メンバーでよく確認しながら実装をする。

(04:19) I AC

一発ACできたときは嬉しくなった。

このままコンテスト終了。結果はADEIの4完でした。

感想・反省

  • きちんと考察してから提出しよう。

  • ライブラリは重要。

懇親会

開始直前まで昼寝をしていて同室の皆さんに起こしてもらった。会場に大量のカツサンドが積まれていて面白かった。

お話してくださった皆さんありがとうございました。

ABC

黄色への変色がかかっていたので懇親会から引きあげて参加する。

そしてついに黄色に...!

同室のyamadさんに「あ、黄色になりました」と言ったらすごく驚かれました。懇親会で何人かから今日で黄色ですね！と言われていたのでちゃんと変色できてよかった。

Day3

シーツ畳み込みのプロ・畳小宮になる。

コンテスト

https://onlinejudge.u-aizu.ac.jp/beta/room.html#JAGSummerCamp19Day3

Aの概要を聞くと奇数に偶数を足していけば良さそう、となって最終的に奇数の個数の偶奇にで場合分けすればよいことがわかった。

(00:15) A AC

Cを読む。どの区間を最後に残すかが重要そう。ニクローさんと話すと最も区間が重複しているところがネックになって重複してる分だけ往復が必要だという結論に至った。あとは重複している区間のうち最も端に近いのを残したいということになったので本当にそれが達成可能なのか正当性を議論した。最終的に達成不可能にしようとすると重複の最大性に矛盾するということになったので正当性のある貪欲を書く。

(01:26) C AC

Bは最初の大小関係がずっと変化しないことがわかる。クエリをセグ木に乗せられるか？という話になったけどどうやっても割り算が無理そうなのでだめになった。なにもわからないので後ろの問題を読んでいるとニクローさんが解けたらしいので実装をお願いする。(すごい)

(02:44) B AC

Eがフローに見えたりJのパズルを解いてたりしたらコンテストが終了してしまった。結果はABCの3完。

全体の感想

上位チームの人々との圧倒的な力の差というのを感じました。いままで習得がおっくうになっていた技術をもれなく要求されたので、やはりやらなければならないなという意識が生まれました。とても刺激的な合宿で参加してよかったと思います。

運営のJAGの皆さんありがとうございました！