kichi2004's BLOG

競技プログラミングの参加記とか日常とか。(※Google Analyticsを使用しています)

競プロ

「AtCoder Beginner Contest 145」A~E問題解説 / 参加記

投稿日:

コンテストページはこちら

結果

5完 [A(100), B(200), C(300), D(400), E(500)] 53:22 ペナルティ: 1 (-> 58:22)
・順位: 321位 (Rated内225位)
・パフォーマンス: 1859 (青)
・Rating変化: 1384 -> 1441 (+57)

各問題の解法

A問題 “Circle” (100点)

コンテスト中の提出
C++ での提出
Python での提出

円の面積は 半径 × 円周率の2乗 で求めることができます。
円周率を \(\pi\) とおくと,半径 \(r\) の円の面積は \(\pi r^2\) で,半径 \(1\) の円の面積は \(\pi 1^2 = \pi\) となります。
よって,求める値は\(\frac{\pi r^2}{\pi} = r^2\) です。

計算量 \(O(1)\)

実装例

#include <iostream>

using namespace std;

int main() {
  int r; cin >> r;
  cout << r * r << endl;
}
r = int(input())
print(r * r)

B問題 “Echo” (200点)

コンテスト中の提出
C++ での提出
Python での提出

文字列 \(S\) がある文字列を 2 度繰り返したものであるか,つまり前半と後半が一致するかを判定する問題です。
まず,文字列の長さ \(N\) が奇数の場合,この条件を満たせないため,No となります。
偶数のときは,ループなどで 1 文字ずつ見ていくか,substring 関数などで前の半分を切り出し,それを 2 度繰り返したものが \(S\) と一致するかを判定すればよいです。実装例は, C++ では前者の方法,Python では後者の方法で実装しています。

計算量 \(O(N)\)

実装例

#include <iostream>

using namespace std;

int main() {
  int N; cin >> N;
  string S; cin >> S;
  if (N % 2) {
    cout << "No" << endl;
    return 0;
  }
  bool ok = true;
  for (int i = 0; i < N / 2; i++) {
    if (S[i] != S[N / 2 + i]) ok = false;
  }
  cout << (ok ? "Yes" : "No") << endl;
}
n = int(input())
s = input()
if n % 2:
    print("No")
    exit()
half = s[0:n // 2]
print("Yes" if s == half + half else "No")

C問題 “Average Length” (300点)

コンテスト中の提出
C++ での提出
Python での提出

問題文に書いてあるとおり,\(N!\) 通りの経路を全探索すれば良いです。
\([1, 2, \dots, N]\) の順列を求めて,その順番で実際に計算を行うことにより求めることができます。標準ライブラリに順列がある言語では,それを利用しましょう。
実装例において, C++ と Python では calc 関数の求める値が違うことに注意してください。

計算量 \(O(N\cdot N!)\)

実装例

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iomanip>

using namespace std;

// 指定した経路での長さを求める
double calc(vector<int>& order, vector<pair<int, int>>& xy) {
  double ret = 0;
  for (size_t i = 1; i < order.size(); i++) {
    int x1 = xy[order[i - 1]].first, y1 = xy[order[i - 1]].second;
    int x2 = xy[order[i]].first, y2 = xy[order[i]].second;
    ret += sqrt(pow(x1 - x2, 2) + pow(y1 - y2, 2));
  }
  return ret;
}

int main() {
  int N; cin >> N;
  vector<pair<int, int>> xy(N);
  for (int i = 0; i < N; i++) {
    int x, y; cin >> x >> y;
    xy[i] = make_pair(x, y);
  }
  vector<int> V(N);
  for(int i = 0; i < N; i++) V[i] = i;
  double ans = 0; int cnt = 0;
  do {
    ++cnt;
    ans += calc(V, xy);
  } while (next_permutation(V.begin(), V.end()));
  cout << fixed << setprecision(9) << ans / cnt << endl;
}
from itertools import permutations
from math import sqrt, pow, factorial

# 座標 a から b の距離を求める
def calc(a, b):
    x1, y1 = a
    x2, y2 = b
    return sqrt(pow(x1 - x2, 2) + pow(y1 - y2, 2))


n = int(input())
xy = []
for i in range(n):
    xy.append(list(map(int, input().split())))

ans = 0
for order in permutations(range(n)):
    tmp = 0
    for i in range(1, n):
        tmp += calc(xy[order[i]], xy[order[i - 1]])
    ans += tmp
ans /= factorial(n)

print(ans)

D問題 “Knight” (00点)

コンテスト中の提出
C++ での提出
Python での提出

まず,駒を \((i, j)\) から \((i+1,j+2)\) に移動する操作を 操作 A ,\(i+2,j+1\)に移動する操作を 操作 B とします。
ここで,操作 A を行っても,操作 B を行っても,移動後の X 座標 + Y 座標 から,移動前の X 座標 + Y 座標を引いた差は \(3\) となります。最初に \((0, 0)\) に置いてあるので,\(X+Y\) が \(3\) の倍数でなければ到達できないということになります。
また,どのような操作を行っても,\((1, 5)\) のような,一方の座標がもう一方の座標の \(2\) 倍を超えるような座標には到達できません。
逆にそれ以外の場合は,操作 A と B を適当な回数繰り返すと到達できることになります。
また,ある到達可能な座標 \((i, j)\) にたどり着くために必要な 操作 A の回数と 操作 B の回数は一意に定まります。これは,操作 A を行う回数を \(a\),操作 B を行う回数を \(b\) とすると,以下の式で表すことができます。
\[
i = 2a + b \\
j = a + 2b
\]
この連立方程式を解くことにより,必要な操作 A と B の回数を求めることができます。
必要な操作の回数が求められたら,「同じものを含む順列」として \(\frac{(A+B)!}{A!\ B!}\) によって答えを求めることができます。
答えを \(\mathrm{mod}\ 10^9+7\) で求める際,割り算を行うときは逆元をかけるということに注意してください。

計算量 \(O()\)

実装例

#include <iostream>

using namespace std;
int MOD = 1e9 + 7;

long long pow_mod(long long a, long long b) {
  long long res = 1;
  while (b) {
    if (b % 2) res = res * a % MOD;
    a = a * a % MOD;
    b >>= 1;
  }
  return res;
}

long long fact[1000001];
int main() {
  int X, Y; cin >> X >> Y;
  fact[0] = 1;
  for (int i = 1; i <= 1000000; i++) {
    fact[i] = fact[i - 1] * i;
    fact[i] %= MOD;
  }

  if ((X + Y) % 3 || X > Y * 2 || Y > X * 2) {
    cout << 0 << endl;
    return 0;
  }

  // 2a + b = X
  // a + 2b = Y
  int b = (-X + 2 * Y) / 3;
  int a = (2 * X - Y) / 3;

  long long ans = fact[a + b] % MOD;
  ans *= pow_mod(fact[a], MOD - 2);
  ans %= MOD;
  ans *= pow_mod(fact[b], MOD - 2);
  ans %= MOD;
  cout << ans % MOD << endl;
}
import numpy
MOD = 10 ** 9 + 7


# a ^ b % MOD
def pow_mod(value, exp):
    r = 1
    while exp:
        if exp % 2:
            r *= value
            r %= MOD
        value *= value
        value %= MOD
        exp //= 2
    return r


fact = [1] * 1000001
for i in range(1, 1000000 + 1):
    fact[i] = fact[i - 1] * i % MOD

x, y = map(int, input().split())
if (x + y) % 3 or x > y * 2 or y > x * 2:
    print("0")
    exit()

a, b = map(int, numpy.linalg.solve([[2, 1], [1, 2]], [x, y]))

ans = fact[a + b] % MOD
# ans /= fact[a] (mod 10^9 + 7)
ans *= pow_mod(fact[a], MOD - 2)
ans %= MOD
# ans /= fact[b] (mod 10^9 + 7)
ans *= pow_mod(fact[b], MOD - 2)
ans %= MOD
print(ans)

E問題 “All-you-can-eat” (500点)

コンテスト中の提出
C++ での提出
Python での提出

— D までの解説で疲れたので,後日書きます. —

計算量 \(O(NT)\)

実装例

全体の感想

過去2番めのパフォーマンスで,それなりにあたたまることができました。早く Highest 復帰したい。

-競プロ

執筆者:


comment

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

CAPTCHA


関連記事

no image

「M-SOLUTIONS プロコンオープン」に参加しました

コンテストページはこちら 結果 3完 [A(100), B(200), D(500)] 68:17 ペナルティ: 0 ・順位: 725位 (Rated) ・パフォーマンス: 1498 ・Rating変 …

no image

「エクサウィザーズ 2019」に参加しました

コンテストページはこちら 結果 2完 [A(100), B(200)] 2:00 ペナルティ: 0 ・順位: 550位 (Rated内533位) ・パフォーマンス: 1721 [パフォーマンス最高値] …

no image

「AtCoder Beginner Contest 121」に参加しました

コンテストページはこちら 結果 3完 [A(100), B(200), C(300)] 11:16 ペナルティ: 0 ・順位: 1006位 ・パフォーマンス: 1108 ・Rating変化: 1039 …

no image

「AtCoder Beginner Contest 138」に参加しました

コンテストページはこちら 結果 5完 [A(100), B(200), C(300), D(400), E(500)] 20:16 ペナルティ: 0 ・順位: 84位 (Rated内39位) [ABC …

no image

「Tenka1 Programmer Beginner Contest 2019」に参加しました

コンテストページはこちら 結果 3完 [A(100), B(200), C(300)] 11:53 ペナルティ: 0 ・順位: 8位 ・パフォーマンス: 1600 (Inner: 2556) ・Rat …