ここ数回、Codeforcesのレートが落ちるばかりです。とても悲しいので、こどふぉの問題傾向に慣れるのと地力アップのため、教育効果が高いと言われるEducational Codeforces(えでゅふぉ)の過去問で精進しようかと思い至りました。
せっかく解くのですから精進記録もつけようと思います。目的は主に以下の2つです。
- 各問題のポイントや教訓を記録として書き留め、知識の定着を促進
- こどふぉは良質な解説へのアクセスが悪い(ことが多い)ため、参考にしたコード(python3|pypy3)や分かりやすい解説記事があれば併せて記録する
Educational Codeforces Round 1
A. Tricky Sum
ポイント
- 普通にforループを回してiが2の累乗か否か判定してるとなので1秒で終わらない
- まず1～nの総和Sを和の公式で求めて、それとは別にn以下の2の累乗の合計S2をforループなりで求める。S-2*S2が答え
B. Queries on a String
ポイント
- 指定された範囲の文字列をスライスで抜き出して回転処理かけて元の文字列に戻すだけ
- 回転の方法は、スライスで指定する方法とdeque.rotate()の2通りあり
#文字列sをn文字分右に回転
#方法1(リストのスライス)
def rolling(s, n):
l = len(s)
#右にシフトの場合
return s[-n%l:] + s[:-n%l] #左にシフトの場合はnの正負を逆に
#方法2(deque.rotate()) ※方法1より遅い
from collections import deque
def rolling_deque(s, n):
t = deque(s)
#右にシフトの場合
t.rotate(n) #左にシフトの場合はnの正負を逆に
return tC. Nearest vectors
ポイント
- atan2を使ってx軸の正の向きと各ベクトルの間の角度θを求めて昇順ソートし、隣り合うベクトル間の角度を比較して最小のものを探す(先頭と最後のベクトルが1番近い可能性もあることに注意(atan2の出力が-π～πなので))
- ↑だけだとWAになったのでACしてる方のコードを参考に実装…がハイライト箇所の処理内容が理解できず。内積と外積の計算良く分からず、以下の公式解説を理解して推敲できるようにがんばります。
from math import atan2
inner = lambda a, b: a[0] * b[0] + a[1] * b[1]
outer = lambda a, b: a[0] * b[1] - a[1] * b[0]
N = int(input())
vec = []
for i in range(N):
x, y = map(int, input().split())
vec.append((atan2(y, x), (x, y), i + 1))
vec.sort()
diff = []
for i in range(N):
diff.append([inner(vec[i][1], vec[(i+1)%N][1]), abs(outer(vec[i][1], vec[(i+1)%N][1])), vec[i][2], vec[(i+1)%N][2]])
min_diff = diff[0]
for d in diff:
if outer(d[:2], min_diff[:2]) > 0: min_diff = d
print(min_diff[2], min_diff[3])参考
- 解説サイト探したのですがロシア語の公式解説しか見当たらず、DeepL翻訳(をちょい整形)したものを以下に貼ります(長いので折り畳んでます)
- 翻訳結果の「もうそれどころではありません。」ワロタ
公式解説(引用)
多くの参加者がこの課題につまずきました。経験豊富な参加者でも失敗することがありました。どうやらこの問題は、g++ではatan2をlong doubleで使うことで解決するようです(long doubleはdoubleと同じ8バイトなので、Visual Studioでは解決しません)。ここでは、整数での解法を説明しますが、確かに理解して知っておくに越したことはありません。
単純な形状のソリューションでは、typedef pair<T,T> pt(Tはpoint/vectorの基本的なデータ型)を使い、同時にXを1番目に、Yを2番目に定義することが好きです。
大雑把に言うと、「すべてのベクトルを極角でソートし、隣り合うベクトルのペアをすべて調べて、ベクトル間の角度が最小になるものを選ぶ」という解答案です。
何かをソートするには、“less than “というオーダーの関数を定義しなければなりません(最初の引数が2番目の引数よりも厳密に小さい場合にのみ、真を返す)。
以下では、ベクトルの擬似スカラー積(cross(a, b) = a.X * b.Y - a.Y * b.X)を使用しますが、簡単にするために単にベクトルと呼びます。ここで、sin(a, b)とは、第1のベクトルから第2のベクトルへの指向角のサインである。したがって、ベクトル積の符号は、“第1のベクトルから第2のベクトルへの角度が180度以下であることは本当か？“、あるいは(同じ意味ですが)“第1のベクトルと第2のベクトルを結合(共オリエント)する最短の方法は、第1のベクトルを反時計回りに移動させることであることは本当か？“を示しています。値が0の場合は、方法は問わないことを意味します。つまり、ベクトルは共方向か逆方向のどちらかになります。
そのため、ソート時に第1のベクトルが第2のベクトルよりも先行しなければならないというのが本当かどうかを知るには、ほとんどの場合、ベクトル積の符号を見れば十分です(ゼロより大きいとイエス)。ただし、ループを通過する際の分岐点では、これが機能しません(例えば、ベクトル(1, -1)は、ベクトル(1, 1)の前に立っていると定義されます)。そのためには、まず、それらが配置されている半平面を比較してみましょう(Y＝0の場合は、上の半平面に対するOx光線の正の方向を与えます)。関数topは、「pが上半平面にあることが真かどうか」を判断します。
bool top(pt p) {
return p.Y < 0 || p.Y == 0 && p.X < 0;
}
したがって、ベクトルを整数の極角でソートする完全な関数「less」は次のようになります。
bool polarLess(const pt& a, const pt& b) {
bool ta = top(a)
bool tb = top(b)
if (ta != tb)
return cross(a, b) > 0;
}
次に、2つ目の小問題を解きます。4つのベクトルa1、b1、a2、b2について、a1とb1の間の角度がa2とb2の間の角度よりも厳密に小さいかどうかを調べます。
ベクトルaとベクトルbの間の無向角は、次のようにして求められることを思い出してください。ベクトルaがOx方向(つまり、すぐ右)に立つように両ベクトルを配置したとします。そうすれば、bの極角を求めればよいことになる(角度は無方向なので、座標b.Yはモジュロにする必要がある)。しかし、ベクトルaはOxに沿っていない。aへの投影bの長さ(実際には座標系のxであり、我々の望む方向に向いている)と、aから左に90度(垂直)回転したベクトルへの投影bの長さを求めよう。第1射影の長さは|b|･cos(a, b)、第2射影の長さは|b|･sin(a, b)と、簡単に求めることができます。しかし、スカラー積だけをとると、|a|･|b|･cos(a, b)となり、ベクトル積は|a|･|b|･sin(a, b)となります。
すなわち、ベクトルp＝(dot(a，b)，cross(a，b))(dot(a，b)はスカラー積)は、ベクトルb’(b’は、aがOxと一致するようにbとaの両方を同時に回転させた場合、ベクトルbを回転させた結果である)と同方向のベクトルである。ここで絵を描けばいいのですが、もうそれどころではありません。
したがって，例えば，ベクトル間の向きのある角度(- π ~ π)を求めるには，ベクトルpの向きをとればよい。つまり，atan2(cross(a, b), dot(a, b))となる。無向角が必要な場合は、ベクトル積(実際にはベクトルpのy座標)からモジュラスを取る必要があります。
次に、上述のようにベクトルp1とp2のペアを見つけ、どちらが小さい極角を形成するかを確認します。これは、すでにおなじみのベクトル積という性質を利用して行うことができます。
したがって、ベクトルa1とb1の間の角度の値と、ベクトルa2とb2の間の角度の値を求める関数「less」の完全なコードは次のようになります。
bool angleLess(const pt& a1, const pt& b1, const pt& a2, const pt& b2) {
pt p1(dot(a1, b1), abs(cross(a1, b1))
pt p2(dot(a2, b2), abs(cross(a2, b2))
return cross(p1, p2) > 0;
}
D. Igor In the Museum
ポイント
- bfsを使う。ただし普通にやるとTLEするので、計算量を落とす工夫が必要
- この問題の肝はハイライト箇所で示したメモ化による枝刈り。一回の探索中で通過した全地点に、その回の探索で見られる絵の合計数を記録することで次回以降同じエリアからスタートする際の処理をスキップ可能
- また、よくある迷路問題のように「ある地点」に到達するまでの歩数を管理する必要がないので、二次元座標を一次元のインデックス化(x+y*m)して、visitedフラグをsetで管理するとちょっと速くできるみたい
import sys
input = lambda: sys.stdin.readline().rstrip()
from collections import deque
move = ([1, 0], [-1, 0], [0, 1], [0, -1])
def bfs(visited, sy, sx):
if pic[sy][sx] != -1: return pic[sy][sx] queue = deque([[sy, sx]])
visited.add(sy*m+sx)
ans = 0
while queue:
y, x = queue.popleft()
for dy, dx in move:
new_y, new_x = y+dy, x+dx
if museum[new_y][new_x] == ".":
if new_y*m+new_x not in visited:
visited.add(new_y*m+new_x)
queue.append([new_y, new_x])
else:
ans += 1
for a in visited: x = a % m y = a//m pic[y][x] = ans return ans
n,m,k = map(int, input().split())
museum = [input() for i in range(n)]
pic = [[-1 for i in range(m)] for j in range(n)]
for _ in range(k):
sy, sx = map(int, input().split())
sy, sx = sy-1, sx-1
visited = set()
print(bfs(visited, sy, sx))E. Chocolate Bar
まだです…
F. Cut Length
まだです…
以上です。