一日目の問題に関するメモ，コメント
Staindings:http://192.168.1.3/acm-icpc-2004/pc2/day1/full.html
問題自体と，問題を作成した際のメモ †
メモ †
解き方 †
- 必ずペアプログラミングGNC
- 解く順番に関して
- A問題に二人で手をつけて，残りの一人で B-E を見る(多数)
- 最初に全部の問題に目を通す
スタッフからのコメント †
A(松崎) †
B(松崎) †
- ノード数の見積もりはたかだか14^4なので，やはり全探索可能
- 図形まわりはライブラリを準備すると楽だ*2
- 点が三角形*3の内部にあるか，条件がそろえば簡単に判定する方法がある(笠原→レクチャー/幾何?)
C(松崎) †
- 過去問ではなく，研究室で行われたコンテストで出題された問題の改造
- 行って帰ってのDPでは，コインの最小公倍数に比例するオーダの計算が必要で，非現実的
D(三廻部) †
- ４パターンの部品だけ準備して，それを利用して解くのが楽
- 各格子について，４つの頂点のどれに円の中心があるかでパターンわけ(GNC)
- 問題を大きくすることで，平面全体をオンメモリの配列に入れられないようにした(松崎)
- 整数でなかったとしたら，どんな問題になるだろう？
E(三廻部) †
- 英文が長いので大変だが，アルゴリズム自体は単純
- 各通路に関して危険度を計算して，その後はダイクストラ法*4で最短経路を求める
国内予選(E,F)の議論 †
国内予選問題E †
- 溢れるのを気にせずに水を注いで，平衡状態になるまで隣のセルに水を流すのが楽らしい.
- 仕切りの高さが高い順に二分木を構築しておくと水の入れる場所が探しやすいけど後が複雑になってしまう？
国内予選問題F †
- 強弱関係は1，同値関係は0or2を重みとしたグラフを考えてWarshall-Floydを使うと楽.
- 問題を解釈するのに時間がかかる問題… 日本語訳の方がかえって分かりづらい？
議論 †
- 本番は英語キーボード(HHKかMSキーボードのどちらかを選択)．
- グローバル変数は使う人と使わない人がいるみたい．
おすすめの本とか †
- Gokuri-Squeeze
- STL標準テンプレートプログラミングによるC++プログラミング David R. Massar?
- 自作ライブラリ(膨大!)
- K&R ギリシャ語版(オリンピックだし)
- Team86
- Introduction to algorithm
- アルゴリズムデザインマニュアル
- GNC
- STL/入出力関連のネット資料を印刷したもの
- Effective STL
- Computer Geometry
- Algorithm C++
- 大学への数学 (接線，交差判定とか幾何系のプログラムを書くときに参照)
- 情報系の人は線形変換で図形を回転させるとかいった発想はしにくい？
- MaximumTNT
- アルゴリズムC++
- C言語による初めてのアルゴリズム入門
- 方眼紙を持っていくと便利!
- combat
- 殊玉のプログラミング
- プログラミング言語C
- 計算機プログラムの構造と解釈
- プログラムプロムナード
- 情報処理学会誌に連載されている記事
- ネット上で無償で公開されています
- たまにSchemeのコードがまぎれているので注意
ライブラリ作ってる？ †
- 去年のWorld Finalsより任意書籍の持込は不可に．ただし25ページ以内のpdfを提出すると主催者側で印刷して渡してくれる．
- 泉さん・三廻部さんがWorld Finalsに持っていったpdfを近日中にupしてくださる模様
コメント †
Gokuri_Squeeze