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

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

■感想.
1. 数列の要素を, 問題文の操作で並び順を変えると, 膨大な計算量(O(nの2乗)) が必要となるが, 規則性を見つけると, 計算量が O(n) の 3倍程度 まで, 削減できる点が, 面白いと感じた.
2. 解説を読んだところ, 標準ライブラリ std::deque があるとのことで, 大変参考になったと思う.
3. 標準ライブラリ std::deque を使ってみたところ, 実装が, よりコンパクトにまとまって, びっくりした(汗).


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


■C++版プログラム.

■C++版プログラム(std::dequeを使った場合).


■参照サイト
AtCoder Beginner Contest 066

カテゴリーC++

コメントを残す

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

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