あったこといろいろ

ほぼ自分用備忘録です。

会津合宿2016参加記

9月の17日〜19日に開催された会津合宿2016に参加しました。

会津合宿数日前~前日

🔥🔥🔥大学で一日中作問作業🔥🔥🔥

会津合宿day1

立命館大学セットの作問を担当していました。
講評・解説・入出力ケースは右のリンクから閲覧できます。public - Google ドライブ

会津合宿day2

会津大学セットに参加しました。
Twitterでメンバーを募集していたらctylさんとkazuさんに声をかけていただきました。

コンテスト開始。
A問題がctylさんにより瞬殺されていたがB問題がうまく行っていないらしい。

一方僕はC問題を担当。謎の学園が出てきたが元アニメを知らず悲しかった(あんはぴというらしい)。
曜日ごとに独立だなーと考えて、各曜日においてbitDPした後「i日目にj科目で得られる幸福度の最大値」を求めるDPをする解法を思いつく。
B問題担当のkazuさんとPCを取り合いながら書いたがWA。
しばらくバグが見つからず悩んだが、論理演算のORを"||" ANDを"&&"と書いていた事に気付き修正し提出するとAC。
「bit演算やったことありますか？？？」という感じ(´･_･`)

Cが通った頃には、BとEが通っていてkazuさんがGを書いているという状態だったので、DとIの概要をctylさんに聞く。

D問題はダイクストラっぽく更新してゴール直前まで行き、ギリギリまで待ってからゴールに渡る解法で解けそうな感じ。

I問題は考察がある程度進んでいて、後は「各頂点から最も遠い頂点までの距離が高速に欲しい」という状態だった。
これ技術奥プログラミングコンテストの不可視境界線では？となったのでcityさんに解法を伝えると良さそうとのこと。

これでDとIの解法が出揃ったが、依然としてGでkazuさんがつらそうにしていた。
この時が一番PCの競争率(?)が高かったように思う。
このときにお菓子を食べに行くと、怒髪先生(ジャッジ側)から「並行して問題解いてるときは一番辛いときだからね。がんばってね。」というありがたいお言葉を頂いた。

その後Iはライブラリを写してもらってすんなりACしたが、DとGはバグが取れずにコンテストが終了してしまった(Gはライブラリが間違っていたらしい)。

コンテスト終了後は駅の方まで移動し懇親会に参加した。
皆で”限界集落”という単語がパワーワードであることに気付きめっちゃ盛り上がった。

会津合宿day3

北海道大学セットに参加しました。
怒髪くんと組みたくなったので探したが遅刻しているらしい。
motiさんに電話をかけてもらってOKの返事をいただく(怒髪先生と連絡をとるのは難易度が高いらしい)。
チームメートがもう一人欲しい気持ちになってTwtterを見ると@tookun_1213さんがメンバーを募集していたのでお誘いした。

問題を各自分担する戦法で僕はA問題を担当。
頑張ってやるだけなのでバグらせないように気をつけながらAC。

実装待ちをしていた怒髪くんがD問題を読んでくれていたので概要を聞く。ありがちだけど時間の制約がデカい。
ライブの開始時刻だけ試すのはすぐ思いついたので累積和+二分探索の方針で実装を固める。
BとCがすんなりACしたようなのでPCを貰って実装を開始する。
場合分けや添字を微妙にミスりながらDをAC。

このあいだに怒髪くんがFの解法を思いついたらしいのでバトンタッチ。
ここでEを読んでいたtookunさんと合流して概要を聞く。
残念ながら僕は何も思いつかなかったが、「意外とゲームはすぐ終了するのでDFSで行けるのでは？」*1という感じと言っていたのでおまかせする。

Gを読む。「角角画伯，かく悩みき」の制約追加版という変わった形式で面白い。
まぁ凸包はするよねみたいなことを話したら、凸多角形の任意の辺を底面とした時の縦横の長さを探索できれば良さそうと教えてもらえた。
「キャリパー法で各辺の最遠点が高速に求まる」とか「辺と各点までの横方向の距離は3分探索で求まる」とか話したけれど、「この問題の制約上与えられる多角形の頂点の数はそんなに多くならない」という仮説が出たので時間の都合でそれを実装する…が僕の幾何実装力が低いので途中から怒髪くんに書いてもらう。
どうやら正しかったらしくコンテスト終了6分前にAC。
残り時間でEを書くのは厳しそうだったので、「Gは最悪ケースを作ろうという気持ちになると (多角形の頂点数)≒√(与えられる正方形の数) になりそうだね」みたいな話をしていた。

順位表を見ると、なんとオンラインで2位になっていていた。
普段2位なんて順位は取れないのでチーム戦は偉大だなぁと思った。

おわりに

考察にかなり時間をかけて作った問題が、オンライン参加していたプロによってあっという間に解かれて驚愕した。
去年はそもそもアルゴリズムを知らず考察に携われない問題も多かったが、今年はそういったことは起こらなかったので少し成長を感じた。
チーム戦は最高！組んでくれた方ありがとうございました

*1:行けませんでした