読者です 読者をやめる 読者になる 読者になる

ferinの競プロ帳

競プロについてのメモ

ABC014を解いてみた

ABC 競技プログラミング

abc014.contest.atcoder.jp

A問題

 (a%b == 0) のとき0を出力し、そうでないとき(b-(a%b))を出力しました。A問題でif文使うの珍しい気がしました。

B問題

 x = bin(x)[2:][::-1] として配列で扱いました。あとはforループで1文字ずつ確かめていって(x[i] == 1) であったらa[i]を答えとなる変数に加えて、出力しました。

C問題

 全ての端点について調べる方法しか思い浮かびませんでした… 計算量的に部分点の制約しかクリアできません。累積和の応用法であるいもす法(by解説)で実装しました。
いもす法 - いもす研 (imos laboratory)

D問題

 追加辺(a, b)に対して始点a、終点bで全探索する方法しか思い浮かばなかったです… LCAを使ったアルゴリズムは覚えておこうと思います。

雑感

 2進数の扱い方は勉強になりました。いもす法やグラフのLCAは応用が効きそうですし覚えておきたいです。