会津合宿2016 参加記

 というのを初めて知ったので、参加記を書きます。

Day 0

前日の夜に移動を開始した。

新千歳空港から仙台空港に行って、JR仙台駅付近のホテルに泊まった。

利久で牛タンを食べました。うますぎる。

 

Day 1

仙台から高速バスで会津若松駅に行き、そこから歩いて会津大に行きました (毎日歩いていたけどみんなバスとか使ってたんだろうか？)

たぶん4年ぶりくらいに会津大に行った。

 

コンテストは宇宙ツイッタラー氏とか会津のWF勢とかいろいろとチームでやってみたい人たちがたくさんいたけど、老害なので調子に乗らずに初心者のサポートをする感じでやろうかと思ってあえて誘わず適当なチーム決めに参加した。

会津の若い人々 (twitterをちゃんと聞くの忘れていた…) と DKK というチームを組んだ。

 

2人にA,Bを任せて僕はDのFAを狙いに行ったがムズすぎてわからない。

Bがわからんと相談され、約数列挙してGCDをその約数にするよう調整する方針を思いついたのでそれを説明したら書けそうとのことだったのでお願いした。Nが小さいのを利用しなさすぎて複雑な実装をお願いしてしまったのが完全に失敗で害悪だった。

Aも問題文の読解に苦しんでいるようだったので一緒に読んだ結果、逆に僕が誤読して指示を出してしまい害悪だった。

Cを読んだら貪欲っぽかったので2人が書いている間に詰めずにDを考えていた。いざ実装するときになって「あれ？復元割とめんどくさくない？」となって害悪だった。

Eが通されているようだったので読むと、「あれ？edgクエリいらなくね？」となる。チームメイトに相談すると「さすがにそんなわけ……」みたいな顔をされるが押し切って書くとWA。lstクエリでkを受け取った後はk個の読み込みをしなければならないのにn個読み込んでいた。はい害悪。

Dは1個辺をとって橋を列挙すればいいよ、とドヤ顔で語っていたが内心「やっべ、橋のアルゴリズムは知ってるけどライブラリ化してねえ、やっべ」となっていた。

 

結局Dは実装する時間がなく、最終的には4完15位 (オンサイトでは3位？)

初心者をサポートするとか調子に乗っていたが完全に害を撒く老害だった。

 

夜は懇親会がなくなったので @public_sate の車に乗せてもらい、曰く「宇宙一おいしいラーメン屋」に連れて行ってもらった。知らないと絶対に行かない場所にあるラーメン屋だった、最初に開拓した人やばすぎる。結論から言うと、2回替え玉した。

Day 2

5時間だと初心者と組むと結局僕が後半実装し続けるだけになり双方得しないと思ったので、経験豊富な人と組みたいと思っていたところ、@yurahuna さんがメンバーを探しているようだったので、組ませてもらった。

@yurahuna さんが誘った @ry0u_yd さんと3人でsoujirouというチームで出た。

2人にA,Bを任せて僕はDのFAを狙いに行ったが (デジャブ)

昔の模擬国内の Sinking islands を思い出して、辺を時系列にソートして0から到達できるとこをUnion-Findすればよさそうと思い、@ry0u_yd さんがAを通したところで実装をしてみるが、サンプル5で同時に複数辺が張られるケースに後から気づき焦る。 (サンプルを先に試すべき (チーム戦で余裕があるときは特に) というのはいつも反省するのに全然身につかない、いい加減学習したい)

@yurahuna さんがB書けそうとのことだったので先にやってもらうことにした。

その間 @ry0u_yd さんにCの相談も受け、1次元にしたらよくあるDPっぽいと聞く。それでよさそうだったし、解法を自分で理解しているようだったので任せて紙コーディングしてもらう。

Bが通ったのでDを書く。同時辺が出るときはそれらからなるグラフについて、すでに0とくっついているのをキューにいれて、キューから出した頂点から行ける点をさらにキューに突っ込む、みたいな実装をして軌道修正したら通った。

その後 @yurahuna さんがEができたとのことだったのでお願いしたら一瞬で通していて神だった。後で解説を聞いたがああいう手で試したらわかる系は僕は苦手なので本当に助かった。

Cの実装をお願いしている間に僕はGをさらっと読んで解けそうだったので、@yurahuna さんに式などの詳細を詰めるのをお願いして、他の問題を読んだ。このときにはIも解けてたはず。

Cが詰まったようなのでペアプロっぽくやった。デバッグ中は @yurahuna さんに交代して幾何ライブラリを写してもらったりしてた気がする。Cは結局forループでDPの最大のとこを参照するためにrepの引数を+1し忘れるみたいな典型ミスで1WAしてしまったが通った。

@yurahuna さんにGをお願いしている間に @ry0u_yd さんにIの解法を説明してお願いした。Gもサンプルが合わなくてつらそうにしていたので、2人の間を行ったり来たりしながら合間に問題を読み進めていた気がする。

Gが通った頃にはHとLが解けていたので、@yurahuna さんにどっちがいいですか？と聞いたところHがいいとのことだったのでお願いした。

Iは実装できたがREが出てしまい、再帰しすぎでスタックオーバーフローしてることに気づく。 (毎回AOJで木の問題やるたびにREしてから気付くのやめたい) @ry0u_yd さんが再帰をスタックに直すのに慣れていないようだったので、僕が書くことにして、Hと交代しながら書き進めていた。@ry0u_yd さんには新たに解けていたKの境界条件とかを詰めてもらっていた。 (これは嘘で、マンハッタン距離を勝手に正方形にしていたが実際はひし形なので45°回転が要るのを完全に忘れていた)

結局先にIが通った。Hは終了直前に実装が落ち着くも、見逃していたケースがサンプル1に含まれていることに気づいたときには終了30秒前だったので諦めて終了。

最終的には7完8位 (オンサイト1位！) になった。自分ではDとIしかコードを書かない立ち回りでいい成績だったので、当初の目的は果たした感があるしこの日は割といい老害だったと思う。

老害なのにオンサイト1位景品をもらってしまったのはさすがに申し訳なかった。

この日は懇親会があったので酒を酌み交わした。宇宙ツイッタラーX氏が酒を備蓄して富豪感を出していたが、後にグラス交換制であることに気づいたところが面白かった。

Day 3

最終日は作問側としてジャッジに回った。会場で仕込んだネタに反応して笑ってくれた人たちを観測できたのが楽しかった。問題が面白かった (多義) と言ってくれる人たちがいて本当に嬉しかったし、そういうのが聞けるとホント作問してよかったなと思う。

会場にMacの電源アダプタを忘れてしまい、ラーメンを食べているところに @public_sate に届けてもらって本当に申し訳のNASA。

この日はまだ泊まって会津観光しようと思っていたので、その後鶴ヶ城を見学して東山温泉に浸かって体を癒した。温泉はわずかにオーバーフローしていた。

Day 4

帰りも仙台空港だったので、早めに仙台に移動して観光しようと思っていたが、いろいろ failed してしまい、結局仙台に着いた頃には17時近いという残念な状態に加えて雨だったので、おとなしく空港に向かって特に何もせずに帰宅した。完全に時間を無駄にしていたのでつらかった。

まとめ

AOJはサイコー！

AOJ 800 solved

3ヶ月ほど前、AOJで800 solvedが目前になったため、

ということをしたら(案の定)グロい問題がたくさん集まりました。

識者のみなさんからは

というありがたいお言葉をいただきました。せっかくなんとかプロコン人生を終わらせずに済んだので、解いた問題達の解説を書き残しておきたいと思います。

795問目: AOJ 1151 くるくる

多角形に棒が1点で内接しているので、その点を中心に回転させ、次に多角形に接した点を新たな中心にしてさらに回転させ……、というのを一定の角度行ったとき、最初に触れていた棒の端点はどこにあるか？という問題。

解法が「回すだけ」で有名な問題。

確かに回すだけなんですが、言うまでもなく回すのが難しい。

どのくらい回転させるのかを、線分の長さを半径とする円の内部にある頂点、あるいは多角形の辺と円との交点、のうち、中心となる端点からもう一方の端点へのベクトルとのなす角が最も小さくなるものから選ぶ、というのが基本的な方針。

複数同じ角度になる頂点がある場合、最も中心から遠いものを選ぶ必要がある。

線分が多角形の辺と共通部分を持つ状態があるというのが結構めんどくさい(例外処理しないと常になす角が0で最小になり、動けなくなるので)。

最終的には計算誤差によりacosに1よりわずかに大きな値を入れてしまいnanが返ってくるバグにずっとやられていた。

 

796問目: AOJ 1523 Cone Cut

円錐と内部の点Pを通る平面が与えられるので、その平面で円錐を切断し、分断された2つの立体の体積を求めよ、という問題。

今回の問題の中で一番良心的な問題だった。amylaseさんが仏に見えました。

制約を見ると、平面は絶対に底面を通ることはないため、切断された上部の立体は必ず斜楕円錐になる。

なので、斜楕円錐の底面の長辺・短辺・高さがわかれば簡単に計算することができ、これらは少し数学を頑張ると比較的簡単にわかる。

最初の立体が割と自由に与えられるのが少しめんどくさいので、最初に頂点が(0,0,h)、Pが(0,y',z')になるように回転させてやると楽になると思います。

 

797問目: Secret Operation

長方形の障害物がある2次元平面上で、2人の人のタイムスタンプ付き軌跡データが与えられる。Aさんは進行方向から左右45°、距離R以内の範囲にBさんがいるとき、その間に障害物がなければ目視できる。AさんがBさんを目視している時間の合計を求めよ、という問題。

実は出力に対する許容誤差がゆるゆるなので、時間をEPSずつ進めていって、実際に見えているかどうか判定するだけでも解ける。

これで一度通したが、ちょっとかっこ悪いのでまともにやる方法で解き直した。見える/見えないが変わり得るイベント点を列挙する方法。

イベント点は、

  1. 2人の間の距離がちょうどRになる
  2. 相手と進行方向とのなす角がちょうど45°になる
  3. 相手と自分を端点とする線分にちょうど障害物が入ってくる = 障害物の頂点が乗る

というのがあり、これらは一緒に考えるとやばいが、独立に考えると頑張って方程式を立てて解くことでわかる。

常に上記の状態を保つ=どのような解も方程式を満たすような場合は、イベント点ではないので気にしなくてよい。

イベント点が列挙できたら、時系列に並べて隣り合った時刻の中間の時間で見える/見えないを判定すればよい。

 

798問目: AOJ 2004 Data Center on Fire

火事になったN階立ての建物の各階から機器を運び出したい。火は一定時間で上下に隣接するフロアに燃え広がり、また別の一定時間で焼け落ち、機器も無くなる。M台のエレベータが同時に通信しながら稼働し、焼失する前に機器を運び出す。全てのエレベータはまだ機器が残っているうち最上階を常に目指し、機器が運び出しor焼失すると、最上階を切り替え目標を変える。いくつの機器を何分で運びだせるか？という問題。

ぶっちゃけ頑張ってただシミュレーションするだけの問題だけど、問題文がひどすぎで、曖昧な部分が多すぎる。

とかいう有様で、データセットを落として来なかったら解けなかったと思う。

問題文がまともなら実装がちょっとめんどいだけ。

今回解いた中で唯一無二のクソ問だったと思う。

 

799問目: 全自動円形掃除機

多角形の部屋の中にルンバがある。移動して掃除できる面積を求めよ、という問題。

これが解法を考えるのに一番時間がかかった(常に考えてたわけじゃないけど2ヶ月くらいかかってる気がする)

解法は、とりあえず近くの壁にぶつけてから壁に沿って動かす。

このとき、壁や角に接した点からなる多角形の面積に、円弧の部分の面積を足せば答えがでる……けどつらい。

基本的に、壁にぶつかるor壁の端につくまで直進させる関数と、1点(=部屋の角)を中心にルンバを回転させる関数を作って、ぶつかる度にどちらを使うべき状況かを判断してシミュレーションする、という感じの方針で書いた。

最終的には計算誤差によりacosに1よりわずかに大きな値を入れてしまいnanが返ってくるバグにずっとやられていた(まるで成長していない)。

 

800問目: Hashigo Sama

はしごグラフという特殊な形をしたグラフを木状に接続してできたグラフが与えられる。2彩色を考えた時、同じ色からなる連結成分の大きさがどれもkを超えないような彩色は何通りあるか、という問題。

最初、木状に接続しているという条件を見落としていて、最悪ほぼグリッドグラフじゃんやばすぎ、となっていた。

木状に接続しているという条件を考えると実は与えられたグラフは外平面グラフになっているため、木幅は高々2となる。

よって、木分解してその上でDPを設計するFPTが考えられる。

木分解&Niceな木分解への変換については、

http://www-imai.is.s.u-tokyo.ac.jp/~imai/lecture/GraphMinor.pdf

を参考にさせてもらった。ありがとうwata神。

グラフ全体の頂点数をN、木幅+1=バッグの最大の大きさをwとおくと、

DPのキーは、(1)木分解上のバッグのID O(N)通り、(2)バッグに含まれる頂点の塗り方 2^w通り、(3)頂点の接続関係5通り、(4)各頂点が含まれる連結成分の大きさ k^w通りとなる。

DPの情報伝播は1ノードで最悪時 k^wくらいかかるので、全体で O(2^w k^{2w} N)くらいになって、N=2000, k=8, w=3を代入すると約 4×10^9となりやばそうだが、接続する頂点同士は同じ色にならなければならない、などの制約から実際の探索空間はもっと小さくなる。

……と思ったけど実際はだいぶやばかったので、いろいろと枝狩りや定数倍高速化的な何かを頑張った。

 

おわりに

つらかった。