3完、div1復帰。いえい。

A. PawnChess

問題

白黒のポーンが置いてある盤面が与えられる。 このポーンは前にしか進めず相手の駒を取れない。 プレイヤーは交互にポーンを進め、先に盤面の端まで動かせば勝ち。 必勝手番を答える。

解法

やるだけ。

実装

#include <iostream>
#define repeat_from(i,m,n) for (int i = (m); (i) < (n); ++(i))
#define repeat(i,n) repeat_from(i,0,n)
#define repeat_from_reverse(i,m,n) for (int i = (n)-1; (i) >= (m); --(i))
#define repeat_reverse(i,n) repeat_from_reverse(i,0,n)
using namespace std;
int main() {
    char f[8][8];
    repeat (y,8) repeat (x,8) cin >> f[y][x];
    int w = 8;
    int b = 8;
    repeat (x,8) {
        repeat (y,8) {
            if (f[y][x] == 'W') w = min(w, y);
            if (f[y][x] != '.') break;
        }
        repeat_reverse (y,8) {
            if (f[y][x] == 'B') b = min(b, 8-y-1);
            if (f[y][x] != '.') break;
        }
    }
    cout << (w <= b ? 'A' : 'B') << endl;
    return 0;
}

B. The Monster and the Squirrel

問題

n次正多角形がある。 頂点を時計回りに見ていって、頂点から他の頂点の方向に線を引く。 ただし別の線に交差する場合はそこで停止する。 するとn角形は複数個の領域に分割される。 この領域を、すべて巡るには、最小で何本の境界をまたぐか。

解法

実験すると$(n-2)^2$ぽいので、本番中はそれで投げてしまえばよい。

実際領域の数は$(n-2)^2$で正しい。 頂点a, b間の直線が、別の直線が間に挟まって分割されるかどうかを考えればよい。 外部から入ってくるときの$1$本、頂点1からの線が$n-3$本、頂点1に隣接する2頂点からはそれぞれ$n-3$本引け、残りの$n-3$個の頂点は頂点1へ辺を引けないのでそれぞれ$n-4$本。 \(1 + (n - 3) + 2 (n - 3) + (n - 3) (n - 4) = (n - 2)^2\)

また、どの領域もその頂点のひとつは多角形の頂点のひとつであるので、多角形の外周すれすれのところを時計回りに移動すれば全ての領域を一度に巡ることができる。

実装

#!/usr/bin/env python3
n = int(input())
print((n-2)**2)

C. The Big Race

問題

虫w, bがレースをする。 レーストラックはtマスの長さしかなく、tマス目を越えることはできない。 虫たちはそれぞれちょうどw, bマスずつしか進めない。 つまりtマスちょうどは走りきれない場合がある。 レースの勝敗を走った(or 走ることのできる最長の)距離で決めるとき、引き分けになる確率を有理数で答えよ。

解法

マス目ごとの引き分けになる/ならないは、${\rm lcm}\{w,b\}$の周期を持つ。 この1周期の中で、$1 \dots \min\{w,b\}$マス目と${\rm lcm}\{w,b\} - 1$マス目の合計$\min\{w,b\}$マスが引き分けになる。

あとはやるだけ。$O(1)$。 制約が$5 \cdot 10^{18}$なのでlong longだと${\rm lcm}$でやばい。pythonやhaskellを使おう。

実装

#!/usr/bin/env python3
import math
t, a, b = map(int,input().split())
l = a * b // math.gcd(a,b) # lcm
p = (t // l) * min(a,b) + min(t % l, min(a,b) - 1)
q = t
r = math.gcd(p, q)
print('{}/{}'.format(p//r, q//r))

editorial