思考のジャンプ幅が狭いなら,飛ぶ回数で補えばいいじゃない!!

非情報系30歳が競技プログラミングやWeb開発を始めるとどうなるか?

いろはちゃんコンテスト Day4 B - 叫び声

f:id:hiro_kato:20190510233855j:plain

目次

結論

  • 単一の電車もしくは走るを選択したときの所要時間を計算して,その最小値を求める.

はじめに

  • AtCoderの問題を復習しています.

  • 公式解説や上位陣による解説ブログを読んで,自分に足りなかった部分や得られた知見を自分なりに消化してアウトプットしようと思います.

想定読者

  • 筆者と同じくらいのレートの方:失敗談・回り道をみて,共感していただける部分もあるかもしれません.

  • コンテストのwriterの方:サンプル n=1ではありますが,レート茶色上位~緑下位の参加者がつまづく可能性があるポイントを知っていただく機会になるかもしれません.

記事の狙い

  • 丁寧でわかりやすい解説記事がたくさん公開されているため,解法そのものについての記述は少ないと思います.

  • ACに至るまでにどうしてそのような発想に至ったのか,考察や実装で試行錯誤した過程(=失敗談や回り道)を重視しています.

  • また,得られた前提知識や着眼点について,今後応用できるように抽象化・言語化していきます.

  • 間違いや勘違いなどがございましたら,ご指摘・ご指導いただけると幸いです(大歓迎です).


問題のリンク

B - 叫び声 (400点)

ACに至るまでの考察・実装のコツなど

  • 制約条件から,それぞれの移動手段を使ったときの所要時間が,最初の状態から単調増加することを図も併用して確認.

  • 移動手段は変えず,電車の乗り換えも不要と判断した.なぜなら,最初から最短時間となるような移動手段を選択すればよいため.

  • 単一の電車もしくは走るを選択したときの所要時間を計算して,その最小値を求める.計算量は, O(N)

提出コード

試行錯誤した過程

  • 制約条件の上限値がとても大きい.計算量が O(1)でないとTLEになる.

    • 400点問題≒DP(動的計画法)の印象があったものの,どのように状態を考えればよいか分からず.

    • 問題文で電車の乗り換えを C回,もしくは電車と走る駅数をそれぞれD, E回などという指定があったら,貪欲法では無理そう.幸いなことにも?,そのような制約条件はなかったため,DPは却下.

  • 電車を乗り換えたり,電車と走るのを組み合わせる必要があるのではないか.

    • 問題文から所要時間が,単調増加する.図も書いて確認してみた.

    • 乗り換えや移動手段を変えることで,最短時間となるような移動を目指すなら,最初からそのような条件を満たすように移動すればよさそう.ただし,前提条件として所要時間が単調増加する場合に限られる.

    • 最終的な状態だけが問われていると判断して,この仮定を却下した.

得られた知識・知見

  • 問題文から得られる情報を図として書いてみる.

  • 最終的な状態にだけ着目して,途中経過はスキップできないか?

  • 反例がないかを列挙する.

  • 順位表から得られる情報もうまく活用する.

感想

  • 3か月前なら配点を見て解けないと思っていた問題がACできたところは,成長していると思います.

課題

  • 動的計画法の基礎を学習する(∞回目).
  • 当日中に記事を書ききれるように,時間を確保する.

参考

記事を執筆された皆さまへ: 掲載不可の場合はお手数をお掛けしますが,@k_hiro1818までご一報ください.

更新履歴

  • 2019/05/10 作成
  • 2019/05/11 更新