![D問題 解説
? 各頂点に対して、距離をDPで求める
– 高さ0は距離1
– 高さjはdp[j] = min(dp[j], dp[i] + dist(point[i],
point[j]))
? 実際は左右の頂点が存在するので、両側について
考えなければならない
? もちろんdist関数は単純な距離だけではなく、交差
判定を行わなければならない。
– 更新回数はV^2 / 2程度？](https://image.slidesharecdn.com/arc001-131223094636-phpapp02/85/AtCoder-Regular-Contest-001-11-320.jpg)
AtCoder Regular Contest 001
- 1. AtCoder Regular Contest 001 解説 AtCoder株式会社 代表取締役 高橋直大
- 2. A問題 問題概要 ? 1,2,3,4の４種類の文字で書かれた文字列が 与えられる。 ? 一番多い数字の個数と、一番少ない数字 の個数を出力しなさい。
- 3. A問題 解説 ? プログラムの一例は以下の通り – 標準入力から文字数を読み込む – 標準入力から文字列を読み込む – 要素数４の配列を用意する – 全ての文字に対しループで判定を行う ? 文字に対応した配列をインクリメントする – 配列の中で、最小値と最大値を出力する ? 適切な関数が存在しない場合はループで取り出す
- 4. B問題 問題概要 ? エアコンの設定温度をA度からB度に変更 したい ? １回ボタンを押すことで変更可能な温度 は、１度、５度、１０度の３種類。上に も下にも変更できる ? ボタンを押す必要のある最小回数を出力
- 5. B問題 解説 ? 解き方は複数存在する – 幅優先探索を用いる – 差が10度以下になるまで、10度の変更をする。 10度以下は埋め込み – 全部の温度に対して最短距離をワーシャルフ ロイドなどで計算してしまう ? どれを書いても良い
- 6. C問題 問題概要 ? 8-queen問題の、3つのクイーンを置いた状 態が与えられる ? 残りの5つを配置せよ。もし不可能な場合 はNo Answerと出力せよ。
- 7. C問題 解説 ? 全通り試すのが簡単に出来るため、深さ 優先探索で良い。 – 同じ列や行にすでに２つ置かれていたら失敗 – 置かれていないのであれば、残った５行に 残った５列を割り当てる。この割り当て方は 5!通り ? それぞれのパターンに対して、8-queenの条件を満 たしているか確認する
- 8. D問題 問題解説 ? 右図のような道が与えられる ? 道の上しか通ることが出来ない ? 最短経路を求めなさい – 幅は1,000,000以下 – 高さは200,000以下
- 9. D問題 解説 ? 最短経路ならダイクストラ法？ – 頂点Vに対して、O(V^2)かO(ElogV)程度かかっ てしまう。 – V=400,000, E=V^2なので、どちらも間に合わな い ? 実際は交差しないかどうかを判定しないといけな いのでさらに計算量がかかる。愚直実装でO(V^3) ? グラフの特徴を利用して、なんか工夫し ないとだめ！
- 10. D問題 解説 ? 考察してみよう！ – 頂点と赤?青の点以外は考える必要がない – 後ろに戻ることは絶対にない ? ってことは動的計画法でいけそう？
- 11. D問題 解説 ? 各頂点に対して、距離をDPで求める – 高さ0は距離1 – 高さjはdp[j] = min(dp[j], dp[i] + dist(point[i], point[j])) ? 実際は左右の頂点が存在するので、両側について 考えなければならない ? もちろんdist関数は単純な距離だけではなく、交差 判定を行わなければならない。 – 更新回数はV^2 / 2程度？
- 12. D問題 解説 ? 範囲を絞って枝刈り？ – これ以上先に絶対行けない場合は更新を止める ? ステップを更新するごとに、行ける角度などが狭まっ て行く ? 交差判定もこれだけで十分 – 余計な頂点は無視 ? 明らかに窪んでいる点や、直線になっている点など ? 最悪ケースはそれでもO(V^2) – これでは通らない ? データセットが弱かったようで、かなり高速化すると 通ってしまうケースもあるようです。ごめんなさい＞ ＜
- 13. D問題 解説 ? 基本的なアイデア – 凹んでる场所に行く必要は絶対にない
- 14. D問題 解説 ? 基本的なアイデア – 凹んでる场所に行く必要は絶対にない – であれば、持つべき情報は、以下のような形 のデータ ? 現在位置から、凹まずに行ける経路を左右独立に 持つ
- 15. D問題 解説 ? 更新方法 – 以下のような顶点が与えられた场合
- 16. D問題 解説 ? 更新方法 – 以下のような顶点が与えられた场合 – 角度が浅いものを消してしまい、更新してい く
- 17. D問題 解説 ? 更新方法２ – 以下のような顶点が与えられた场合
- 18. D問題 解説 ? 更新方法 – 以下のような顶点が与えられた场合 – 交差してしまう？
- 19. D問題 解説 ? 更新方法 – 以下のような顶点が与えられた场合 – 交差した時は、交差してしまった方を確定さ せ、現在位置を変更する
- 20. D問題 解説 ? 先ほどの様な更新方法をした場合 ? どちらが内側にあるかを調査するごとに、 考えている頂点が１つ減る – よって、この回数はO(V)で良い。 ? これで十分な証明は各自考えてくださ い！