ABC014を解いてみた

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は応用が効きそうですし覚えておきたいです。