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

C++の練習を兼ねて, AtCoder Beginner Contest 034 の 問題C(単調増加) ~ 問題D (プレゼント) を解いてみた.

■感想.
1. 問題D は, 解答方針が, 全く見えなかったので, 解答を参照して, 解答を組み立てた.
2. Binary Indexed Tree について, そもそも知らなかったので, 後述の参照サイトを元に, サンプルプログラム(binary_indexed_sample.cpp) で, いったん動作確認してみた.
3. 組み立てた解答が, テストケースをほとんど通過しなかったので, 正解者 の コーディング を参照したところ, update関数で, tree[idx] の 更新処理 が 誤っていることが分かったので, 以下のように修正した.
[修正前]
値 k で 更新.

[修正後]
値 k と tree[idx] のうち, 大きい方で 更新.


本家のサイトAtCoder Beginnar Contest 038 解説をご覧下さい.
※感想として, 私見ではあるが, 以下の読み替えが必要となるように思われる.
解説(P.20): “列で1番目からk番目の最小値を求める操作” -> “列で1番目からk番目の最大値を求める操作”
解説(P.21): “update(i,a)を列のi番目をaで更新” -> “update(i,a)を列のi番目を a, BIT[i] の大きい方で更新”


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

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

■Binary Indexed Tree とは?

■参照サイト
AtCoder Beginner Contest 038
Fenwick tree.
Fenwick (Binary Indexed) Trees.
Binary Indexed Tree のはなし.

カテゴリーC++

コメントを残す

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

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