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

C++の練習を兼ねて, AtCoder Beginner Contest 130 の 問題D (D – Enough Array) を解いてみた.

■感想.
1. 苦手な DP の訓練となったと思う.
2. 解答を見る前に, 解けたので, 及第点は取れたと思う.

本家のサイトABC 130解説をご覧下さい.

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

■参照サイト
AtCoder Beginner Contest 130

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

C++の練習を兼ねて, AtCoder Beginner Contest 132 の 問題F (F – Small Products) を解いてみた.

■感想.
1. 方針も見えず, 解けそうに無かったので, 解答を参考に実装した.
2. 解説上, N の 平方数 を 考えて, DP高速化 を 図る必要があると指摘があり実装したが, DPの組み立て方で, 非常に苦労した.
3. 実装終わったものの, AC版 とならなかった(※必ず, テストケース 03.txt, 12.txt で, WA版 となる).
4. 考えても分からなかったので, 正解者のソース を, 色々眺めていたところ, “N の 平方数 に 1 を 加算する必要がある” ことが判明したので, 修正後, 再提出して, AC版 と なった.
5. AC版となったものの, “N の 平方数 に 1 を 加算する必要がある” ことの理由が分からないため, とりあえず, 解法パターンの一つとして暗記しておくことにした.

本家のサイトABC 132解説をご覧下さい.

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

■参照サイト
AtCoder Beginner Contest 132

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

C++の練習を兼ねて, AtCoder Beginner Contest 132 の 問題E (E – Hopscotch Addict) を解いてみた.

■感想.
1. 方針も見えず, 解けそうに無かったので, 解答を参考に実装した.
2. 解説上, グラフを “3倍化” するというのが, 何のことか理解出来なかったが, 多分こうだろうという実装で, AC版まで行ったので, 大きなズレは無かったと思う.
3. TLE版 と AC版 を 掲載した.
※1. TLE版 を AC版 に 修正する訓練を積めたので, 貴重な経験となったと思う.
※2. AC版は, 50 ~ 51ms で通過したので, 十分高速化出来たと思う.

本家のサイトABC 132解説をご覧下さい.

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

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

■参照サイト
AtCoder Beginner Contest 132

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

C++の練習を兼ねて, AtCoder Beginner Contest 049 の 問題D (D – 連結 / Connectivity) を解いてみた.

■感想.
1. 解説上, Union-Find木について触れられていたので, Union-Find木 に 慣れるため, 解き直しした.

本家のサイトABC049/ARC065解説をご覧下さい.

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

■参照サイト
AtCoder Beginner Contest 049
素集合データ構造(Union-Find)

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

C++の練習を兼ねて, AtCoder Beginner Contest 002 の 問題D (D – 派閥) を解いてみた.

■感想.
1. 解説上, 最大クリーク問題について触れられていたので, 最大クリーク問題として解いたら, どうなるか見てみた.
2. 新しい知識が一つ増えたので良かったと思う.

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

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

■参照サイト
AtCoder Beginner Contest 002
Maximum Clique using backtracking in C

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

C++の練習を兼ねて, AtCoder Beginner Contest 132 の 問題D (D – Blue and Red Balls) を解いてみた.

■感想.
1. 仕切りに必要な, 赤いボール, 青いボールを考えてから, 残った赤いボール, 青いボールの並べ方に気付けたので, ACを取ることが出来たと思う.
2. 解答を見る前に, 解けたので, 及第点取れたと思う.
3. 課題としては, 復習が全く追い付いてないので, 考慮時間を限定して, なるべく多くの問題(※新しい知識の獲得)に触れるように方針の変更が必要と思った.

本家のサイトABC 132解説をご覧下さい.

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

■参照サイト
AtCoder Beginner Contest 132

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

C++の練習を兼ねて, AtCoder Beginner Contest 035 の 問題B (B – ドローン) ~ 問題C (C – オセロ) を解いてみた.

■感想.
1. 問題B は, ‘?’ を カウント後, 後から評価する点が面白いと感じた.
2. 問題C は, 遅延評価セグメント木 が 使えそうに見えたので, 下記, 参照サイトのライブラリをもとに, 提出した内容である.
※新しい知識となるが, セグメント木の理解が, 全然追い付いてないので, いろいろなパターンの問題に触れてみて, 本質をつかんでいく必要があると感じた.

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

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

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

■参照サイト
AtCoder Beginner Contest 035
遅延評価セグメント木をソラで書きたいあなたに

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

C++の練習を兼ねて, AtCoder Regular Contest 006 の 問題C (C – 積み重ね) を解いてみた.

■感想.
1. どこかで類題を見た記憶があったので, 探したところ, 本問も, yukicoder の No.4 おもりと天秤 に似ていることが分かった.

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

■参照サイト
AtCoder Regular Contest 006
No.4 おもりと天秤

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

C++の練習を兼ねて, AtCoder Regular Contest 005 の 問題C (C – 器物損壊!高橋君) を解いてみた.

■感想.
1. AtCoder Typical Contest 002 の A – 幅優先探索 に似ているように見えたが, 解けそうになかったので, ネット上の情報を探した.
2. 01-BFS で 解いていく方針が紹介されていた(※下記, 参照サイト)ので, もともとの幅優先探索のロジックを, 01-BFS用 に 書き換えた.
※但し, 書き換え前のコードを, ほとんどコメントアウトしているので, やや見づらくなってしまったように見える.
3. 新しい知識として, 01-BFS の アルゴリズム を 体感できたので, 非常に勉強になったと思う.

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

■参照サイト
AtCoder Regular Contest 005
01-BFSのちょっと丁寧な解説

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

C++の練習を兼ねて, AtCoder Beginner Contest 088 の 問題D (D – Grid Repainting) を解いてみた.

■感想.
1. どこかで類題を見た記憶があったので, 探したところ, AtCoder Typical Contest 002 の A – 幅優先探索 に似ていることが分かった.
2. 幅優先探索(BFS) を 復習出来たので, 良かったと思う.

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

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

■参照サイト
AtCoder Beginner Contest 088