結果
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 復帰したい。
