後輩2人と, チーム Sophinyan として, ACM/ICPC 国内予選に参加しました.
6完/7問で, 7位(チーム順位). 順位表
| チーム順位 | 大学順位 | 解いた問題数 | 時間 |
|---|---|---|---|
| 7 | 6 | 6/7 | 26280 |
2つ目の出力ファイルのタイムスタンプは次の通り.
| A | B | C | D | E | F | G |
|---|---|---|---|---|---|---|
| 6'57 | 17'20 | 58'22(1WA) | 82'36 | 104'58 | - | 147'06 |
なんかこんないい順位になってしまっていいんだっけという感じだった.
アジア地区予選も頑張りたい.
以下, 時系列順の詳細.
見難くてごめんなさい.
僕の記憶容量3バイトくらいしかないので, 問題聞いたタイミングとか違うかも.
事前の打ち合わせとして,
という事を言っていた.
0'00
始まる.
A 読む.
えっまぁはい, これ A 問題なの, A にしてはむずいような.
0 円はありなのか, どっちなんだ. rep 書いたし, とりあえず 0 も含めておくか.
書く. サンプル合わん.
あぁ, やっぱ(当たり前だけど) 0 円は無しなのね.
よく見たら input に書いてあった. こんな所に書くの...
提出, AC.
あれ, なにこれヒントとか書いてあったのか, そんな下に書くなよ...
6'57
B と C を聞く.
C めんどそうだなぁと思いながら B を書く.
石に 0 が使われていないのはよいな. 初期状態全部埋まっているのも嬉しい.
適当に書いたら微妙に間違っていたので, どうせこの辺だろうと思った所を, バグらなさそうな感じに修正したら, サンプル通った.
提出, AC.
17'20
C の方針を立てる.
ヒストグラム的なのを作り, 枠の線分を持ち, 主にそれに円が接するか否かで二分探索すればよさそう.
書く. バグってる.
にぶたんなのに範囲二分してなかった.
修正. 提出. WA.
後で見たら, WA の原因は, 値がでかい所での判定をさぼっている事だった. (初期幅を適切に設定したら判定さぼれるだろーという脳内の判断だった)
死にたいなぁと思いながら, とりあえず D を聞く.
｢辞書順の最後はこうやれば解る｣
｢辞書順の最初もこうやれば出来る｣
というような事を聞いて, 確かに出来てるなぁと思う. これが想定解なら, ちょっと面倒そうな気がして, もうちょい進めておいて貰う.
E を聞く.
グラフで, 辺の上を動きながら取っていくような問題だと把握. 最小全域木かなんかごにょごにょする系? (蟻本の徴兵のヤツ思い出していた)
F もこの辺で聞いたかも?
C を思いついた.
どうせヒストグラムの枠を多角形と思った時の頂点の所が問題なので,
こいつらを超える時間の最小値を取ってくればいい.
書く. 提出. AC.
58'22
D を詳しく聞く.
とりあえず, 言われたようにやったら, 辞書順で一番最後のは出来た.
もう少し頑張ったら, 辞書順の最初の方を探索出来るようになった.
微妙に謎実装してたけれど, これ普通にそのまま dfs すればいいだけじゃんと思って綺麗に書きなおす.
これ意外に行けるんじゃね? と思って, 初めの 10 個くらいしか取ってきてなかった制約を外して入力喰わせてみる.
余裕で動いてるっぽいので, 適当に出力を 10 個までにするの書いて提出. AC.
82'36
E の問題をよく聞く.
この辺で G も概要を聞いたかも.
どうやるんだ, うーん, ぱっとわからんなぁと思いつつ, 更に聞いてるとどうやら木らしい.
それならまぁ(葉除いた)最遠点対で出来るね.
n=2 あたりがコーナーケースっぽい気がしたけれど, 3 点以上はあるらしい.
｢大体の場所は 3 重だよね??｣
｢端のほうは 1 重だよね??｣
とか確認しながら書く. 提出. AC.
104'58
G を詳しく聞く.
どうやら, 3 つの円盤が重ならない (共有点すら持たない) 制約があるらしい.
とりあえず,
｢p か q が少なくとも一つの円に含まれているなら, ｢どの円に含まれているか｣が一致するかの判定だけでよい｣
事を確認する.
あとは, 円の外側だけが問題.
要するに, 円同士が回りで色々くっついて囲ってたりするとやばいよねーという話.
これは, 円の中心を頂点, 交差している円の所に線分があると思った平面グラフで, p と q が同じ平面に含まれるか否かと一致しそう.
｢こういうのと一致しそうだよね?｣ と確認しつつ, 平面グラフと双対グラフのライブラリをひっぱり出し, ひたすら写経.
サンプル喰わせる. せぐふぉ.
何箇所か cout << __LINE__ << endl; を追加して場所を特定すると, vector の初期化忘れ.
修正してサンプル喰わせる. なんかおかしい.
よく見ると, 頂点の座標設定し忘れていた.
修正. 提出. AC.
147'06
残りは F しかない.
辞書順は判定さえ出来ればよいので, 判定ルーチンがあれば嬉しいという事は, 他の問題を解きながら話しておいた.
後輩たちが, ｢こうしたら出来そう｣みたいな操作のアイディアを書いてくれていたけれど, ｢それで出来なければ必ず無理｣というタイプっぽくなくて, どうしよう...
とりあえずサイコロライブラリを写経.
わからんので, とりあえず, ナイーブな dfs を書く.
全然実行終わる気配がないが, コンテストが終わりそう.
実はもう少し頑張っていたら出来たのかもしれないけど, そんなことないのかもしれない.
おわり.