KOTET'S
PERSONAL
BLOG

#atcoder AtCoder Beginner Contest 174

Created:
#atcoder #dlang #tech

全6問の新形式になってから初の全完!

結果

全完81分で589位。 ここ最近レートが上がりつづけているので青帯になる日も近いかもしれない。

コンテスト成績証 - AtCoder

A - Air Conditioner

$30 \leq X$を判定する。 atcoder-toolsの入力コードとyes/no自動生成とがとても役に立った。

提出 #15589015 - AtCoder Beginner Contest 174

B - Distance

$D \leq \sqrt{X_i^2 + Y_i^2}$ を満たす点を数えるのだが平方根を求めると誤差がこわいので、 $D^2 \leq X_i^2 + Y_i^2$に変形して整数演算に収まるようにする。

提出 #15594414 - AtCoder Beginner Contest 174

C - Repsept

$a_1 = 7, a_{N+1} = a_N * 10 + 7$を計算して条件を満たすものを探す。 $a_N$は大きくなるので$K$で割ったあまりで計算する。 コンテスト中は直感で書いているのでこれで正しく動く確信がない。 実際条件が詰めきれずに2WA。

提出 #15611165 - AtCoder Beginner Contest 174

D - Alter Altar

ある場所を境に左側はすべて赤、右側はすべて白になる。 境界の位置を固定したとき、左側にある白と右側にある赤を入れ替えて、残ったものの色を反転操作で変えるのが最適になる。 累積和を使えばこの問題は$O(1)$で解けるので、境界の位置を総当りすれば$O(N)$で解ける。

提出 #15615020 - AtCoder Beginner Contest 174

E - Logs

あらかじめ答え$x$がわかっていれば、$x$より長い丸太を端から$x$づつ切っていけばよく、 そのように切れば長さが小数の丸太を作らずに$K$回の切断で最も長い丸太の長さを$x$にできる。 $x$が与えられた時に何回の切断でそれを実現できるかは各丸太の長さを$x$で割って(切り上げ) やれば$O(N)$で求められる。 あとは切断回数が$K$以下になる最小の長さを2分探索で求めてやれば$O(N\log{N})$で解ける。

提出 #15619219 - AtCoder Beginner Contest 174

F - Range Set Query

なんかこういう問題見たことあるなと思って「種類数 競プロ」とかでググったら そのままのアルゴリズム が出てきた。 クエリを$r$の昇順でソートしてやると、BIT(Binary Indexed Tree) 等の区間和を高速に求められるアルゴリズムを使うことで$r$が小さいものから順に求められる。 典型問題をそのまま出してきた感じっぽい。

提出 #15630857 - AtCoder Beginner Contest 174