このページに添付されているデータは間違っている可能性があります!

問題の出典については Judge's Data のページを参照してください．

• 2004/Practice/夏合宿/2nd Day/Problem A - Prime Digital Roots
• 2004/Practice/夏合宿/2nd Day/Problem B - Ski Slopes
• 2004/Practice/夏合宿/2nd Day/Problem C - Space Ant
• 2004/Practice/夏合宿/2nd Day/Problem D - Rectangle Coloring
• 2004/Practice/夏合宿/2nd Day/Problem E - Easier Done than Said?
• 2004/Practice/夏合宿/2nd Day/Problem F - Match Maker
• 2004/Practice/夏合宿/2nd Day/Problem G - Magazine Delivery
• 2004/Practice/夏合宿/2nd Day/Problem H - Area Covered by Circles

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

• 講評
• A 簡単

• E 本線なら()の対応なども問うような問題になるだろう． 初期化の忘れに注意．

• D 交差判定して連結していくのがいい．
  • 交差判定の方法

縦横独立

四角形と点の内外判定を用いる 四角形上の各点を内外判定すれば，インターセクションが調べられる．

• F 2000年ソウル大会? Gokuriがライブラリ所持で一発．
  • Gokuri 男性を女性と結びつける． 衝突したら，女性の好きなほうを結びつけて，負けたほうを下位にまわしていく．

• H メッシュで切る．

モンテカルロ法 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でも可能?

お疲れ様でした...

• 2004/Practice/夏合宿/2nd Day/Problem A - Prime Digital Roots
• 2004/Practice/夏合宿/2nd Day/Problem B - Ski Slopes
• 2004/Practice/夏合宿/2nd Day/Problem C - Space Ant
• 2004/Practice/夏合宿/2nd Day/Problem D - Rectangle Coloring
• 2004/Practice/夏合宿/2nd Day/Problem E - Easier Done than Said?
• 2004/Practice/夏合宿/2nd Day/Problem F - Match Maker
• 2004/Practice/夏合宿/2nd Day/Problem G - Magazine Delivery
• 2004/Practice/夏合宿/2nd Day/Problem H - Area Covered by Circles

添付ファイルに対する補足 †

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）