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

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

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

no image

「AtCoder Grand Contest 031」に参加しました

コンテストページはこちら 結果 0完 ・順位: 1565位 ・パフォーマンス: 358 ・Rating変化: 1046 -> 992 (-54) 各問題の考察 感想 全くわからなかった。出なかったら良 …

no image

競プロから離れて3週間経った今のお気持ち

お詫び 競プロについては、既に復帰しています。記事を書いたからには心情の変化等をお伝えするべきかと思いますが、余裕ができてからにさせていただければと考えています。今後ともよろしくお願いします。 また、 …

no image

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

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

no image

JOI 2020 / 2021 二次予選 参加記

はじめに おひさしぶりです.kichi2004 です.競プロ関係の記事は今年の 3 月以来 9 か月ぶりなので,まずはそれについて簡単にお話します.今年の 2 月に,JOI に二次予選落ちしたことや …