Toy と帽子と ADP BE

主にプログラミングに関わる話をゆるくエモくやっていきます

AtCoder Beginner Contest 162

4完1CE

各問題

A - Lucky 7

文字列で読み込んで、一文字ずつ判定するのが一番早いでしょうか。

B - FizzBuzz Sum

愚直にループを回して計算すれば良いです。forとifを使う、This is the B! って感じの問題でした。

ちなみに、いわゆるFizzBuzzと違って、15で割った余りを求めなくてよかったりします。問題を読み替えると「3でも5でも割り切れない数を足す」となりますので。

ちなみにCEはここで出しまして・・・

最初に全問題を開いた→Aの提出のときは言語が違うことに気づいた→Bの提出のときに忘れていた、ということをやらかしました。CEがペナにならないルールでよかった・・・。

なお、直後に残りの問題のページを慌ててリロードしました。

C - Sum of gcd of Tuples (Easy)

制約が200までなので、愚直に3重ループを回してgcdを計算すればよいです。なお、3つの数のgcdはgcd(a, gcd(b, c))と求めればよいです。

D - RGB Triplets

まず、各文字毎の出現数の累積和を取ります。

次に、jの位置を決めた時に、jの位置にある文字以外の2文字がいくつ出るかを先程の累積和を使って数えます。例えばGRRBGRGで、4番目のBを真ん中と決めた場合、左にRが2つ右にGが2つです。求めたい組み合わせはこれをかけ合わせたものですから2 * 2 = 4通りとなります。

(Editorialによると、すべてのパターンの組み合わせの数は「Rの数×Gの数×Bの数」でよいらしいです・・・)

しかし、j - i != k - jという条件があるので、jを中心として対象となる位置の文字を確認して、左にR右にGとなっていればその分数を減らします。これをRとGを逆転させたものでも行えばよいです。そしてjは2からN-2までを取りうるので、それをすべてチェックします。これは愚直に2重ループを回すことになりますが、制約が4000と小さいので大丈夫です。

E - Sum of gcd of Tuples (Hard)

gcd(A1, ..., AN ) = X となる数列 {Ai} がいくつあるかを数える、というところまではわかったのですが、単純にやると重複して数えてしまうためなんとかしなければなりません。この何とかする方法が最後までわからずじまいでした。

Editorialによると、大きい方から計算すればよいとのこと。それはそうですね・・・。

F - Select Half

みてません。

まとめ

Highestを上回るパフォでとりあえずスランプ脱出、ですかね?このあとのこどふぉで冷えたんですけどね・・・。

f:id:mdstoy:20200413011728p:plain