Toy と帽子と ADP BE

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

AtCoder Regular Contest 118

1完7WA。

maspyさんがwriterだから、覚悟はしていました・・・。

各問題

A - Tax Included Price

税抜き価格100円ごとに、問題の事象はt回発生します。なので税抜き価格が何百円のときにn回目が来るかを計算して、その手前(例えば15000円台で到達するなら15001円)から全探索すればよいです。

なんかいろいろ取っ散らかして、立式のミスやらうっかりintで宣言していた部分が残っていたりやらなんかわからんけどソースコードの修正ミスやらで7WAだして時間ギリギリで通しました。

B - Village of M People

華麗にスルー。

C - Coprime Set

実はこれが一番解けそうな見た目をしていたので、前半半分くらいはこっちに特攻していました。

結論からいうと6の倍数または10の倍数または15の倍数を小さいものからn個置けばそれが答えになります。

6 = 2 * 3, 10 = 2 * 5, 15 = 3 * 5 であり、どの組み合わせでも2か3か5を必ず共通で持っているため二つの最大公約数は1より大きくなりますが、全ての最大公約数をとると2か3か5のいずれかが欠けているので1になってしまうためです。

自分は6, 10, 15には気づいたのですが、残りを6の倍数のみで埋めようとしてA <= 10000の制限に引っかかってしまい、そこで思考停止してしまいました・・・。

かなり正解に近づいていたのは確かなので、Aに戻らずこれを考え続けるべきだったか・・・。

まとめ

安定を取ってAを意地で通したのでなんとか緑落ちは免れましたが・・・。Cで最後まで粘るべきだったのか・・・。

f:id:mdstoy:20210510002944p:plain