ABC145 参加記

AtCoder の ABC145 に参加してきましたので自分の解いた問題と解き方について記事を書こうと思います.

その前に...
緑コーダーになりました！！

A問題

整数 r が与えられます。 半径 r の円の面積が半径 1 の円の面積の何倍になるかを求めてください。 なお答えは制約の下では必ず整数になることが示せます。

-- 解答 --
円の面積の公式より r * r の値を出力する.
提出したコード

B問題

正整数 N 及び、長さ N の英小文字から成る文字列 S が与えられます。 この文字列が、ある文字列を二度繰り返したものであるかを判定してください。 則ち、文字列 T であって、S = T + T となるものが存在するかを判定してください。

--解答--
n / 2 をして for 文を 0 ~ n / 2 まで回して s[i] と s[i + n / 2] が一致するか比較する.
提出したコード

C問題

座標平面上に N 個の町があります。町 i は、座標 (xi, yi) に位置しています。 町 i と町 j の間の距離は√((xi − xj)² + (yi − yj)²)です。 これらの町を全て 1 回ずつ訪れるとき、町を訪れる経路は全部で N! 通りあります。 1 番目に訪れる町から出発し、2 番目に訪れる町、3 番目に訪れる町、…、経由し、N 番目に訪れる町に到着するまでの移動距離 (町から町への移動は直線移動とします) を、その経路の長さとします。 これらの N! 通りの経路の長さの平均値を計算してください

--解答--
2 <= n <= 8 と制約が小さいので c++ にある next_permutation を使って N! 通り全ての場合において各町の距離を求めて最後に N! で割って平均とした.
提出したコード

D問題

二次元グリッドの原点 (0, 0) にチェスのナイトの駒があります。 ナイトの駒はマス (i, j) にあるとき (i + 1, j + 2) か (i + 2, j + 1) のどちらかのマスにのみ動かすことができます。 ナイトの駒をマス (X, Y) まで移動させる方法は何通りありますか？ 10⁹+7 で割った余りを求めてください。

--解答--
(i + 1, j + 2) と (i + 2, j + 1) を (i + 1 + 0, j + 1 + 1), (i + 1 + 1, j + 1 + 0) と考えて, 強制的に (+ 1, + 1) される回数を (X, Y) から引いて X < 0 や Y < 0 だったりなど条件が合わないもの落として, 後はnCrをやるだけ. AtCoderのABC034のC問題と同じ条件まで落とせたので同じように解く.
提出したコード