2009/Staff
野田久順 †
東京工業大学集積システム専攻博士課程2年
模擬練習会解答例集 †
前年度模範解答集はこちら2008/Staff/野田
模擬国内予選 2009 †
模擬国内予選の防衛ラインとして設置された幾何問題です。
ある方から説明スライドの内容が不十分であるとお叱りを受けてしまいました。
皆様に御詫びするとともにこの場にて補足いたします。
あらかじめ線分同士の交差判定ルーチンと線分が交差していた場合の交点を求めるルーチンを用意してください。
これらはベクトルを用いる方法、複素数を用いる方法、方程式を用いる方法等さまざまな方法がありますが、
コーナーケースに耐えられるものである必要があります。
特に二つの線分が平行な場合、一直線上に並んでいる場合、一部が重なっている場合にも
正しい解を出力するルーチンを用意しておいてください。
続いて問題の解答手順は以下のとおりです。
- 頂点を入力する
- 各頂点について対角線の長さが2Rとなり、各辺が45度傾いた正方形を線分の集合に加える
- 2で加えた正方形について、海岸線に沿って動かしたときの各頂点の奇跡を線分の集合に加える
- 全ての線分を交点で分割する
- 4の各線分について元の海岸線からマンハッタン距離でR以下のものを取り除く
- 5の各線分について下の海岸線の内側に無いものを取り除く
2.、3.では浸食後の海岸線の候補となる線分を列挙しています。
4.は線分アレンジメントと呼ばれる処理です。
全ての線分の交点を列挙した後、x座標順にソートし、
各線分についてどの交点を通るかという判定をしていきます。
5.は非常に難しそうに見えますが、各線分の中点と元の海岸線とのマンハッタン距離を求め、
距離がR-ε以下なら取り除くという方法で解決できます。
点と線分のマンハッタン距離は「x軸に非並行かつ共通のy座標を持つ場合は点から線分にx軸に平行な線分を引いたときの線分の距離」
「y軸に非並行かつ共通のx座標を持つ場合は点から線分にy軸に平行な線分を引いたときの線分の距離」「点から両端との距離」
の4つの値の最小値となります。
何故こうなるかは考えてください。
6.は点と多角形の包含判定と呼ばれる処理です。
この処理についてはここでは詳しく述べません。各自お調べください。
N<=100ですのでO(N^3)のアルゴリズムで十分に間に合います。
是非挑戦してみてください。
夏合宿 2009 †
Day 2 Problem A - Infected Computer - 感染拡大 
infected.nodchip.cpp †
やることがわかったら書くだけの問題です。目標は5分でしょうか・・・。
Day 2 Problem G - Defend the Bases - 君達の基地は、 全てCATSがいただいた。 defend.nodchip.cpp †
ほとんどのチームが閾値Rを二分探索+最大流で解いたようです。
Day 3 Problem D - Luigi’s Tavern - ルイージの酒場 luigi.nodchip.cpp †
問題のタイトルは大事です。ニ○ニ○動画のドラクエ関連動画を見てこの問題を作りました。
慣れている人であれば一目見て最大流の問題だと気づけるのですが、
グラフが若干複雑で、うまく組めるかどうかが勝負の分かれ目だったと思います。
Day 3 Problem I - Wind Passages - 風の回廊 wind.nodchip.cpp †
タイトルドリブンで作ったのはいいのですが、
元のタイトルを覚え間違っていたことが後から発覚したという・・・。
ググって見たら某有名アーティストの楽曲が引っかかりました。
模擬地区予選 2009 †
問題のネタ探しのためにWikipediaを眺めていたところ目にとまり、そのまま問題にしてしまいました。個人的にはこういったadhoc系のプログラムは神経が磨り減りそうで苦手です。本番前に問題タイトルを見てググった人、怒らないので正直に手を挙げなさい。
夏合宿2009で出題したTatamiの兄弟問題を作ろうとしたところ、「これはむしろ布団」と言われ、布団になりました。2-SATの問題が久しぶりだったためか、予想より解答チーム数が少なかったです。
前々からシューティングゲームを題材にした問題を作ろうと思っていたのですが、思うような難易度調整が出来ず、今回やっと納得の行く難易度の問題に仕上げることが出来ました。レーザーを予告線からR+r+ε膨らませるのがポイントです。
ねこさんです。かわいいです。DAGの最長パスを求める部分にダイクストラ法のようなアルゴリズムを使っているのですが、本来であればトポロジカルソートとDPを使用するべきです。このコードでも十分な速度が出るのですが、最悪ケースで時間計算量が(N^2logN)となるため、避けたほうが無難です。
JAG Winter Contest 2010 †
Problem I - Train King - 電王 (審判団のソースコードにバグが発見されました。以下のソースコードは正しい解を出力しません。近日中に修正いたします。)train.nodchip.cpp †
2年ほど前に原案だけ提案したものの、スタッフ内で誰も解き方がわからずにお蔵入りになりかけていた問題です。高橋さんにより解法が提案されました。まずは列車のダイヤグラムを考えます。ダイヤグラムは自然にグラフとしてみることができます。ここでAからBに向かう列車のエッジはコスト-1容量Ci、BからAに向かう列車のエッジはコスト0容量Ci、上から下向きのエッジはコスト0容量∞とし、Aの最初の頂点からBの最後の頂点への流量1の最小費用流を求めます。これは主人公がAからBに1回荷物を運ぶと、総コストが-1される仕組みになっています。最終的に出た総コストに-1を掛けたものが答えとなります。負の閉路が出るためベルマンフォード法による負閉路消去が必要です。
