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++

コメントを残す

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

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