ICPC国内予選2015 参加記
FinalZukkyというチームで出ました。
全体８位でした。
いつもの常勝セリフを言いたいところだが、あまりにも空気だったのでやめよう。
- 開始前
- とん八で勝利のカツを食う。
- 12:15 集合
- 練習セッションで全完
- 13:00 ~ 15:00 マッサージチェアで惰眠をむさぼる
- 15:00 勝利のレッドブルとアルフォートを購入
- twitterを鑑賞しながら予選開始を待つ
- 開始 16:30~
- 印刷フェイズ
- とりあいずB担当なのでBを読む、やるだけ例年より簡単そう
- Aが瞬殺されたので、Bをやる。通った。一安心。
- Cをdohatsuさんが実装している間にDの解法について考える。
- dpなんだけど状態多くない？
各コインの枚数を5枚持てばOKという路線でとりあいずZukkyさんが実装スタート。 - いつの間にかCが通っていた。
dohatsuプロの【いつの間にAC（バック・グラウンド・アクセプト)】が発動。 - Eを読んで問題文をdohatsuさんに伝える。
怒髪「ちょっと、考えてみる…」 - F問題を伝えられるもとりあいず保留。
- D問題WA,やっぱ、コイン５枚だけ持つのまずくない？ってことで再考察、よくないケースが存在していた。
- この辺りの考察でかなり時間かかった。3ACのまま残り１時間切っててかなり焦る。
- 実はよくないケースは気のせいっぽくて結局100円玉だけいっぱいもてばよくね？という結論に至った。（この時点で自由に上に両替可能=総和持てばよいというのに気づけばよかった）
- dp[100][5][2][5][2][511] + 遷移はコインを使う枚数を全探索でオーダーがすごいことに、5分くらいぶん回して答えが出たので出したら通った。
- いつの間にかEも通されていた。
怒髪プロの【バックグラウンド・アクセプト】発動２回目。 - 一気に5ACになって、一安心する。
- F問題を考察。辺をノードとして考える最小費用流では？と思いついてみたがサイクルで死ぬ大嘘解法で無駄に時間を浪費してしまい終了。
- 打ち上げ 20:15 ~
- 恒例のBigBoyで打ち上げ。
- Yutaka大先生に感謝して飯を食う。
- 二次会11:00 くらい
- あおやまでラーメンを食うという約束をしていたのに来たのは俺含めたった二人。
- 二玉食って胃に限界を感じる。
- 飯屋→飯屋はやばい
- 睡眠 04:30
先輩方のおかげで国内予選通過しました。お会い出来る方は筑波で会いましょう。
僕はそれまでに正戦力になれるよう頑張りたいです。
JOI春合宿day4 : Spaceships
問題文↓
http://imoz.jp/data/joi/2013-sp-d4-spaceships.pdf
ジャッジ↓
3: 宇宙船 (Spaceships) - 2013年 日本情報オリンピック春合宿 4日目 | AtCoder
問題概要
- N個の頂点とQ個のクエリがきます。
- 頂点を結ぶ辺の関係は森か木であることが保証されています。
- クエリは次の三種類です。
- 頂点a の親を頂点b とする。
- 頂点a とその親を結ぶ辺を削除する
- 頂点a と 頂点b のLCAを出力する。
解法
続きを読むAOJ 2454 : Repairing
問題↓
問題概要
- 線分が与えられます。
- source と sink となる点が与えれます。
- sorce から sink 線分に沿って水を流します。
- 途中に stopper という点がいくつか存在します。
- stopperを〆ることでそこで水の流れを止めることができます。
- 止まる水の流れる最小の距離を求めて下さい。
解法
続きを読むAOJ 1289 : Spherical Mirrors
問題↓
Spherical Mirrors | Aizu Online Judge
三次元の球体と直線の交点、反射のライブラリが出来たので乗っけます。
問題概要
- 三次元空間上にN個の球体があります。
- 原点(0,0,0)からレーザーが方向(u,v,w)に発射されます。
- 球体に当たるとレーザーが反射されるので
最後に反射する場所の座標を出力して下さい。
解法
続きを読むAOJ 2443 : ConvexCut
問題↓
最遅コードを叩きだしたので上げます。
間違いなく想定解法ではありません。
問題概要
- 凸多角形が与えられれます。
- 凸多角形の内部にある点のうち
そこから伸びる直線で多角形をカットした際に出来る2つの多角形の面積が等しいような点の座標を出力して下さい。 - ない場合は"NA"
- 頂点数 N = 50
解法
続きを読むAOJ 2326 : Number Sorting
問題↓
Number Sorting | Aizu Online Judge
問題概要
- [A,B]からなる数列が与えられます。
- それらの数字を任意の数選んで出来る部分数列を
辞書順ソートしたものと通常のソートをしたものの
順序が一致するようなものは何通りでしょう？
解法
続きを読むAOJ 1283 : Most Distant Point from the Sea
問題↓
Most Distant Point from the Sea | Aizu Online Judge
問題概要
- 凸多角形が反時計回りで与えられます。
- 凸多角形の内部にある点のうち
辺からの距離が最も遠い点との距離を出力してください。
