AtCoder Beginner Contest 162
ABC162お疲れ様でした。水上位パフォがとれて良かったです。この調子で進んでいきたいです。
ちなみに言語アップデートの後確認をしておらず,最初2回ほど気づかずにC言語で提出していてコンパイルエラーを出しました。サーバーに負荷かけてすみません。ペナなくて良かったです。気をつけます。
---
A - Lucky 7
stringとして受けとって各桁が7かどうか判定しました。pythonだと書きやすそう。
上記のコンパイルエラーで心臓止まるかと思いました…
あと,全体で10000ACおめでとうございます。だんだん規模感がこどふぉみたいになってきましたね。
B - FizzBuzz Sum
言われた通りにやるだけで問題なし。
C - Sum of gcd of Tuples (Easy)
と,3乗しても愚直で通る計算量なので,そのままぶちこみます。python3だと間に合わない?(pypyならいける?)
D - RGB Triplets
制約がなので,までは可能と判断できます。R, Gの二つを固定してみると,Bに関して以下の3パターンがダメだということがわかります。
各R, Gに対して,Bの個数からダメなパターンの数を引いたものを足していくと答えが出ます。
R,Gに関してはvectorにpush_backして順番に取り出せるように,Bに関しては配列の中に保存してでアクセスできるようにすると楽でした。
言語選択でのパニックが抜けきっておらず,無駄に添字ミスのバグなどを出し続けて時間を溶かしました。もう少し早く解けると良かったです。
E - Sum of gcd of Tuples (Hard)
制約的にもしくはくらいまでしか計算できないので,その筋で考えます。
いくつか例を書き出していくと,の範囲で,gcdがちょうどになるものの個数を頑張って数えられないか,という考えに至ります。
gcdがちょうどになる数列は,の倍数の集合でかつ,の倍数の集合でないものとなります。が小さいものから計算すると,gcdがになるという例外を弾くのが大変なので,大きい方からgcdがとなる数列の場合の数を計算していきます。
が大きい方からくらいまでは,そのような数列は「全て」の1通りです。
それ以下の場合は,まず数列の全ての要素がの倍数となる時を考えて(とすると,通りとなります),そこからgcdがとなる数列の場合の数を引いていくという方針をとります。
最後に,各々の場合の数にをかけて足し合わせていきます。過程で適宜modをとると答えが出ます。
---
ここ2回は数学で美味しい思いをさせてもらっているので,ちゃんとアルゴリズムの勉強をして次回に備えようと思います。入水したい。
次回も頑張りましょう。