ICPC 国内予選練習会 2012/05/27 hos.lyric A. 余りが足りない? • 解法の例: 条件を満たす数を順に生成して いって,xi の中にない最小のものを答える • B = 0 の場合に注意 (サンプルにある) • データにミスがありました,申し訳ありません – N を N - 1 と書いていてバグが入りました…… B. カラフルなパネル • 白いパネルはすべて同じ色に変えるとしてよ い • DFS などで数える C. 予定は未定 • 区間を右に 10 分広げれば典型的な区間ス ケジューリング問題 – Greedy or DP D. 広がっていこう • うさぎたちの位置を状態として Dijkstra • うさぎが多すぎるときすぐ -1 を出力するように すると速くなる – 国内予選は案外データセットが大量に入っている 傾向あり (1 番目の入力を覗いて確認しよう) E. 高階関数のお勉強 • 次のいずれかしか作れないことがわかる: – (B (B ... (B A) ... )) – (B (B ... (B B) ... )) • 文字列の各区間に対してどれが何通り作れ るか求める – O((長さ)5) – 3 k - 2 文字でない区間はスルー,短い区間で作 れる関数は少ない,などで定数が小さくなる F. 集団引越し計画 • 最小カット – pi,j は最大のものから引いておいて最小化問題に p'i,2 p'i,3 p'i,4 p'i,1 ∞ ∞ ∞ ∞ c d l 3 cl d 2 s p'j,1 cl d1 p'i,4 t p'i,2 p'j,3 ∞ ∞ ∞ ∞ G. にちようびのおでかけ • 正方形 [-r, r] × [-r, r] で区域を求めてあとで 円との共通部分の面積を求める • 1 番目・ 2 番目に近い店を決めれば O(n2) 回 の凸多角形切断で区域は求まる • 順番を工夫すると同じ切断をたくさんするの でまとめることができ,2 番目の店を決めて分 割統治すると O(n log n) 回の切断でできる • 別解: O(n log n) か O(n2) の Voronoi 図を使う
© Copyright 2024 ExpyDoc