AtCoder Beginner Contest 182 備忘録

AtCoder Beginner Contest 182 の備忘録です。

問題はこちら↓

AtCoder Beginner Contest 182 - AtCoder

今回はABCD4完でした。

・A問題:twiblr

SNSのフォロー数が 2 * ( フォロワー数 ) + 100 を超えないようにフォローする事ができるので、あと何人フォローする事ができるか求める。
上記の式で計算をしてそのまま出力すれば良い。

解答例(Python)
https://atcoder.jp/contests/abc182/submissions/17994742

・B問題:Almost GCD

A1~An までの数列が与えられる。ある正の整数 k のGCD度を数列 A の内 k で割り切れる物の数と定義した時、2 以上の整数の内GCD度が最大になるものを一つ求める。複数ある場合はどれを出力しても構わない。
数列 A の長さは最大でも100であり、また Ai≦1000 なので k が1000 を超えることはない(k が1000以上であれば Ai を割り切る事ができない為)、数列 A の各値を2~1000について全て試し割りをして割り切れたものの多い数を出力すれば良い。

解答例(Python)
https://atcoder.jp/contests/abc182/submissions/me

・C問題:To 3

各桁に0が出現しないような正の整数 N が与えられる。N の桁数を k とし、N の桁を0個以上 k 個未満消して残った桁をそのままの順序で結合して3の倍数を作れるか判定し、作る事ができれば作るのに必要な最小の桁数を求める。作る事ができなければ -1 を出力する。
まず3の倍数かどうかを判定する方法として、ある整数の各桁の和が3の倍数であれば元の値も3の倍数であると言えることから、N の各桁を使うかどうか決めて使う桁の値を合計したものが3の倍数かを調べることとする。
N<10^18 なので桁数は17桁で、DFSを用いて各桁を使うかどうか全探索をして求める事ができる。

解答例(Python)
https://atcoder.jp/contests/abc182/submissions/17995418

・D問題:Wandering

A1~An の数列が与えられる。この数列には負の要素が含まれることがある。数直線上の座標0に置かれているロボットが以下の動作を順に行う。
・正の向きに A1 進む
・正の向きに A1 進み、正の向きに A2 進む
〜
・正の向きに A1 進み、正の向きに A2 進み、…、正の向きに An 進む
動作開始から終了時までの間にロボットが移動する座標の最大値を求める。
N≦200000 のため、愚直にシミュレートすることは出来ない。そこで各 i の時に最終的にどれだけ移動するか、その間に最大でどれだけ座標が大きくなるかを事前に求めておく。
前計算では、累積和を用いる事で A1~Ai だけ移動した時の最終的な座標の増減を求める事ができる。また同時に各 i の時に最大でどれだけ座標が大きくなるかも求めておく。これは i-1 まででどれだけ座標が大きくなるかをメモしていき、i-1 の時の座標の増加量と i で移動した時の座標の増加量を比較する事で求める事ができる。
そして、前計算した情報を元に各 i で移動する先とその間の座標の最大値を求めていくことで答えを求める事ができる。

解答例(Python)
https://atcoder.jp/contests/abc182/submissions/17996311