はじめに
AtCoder Beginner Contest 273の復習記事です。
記事におけるScanner
クラスは、自作の入力クラスです。
コンテスト
https://atcoder.jp/contests/abc273
問題A
制約がN<=10
と小さいので、下のような関数で解くことができます。
しかし、何度も同じ関数が呼ばれてしまい、F(10)
のときには10!
回もの関数が呼ばれてしまいます。
そこで、あらかじめF(1), F(2), F(...)
の計算結果をメモしながら次の値を求めていくことで、計算量を大幅に削減することができます。
問題B
四捨五入する桁(10^k
の桁)の値をv
としたとき、v = X / 10^k % 10
で求めることができます。
そして、v
が4以下
のときX
の10^k
の桁を0
にします。
あるいは、v
が5以上
のときX
の10^k
の桁を0
にし、10^(k+1)
の桁を+1
します。
問題C
A
の値はとても大きなものもありますが、求められるものは大小関係なので、A
を重複なしでソートしたときの順番を圧縮したものとして扱うことにします。
これにより、数値の種類数-数値を圧縮した時の順番
がその数値よりも大きな数の種類数を求めることができます。
そして、全てのA
においてその種類数を数え上げることで答えを求めることができます。
問題D
行と列の移動はそれぞれ独立しているので、行を移動するときの列、列を移動するときの行ごとにブロックの座標を管理し、移動途中にブロックが存在するかをLowerBound
等で調べることで、クエリ当たり時間計算量O(logN)
で求めることができます。
下記のプログラムは考え方はあっていると思いますが、テストケースが4つ落ちています。どこがバグかわからないです...
修正しました。
番兵に指定したrows
とcols
、cr
とcc
のH
とW
が逆でした。