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

C++の練習を兼ねて, AtCoder Beginner Contest 127 の 問題E (Cell Distance) を解いてみた.

■感想.
1. 問題Eは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 解説にある通り, X, Y方向で, 独立に数え上げできるという部分が, 面白く感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

本家のサイト AtCoder Beginner Contest 127 解説 を ご覧下さい.

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

■参照サイト
AtCoder Beginner Contest 127

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

C++の練習を兼ねて, AtCoder Beginner Contest 234 の 問題F (Reordering) を解いてみた.

■感想.
1. 問題Fは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 苦手な動的計画法の訓練を積めたので, 非常に良かったと思う.
3. 個人的には, 数え上げする種類数が, アルファベットの出現数にのみ依存するという部分が, 不思議な印象を受けた.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

■参照サイト
AtCoder Beginner Contest 234

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

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

■感想.
1. 問題Eは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. ダイクストラ法(応用版)の復習が出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

■参照サイト
AtCoder Beginner Contest 237

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

C++の練習を兼ねて, AtCoder Beginner Contest 085 の 問題D (Katana Thrower) を解いてみた.

■感想.
1. 問題Dは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 解説にあるロジック(投げ刀, 強い投げ刀, 振り刀に分けて考える)が, 非常に面白く感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

本家のサイト AtCoder Beginner Contest 085 解説 を ご覧下さい.

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

■参照サイト
AtCoder Beginner Contest 085

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++ の動作確認をしてみた(650)

C++の練習を兼ねて, 競プロ典型 90 問 の 問題025 (Digit Product Equation) を解いてみた.

■感想.
1. 問題025は, 方針が見えなかったので, (問題025 (Digit Product Equation) 解説) を参考に実装したところ, AC版に到達出来た.
2. 個人的には, 深さ優先探索の訓練を積めたので, 非常に良かったと思う.
3. 手強い問題が非常に多い気もするけど, 時間を見つけて, 引き続き, 取り組んでいきたいと思う.

詳細は, 本家のサイト(GitHub) 競プロ典型 90 問 の 問題025 を ご覧下さい.

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

■参照サイト
025 – Digit Product Equation
問題025 (Digit Product Equation) 解説

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

C++の練習を兼ねて, AtCoder Beginner Contest 238 の 問題E (Range Sums) を解いてみた.

■感想.
1. 問題Eは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. Union-Find木 の 復習が出来たので, 非常に良かったと思う.
公式のライブラリを拝借させて頂いてます.
3. 個人的には, 解説にあるロジックで, 整数列の和が, 特定できるか否かを判定できる点が, 非常に面白いと感じた..
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

■参照サイト
モノグサプログラミングコンテスト2022(AtCoder Beginner Contest 238)
Union-Find木

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

C++の練習を兼ねて, AtCoder Beginner Contest 032 の 問題C (列) を解いてみた.

■感想.
1. 問題Cは, 方針が絞り込めたので, AC版に到達できたと思う.
2. 実装に苦労した(※1. ~ 2.)ものの, 尺取り法 の 復習ができたので 非常に良かったと思う.
※1. 左端の要素を, 要素の積に反映する時に, (右側で反映済みのケースがあるので)二重に, 積を反映してしまわないように, 注意する必要がある点.
※2. 右端の要素が, 最終要素まで到達してしまった場合の処理も考慮する必要がある点.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

■参照サイト
AtCoder Beginner Contest 032

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

C++の練習を兼ねて, AtCoder Beginner Contest 238 の 問題C (digitnum) ~ 問題D (AND and SUM) を解いてみた.

■感想.
1. 問題C, Dは, 方針が絞り込めたので, AC版に到達できたと思う.
2. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

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

■参照サイト
モノグサプログラミングコンテスト2022(AtCoder Beginner Contest 238)

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

C++の練習を兼ねて, AtCoder Beginner Contest 020 の 問題C (壁抜け) を解いてみた.

■感想.
1. 問題Cは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 二分探索, ワーシャル–フロイド法 の 復習が出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

■参照サイト
AtCoder Beginner Contest 020