このページに添付されているデータは間違っている可能性があります!
問題の出典については Judge's Data のページを参照してください.
STANDINGS:http://192.168.1.3/acm-icpc-2004/pc2/day2/full.html
二日目の問題に関するメモ・コメント
アナウンスすること †
二日目の厳密なルール:
- プリンタの使い方
- 質問の仕方(事務的なこと、技術的なこと、マシントラブル、...)
- スタッフとの会話言語
- アナウンスの言語
- 外部ネットワークアクセス
- 辞書
終わって
- 解答経過
- Gokuri
A > D,E (C,F,G,H,読みながら)
Fは持っているライブラリそのまま > G
Cではまり>H >C > B
- horizon
Aも2人で > E > C > F > H > 残ったBとG > 完答
- Maximum-TNT
Aも2人で@9分! > D > E > C >F > G > H > B(DP失敗) > おにぎり
- GNC
Aも2人で > E > D > F > C(はまりながらも) > H > G
- combat
一人が問題をひたすら読む読む。
A > E > D > C,E(苦戦) > H(モンテカルロ法でAccept)
- team86
問題を全部読むより先にわかる問題から解く.
A,D,E > G > F(O(n^n)に断念) > B
- qoo_
A > E > D(はまりで時間がかかる) > Bを解こうとするも挫折orz
- E
本線なら()の対応なども問うような問題になるだろう.
初期化の忘れに注意.
縦横独立
四角形と点の内外判定を用いる
四角形上の各点を内外判定すれば,インターセクションが調べられる.
- F
2000年ソウル大会?
Gokuriがライブラリ所持で一発.
- Gokuri
男性を女性と結びつける.
衝突したら,女性の好きなほうを結びつけて,負けたほうを下位にまわしていく.
モンテカルロ法
2,3分でTime Limit
- G
L1 > L3 (配達せず) > L2 も可.
Floydで最短経路を一通り求めておいて,Dijkstra
- C
与えられたすべての点は通る.
進行方向左側の角が一番小さくなるような進み方をすればよい.
- 注意
- 同一直線上の点は近いほうからたどる.
- y(またはx)方向の同一直線(x = k)上には点が2つ以上は存在しない!
atan()よりもatan2()を用いる.
atan2は象限判定まで行ったうえで答えが返ってくる.
- B
DPは不可?
探索
effortとdistから枝刈するのは難しい.
枝を刈らないとTime Limit Exceeded.
- ポイント
- NP問題とわかったら逆に値は大きくないと検討をつけてみる.
DPでも可能?
お疲れ様でした...
添付ファイルに対する補足 †
check-F.cpp の中に“Is Woman z prefers Man i to Man wp[j]?”という実に無茶苦茶な英文が書いてありますが,正しくは“Does Woman z prefer Man i to Man wp[j]?”です.あまりにひどい英文なのでファイルを修正しようかとも思いましたが,自分への戒めのために残しておきます. -- 泉(24 Sep 2004)