AtCoder Beginner Contest 191のきろく
D問題が通せなかった...
- A - Vanishing Pitch (100点)
- B - Remove It (200点)
- C - Digital Graffiti (300点)
- D - Circle Lattice Points (400点)
- E - Come Back Quickly (500点)
- F - GCD or MIN (600点): 未提出
- 結果、感想
A - Vanishing Pitch (100点)
であるかどうかを判定します。前回のAのWAで焦ってしまった経験からサンプル通してから提出しているので少し遅いです。
B - Remove It (200点)
問題文通りに実装します。 と等しい要素をスキップしながら出力でもいいのですが、空白が入ってしまうので避けました*1。
C - Digital Graffiti (300点)
###、
###、
###、
###である
の組の延べ個数を
とします。
は延べ個数なので上の条件を2つ満たしているときは2組、3つなら3組、4つなら4組として扱います。この
は内角が
の角の数です。
は最小で
ですが、これは四角形の時になります。そして、
が
増えると内角が
の角と内角が
の角がそれぞれ
個増え、辺の数は
本増えます。なので答えは
となります。
D - Circle Lattice Points (400点)
点 が円の内部または周上にある条件は
です。格子点の個数なので、直線
上の条件を満たす格子点の個数を求めて
を円と共有点をもつ範囲で動かして合計をとればいいです。
であり、
を1つ決めたとき、
であり、$$ \begin{align}
& (y-Y)^2 \leq R^2 - (c-X)^2 \\
\Longleftrightarrow\ & |y-Y| \leq \sqrt{R^2 - (c - X)^2} \\
\Longleftrightarrow\ & Y - \sqrt{R^2 - (c-X)^2} \leq y \leq Y + \sqrt{R^2 - (c-X)^2}
\end{align} $$ となるので、この範囲で が直線
上の格子点の個数です。
コンピュータで計算させる際は小数で計算させると誤差が出てくるので、全体に をかけてやることで整数にして計算を行います。
ここで雑に普通に型変換でええやろ、ってやってWAのまま終わってしまいました。普通の型変換は切り捨てなのですが、それだとまずいケースがあり、round関数を挟む必要があったようです。こちらのコードで例えば99999.9999がそのケースの一例なのが分かります。
また、 の範囲を求める時、ルートをとる関係で小数型が出てくるので、区間の両端の所は少しだけ幅を確認してみてみるといいでしょう。
E - Come Back Quickly (500点)
町 を出発点とする正しい散歩経路は、自己ループか
へ続く道がある町まで最短距離で行き、そこから
へ帰ってくる経路の最短なもの、のどちらかであるのでDijkstra法などを用いて計算することができます。
F - GCD or MIN (600点): 未提出
未だ解けてないので、何も書けません。
結果、感想
やっぱり、D問題が通せなかったのが悔しいですね。どっか間違った計算をさせているんじゃないかと思って、色々いじっていたのですが、計算ではなく型変換のやり方がまずかったというわけで、そこを修正したらすぐにACになりました。言われてみればそりゃ、常に0方向への丸めにするのはまずいのですが、コンテスト中はそこまで気が回っていませんでした。
