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

C++の練習を兼ねて, AtCoder Beginner Contest 218 の 問題G (Game on Tree 2) を解いてみた.

■感想.
1. 問題G は, 方針が見えなかったので, 解説(プログラム)を参考に実装して, AC版に持って行く方針を取った.
2. 苦手な動的計画法(木dp)の訓練を積めたので, 非常に良かったと思う.
3. いったん自力で実装してみたものの, AC版に到達できなかった.
-> 原因としては, 二つの multiset の 個数調整で, 実装が正しくなかったこと, dpへの中央値設定(のタイミング, 更新条件)などがあげられると推測する.
いずれにしても, dfsの実装を正しく行うことは, 相変わらず, 直観的に分かりづらく, 難しく感じる(※)ため, 継続して, 今後の課題になっていくと思う.
※dfsの終了条件, dp更新(条件, タイミング)などが, 難しく感じる原因の一つと推測する.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

■参照サイト
AtCoder Beginner Contest 218

カテゴリーC++

コメントを残す

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

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