C++ の動作確認をしてみた(651)

C++の練習を兼ねて, AtCoder Beginner Contest 142 の 問題E (Get Everything) を解いてみた.

■感想.
1. 問題Eは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 苦手な動的計画法の訓練を積めたので, 非常に良かったと思う.
3. 最初, TLE版で実装したが, 計算量の削減方法が分からず, dp更新式に渡す鍵情報を, AtCoder Beginner Contest 142 (解説プログラム)を参考に修正している.
4. 個人的には, 動的計画法に関する理解を, 深めることが出来たように感じた.
現状, TLE版 と AC版 との違いは, 本質的には, 鍵情報の捉え方の違いにあると理解している.
→ 具体的には, 鍵情報が, {宝箱1, 宝箱2, 宝箱3} だった場合に, TLE版では, {宝箱1}, {宝箱2}, {宝箱3}, {宝箱1, 宝箱2}, {宝箱1, 宝箱3}, {宝箱2, 宝箱3}, {宝箱1, 宝箱2, 宝箱3} の 7通りの鍵情報で, dp更新を行っているが, AC版では, {宝箱1, 宝箱2, 宝箱3} の 1通りの鍵情報で, dp計算を行っているため, 計算量に違いが現れたと理解している.
→ さらに, TLE版 と AC版 は, dp配列 の 途中部分は, 差分が生じるものの, 最終的に必要な情報は, すべての宝箱を, 開けることが出来るかどうか(および, 最小費用)であるため, 各鍵毎に, 常に, 1通りの鍵情報(ここでは, {宝箱1, 宝箱2, 宝箱3})を見れば十分という点について, なるほどと, 改めて感じた.
5. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

本家のサイト AtCoder Beginner Contest 142 解説 の 各リンク を ご覧下さい.

■C++版プログラム(問題E/TLE版).

■C++版プログラム(問題E/AC版).

■参照サイト
AtCoder Beginner Contest 142
AtCoder Beginner Contest 142 (解説プログラム)

カテゴリーC++

コメントを残す

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください