いろいろな記録

大学院生やってます

AtCoder Beginner Contest 162

ABC162お疲れ様でした。水上位パフォがとれて良かったです。この調子で進んでいきたいです。

atcoder.jp

 ちなみに言語アップデートの後確認をしておらず,最初2回ほど気づかずにC言語で提出していてコンパイルエラーを出しました。サーバーに負荷かけてすみません。ペナなくて良かったです。気をつけます。

--- 

 

 A - Lucky 7

stringとして受けとって各桁が7かどうか判定しました。pythonだと書きやすそう。

上記のコンパイルエラーで心臓止まるかと思いました…

あと,全体で10000ACおめでとうございます。だんだん規模感がこどふぉみたいになってきましたね。

 

B - FizzBuzz Sum

言われた通りにやるだけで問題なし。

 

C - Sum of gcd of Tuples (Easy)

 k \leqq 200と,3乗しても愚直で通る計算量なので,そのままぶちこみます。python3だと間に合わない?(pypyならいける?)

 

D - RGB Triplets

制約が n \leqq 4000なので, O(n^2)までは可能と判断できます。R, Gの二つを固定してみると,Bに関して以下の3パターンがダメだということがわかります。

f:id:bustle0309:20200412235954p:plain

各R, Gに対して,Bの個数からダメなパターンの数を引いたものを足していくと答えが出ます。

R,Gに関してはvectorにpush_backして順番に取り出せるように,Bに関しては配列の中に保存して O(1)でアクセスできるようにすると楽でした。

言語選択でのパニックが抜けきっておらず,無駄に添字ミスのバグなどを出し続けて時間を溶かしました。もう少し早く解けると良かったです。

  

E - Sum of gcd of Tuples (Hard)

制約的に O(k)もしくは O(k\log(k))くらいまでしか計算できないので,その筋で考えます。

いくつか例を書き出していくと, 1\leqq g \leqq kの範囲で,gcdがちょうど gになるものの個数を頑張って数えられないか,という考えに至ります。

gcdがちょうど gになる数列は, gの倍数の集合でかつ, 2g, 3g\cdotsの倍数の集合でないものとなります。 gが小さいものから計算すると,gcdが 2g, 3g\cdotsになるという例外を弾くのが大変なので,大きい方からgcdが gとなる数列の場合の数を計算していきます。

 gが大きい方から \frac{k}{2}くらいまでは,そのような数列は「全て g」の1通りです。

それ以下の場合は,まず数列の全ての要素が gの倍数となる時を考えて( p =  \frac{k}{g}とすると, p^n通りとなります),そこからgcdが 2g, 3g\cdotsとなる数列の場合の数を引いていくという方針をとります。

最後に,各々の場合の数に gをかけて足し合わせていきます。過程で適宜modをとると答えが出ます。

 

---

 

ここ2回は数学で美味しい思いをさせてもらっているので,ちゃんとアルゴリズムの勉強をして次回に備えようと思います。入水したい。

 

次回も頑張りましょう。