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

C++の練習を兼ねて, AtCoder Beginner Contest 109 の 問題D(Make Them Even)を解いてみた.

■感想.
1. 下記 C++版プログラム(RE版) は, おそらくロジック的に間違ってないと思われるが, 時間内では, テストケース(C018_scrambled – C029_scrambled)で, Runtime Error となった.

2. Runtime Error の 原因としては, ネット上の情報で, “vectorは要素数が数万くらいになるとデータ構造がぶっ壊れる???” との指摘をされている記事があったので, vector を使ったことが原因と推測した.
※参照URL② にあるように, vector よりも 配列の方が, 処理は早いとのこと.

3. コンテスト終了後に, 解説を見たところ, 一筆書きによる解法が紹介されていたので, 下記 C++版プログラム(AC版) のような形で実装したところ, 全テストケースを通過出来た.
※但し, 一筆書きによるコイン情報の保存方法に, 一次元配列を使ったが, 不慣れなせいか, これを一筆書きの順で保存するロジックを構築するのに, 膨大な時間を使ってしまった(汗).


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


■C++版プログラム(RE版)


■C++版プログラム(AC版)


■参照サイト
【参照URL①】AtCoder Beginner Contest 109
【参照URL②】vectorの要素数上限とか

カテゴリーC++

コメントを残す

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

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