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

C++の練習を兼ねて, AtCoder Beginner Contest 084 の 問題C(Special Trains) ~ 問題D (2017-like Number) を解いてみた.

■感想.
1. 問題C は, いったん解いてみたが, ロジックのバグを直すことが出来なかったため, 解答を参照して, 復習した.
2. 問題D は, いったん解いて, TLE版まで持ってこれたので, 2017に似た数のテーブルを持たせたりして, 計算量を減らすように修正したところ, AC版に到達出来た.


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


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

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

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

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

■参照サイト
AtCoder Beginner Contest 084

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

C++の練習を兼ねて, AtCoder Beginner Contest 083 の 問題C(Multiple Gift) ~ 問題D (Wide Flip) を解いてみた.

■感想.
1. 問題D は, 解答方針が見えなかったので, 解説を参照して確認した.


本家のサイトARC 088/ABC 083 解説をご覧下さい.


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

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

■参照サイト
AtCoder Beginner Contest 083

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

C++の練習を兼ねて, AtCoder Beginner Contest 081 の 問題C(Not so Diverse) ~ 問題D (Non-decreasing) を解いてみた.

■感想.
1. 問題D は, 解答方針が見えなかったので, 解説を参照して確認した.


本家のサイトAtCoder Beginner Contest 081 / AtCoder Regular Contest 086 解説をご覧下さい.


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

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

■参照サイト
AtCoder Beginner Contest 081

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

C++の練習を兼ねて, AtCoder Grand Contest 002 の 問題C(C – Knot Puzzle) を解いてみた.

■感想.
1. いったん実装してみた(下記, WA版)が, ロジックの修正方法が分からなかったので, 解説を見て, 再度やり直ししたものである.
解説を見て, 本問についても, なるほどと感心させられた.


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


■C++版プログラム(問題C/WA版).
※テストケース(1_04.txt, 1_08.txt, 1_10.txt, 1_18.txt, 1_21.txt, 1_22.txt, 1_24.txt, 1_26.txt, 1_27.txt, 1_29.txt)で,
WA判定となった.

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

■C++版プログラム(問題C/AC版).
上記のプログラムが, 冗長に感じたので, 修正.

■参照サイト
AtCoder Grand Contest 002

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

C++の練習を兼ねて, AtCoder Grand Contest 002 の 問題B(Box and Ball) を解いてみた.

■感想.
1. 解答方針が, 全く見えなかったので, 解答を確認したところ, なるほどと感心させられた.


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


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

■参照サイト
AtCoder Grand Contest 002

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

C++の練習を兼ねて, AtCoder Beginner Contest 113 の 問題C(ID) ~ 問題D (Number of Amidakuji) を解いてみた.

■感想.
1. 問題C は, かなりゴリゴリ実装せざるを得なかった.
2. 問題D は, 解答方針が, 全く見えなかったので, 解答を参照して, 解答を組み立てた.
但し, おおよそ, このような内容を解答で説明されているだろう, との推測が多分に含まれていると思われる.


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


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

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

■参照サイト
AtCoder Beginner Contest 113

Python の動作確認をしてみた(1)

Python 3 の練習を兼ねて, AtCoder Regular Contest 002 の 問題B(割り切れる日付) ~ 問題C (コマンド入力) を解いてみた.

■感想.
1. C++で実装しようとしたところ, 実装方法で迷宮入りしたため, Python 3 で, 書き換えたものである(汗).

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

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

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

■参照サイト
AtCoder Regular Contest 002

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++ の動作確認をしてみた(45)

C++の練習を兼ねて, AtCoder Beginner Contest 034 の 問題C(経路) ~ 問題D (食塩水) を解いてみた.

■感想.
1. 問題C は, AtCoder Beginner Contest 042 問題D (いろはちゃんとマス目 / Iroha and a Grid) と類似しているように見えたので, この問題の解答をベースに, 対応した.
2. 問題D は, 解答方針が, 全く見えなかったので, 解答を参照して, 解答を組み立てた.
但し, おおよそ, このような内容を解答で説明されているだろう, との推測が多分に含まれていると思われる.
※例えば, テストケース s1.txt の WA回避対応で, 小数第10桁までを出力するように修正している.


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


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

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

■参照サイト
AtCoder Beginner Contest 034