トップ > 競技プログラミング-AtCoder > ACoder ABC162 参加記

ACoder ABC162 参加記

競技プログラミング-AtCoder

お久しぶりです。
4/12 に開催された AtCoder の ABC162 に参加したので参加記を書いていこうと思います。


f:id:granddaifuku:20200413222052p:plain

A, B, C, D の 4 完 1 WA でした。
今回のセットはそんなに苦手な分野もなく解きやすかったかなという気持ちです。

A 問題

問題概要
  • 3 桁の整数 N が与えられる
  • N のいずれかの桁に 7 が含まれていれば "Yes" そうでなければ "No" を出力する
解答

実際に各桁を見ていけば良いです。
本番中には 1 桁ずつ桁をずらして確認しましたが、文字列として受け取れば各文字を見るだけで済むということに本番後気づきました。

提出したコード


B 問題

問題概要
解答

1 ~ N までループを回して Fizz Buzz かどうかを確認し、該当しない場合は足してあげれば良いです。

提出したコード


C 問題

問題概要
  • 整数 K が与えられる
  • \displaystyle\sum_{a = 1}^{K}\sum_{b = 1}^{K}\sum_{c = 1}^{K} gcd(a, b, c) を求める
解答

gcd(a, b, c) = gcd(gcd(a, b), c) を踏まえて計算するだけです。
本番では TLE に備えて 配列 tmp[i][j] = gcd(i + 1, j + 1) をあらかじめ求めておき、gcd を求める回数を減らしました。
ちなみにあらかじめの計算をせずに純粋に計算させるコードも書き、そちらも制限時間内に実行できました。

提出したコード


D 問題

問題概要
  • 'R'、'G'、'B' の 3 文字のみから構成される長さ N の文字列 S が与えられる
  • 次の 2 つの条件を満たす (i, j, k) の組の数を求める
    1. S_i \neq S_j かつ S_i \neq S_k かつ S_j \neq S_k
    2. j - i \neq k - j
解答

S 中の R, G, B それぞれの位置に対応した配列 r, g, b を用意し、
累積和である位置 i から最後までの R, G, B それぞれの文字の個数を数えられるようにしておきます。
制約が N = 4000 なので 2 重ループまでは回せることがわかります。
そのため、i = 1 ~ N, j = i + 1 ~ N と 2 重ループを回し、k = j + 1として、位置 k から最後までに何個条件を満たす文字があるかを求めます。
最後に 2 つ目の条件 k = 2 * j - i の時も条件を満たしているかを確認し、満たしていない場合は上で求めた個数から 1 引きます。
求めた個数を足し合わせたものが答えです。

提出したコード