Yukicoder No.455 冬の大三角

,

http://yukicoder.me/problems/no/455

一直線上にあるかどうかは外積で判定できる。 乱択をして判定なしで答えてもも失敗確率は$0.5$未満であるので、(テストケース次第ではあるが)何度も提出すれば通る気がする。

#!/usr/bin/env python3
h, w = map(int, input().split())
s = [ input() for _ in range(h) ]
stars = []
for y in range(h):
    for x in range(w):
        if s[y][x] == '*':
            stars += [( y, x )]
assert len(stars) == 2
for y in range(h):
    for x in range(w):
        if len(stars) == 3:
            continue
        if s[y][x] == '-':
            ay, ax = stars[0]
            by, bx = stars[1]
            if (ay - y) * (bx - x) != (ax - x) * (by - y):
                s[y] = list(s[y])
                s[y][x] = '*'
                s[y] = ''.join(s[y])
                stars += [( y, x )]
for line in s:
    print(line)

Yukicoder No.454 逆2乗和

,

http://yukicoder.me/problems/no/454

なぜ通るのか理解できない。 もしかしたら$\frac{1}{x+l}$を足す方が正確かもしれない。

solution

単純に第$l$項までの和を計算し$\frac{1}{l}$を足せば通る。 $\frac{1}{l^2}$ぐらいの精度になるようだ。

implementation

#include <cstdio>
#include <cmath>
#define repeat_from(i,m,n) for (int i = (m); (i) < (n); ++(i))
const int l = 1000000;
int main() {
    long double x; scanf("%Lf", &x);
    long double y = 0;
    repeat_from (n,1,l) y += powl(x+n, -2);
    y += 1.0/l;
    printf("%.12Lf\n", y);
    return 0;
}

AtCoder Regular Contest 064: F - Rotated Palindromes

,

http://arc064.contest.atcoder.jp/tasks/arc064_d

解けず。$1000$点だからとF openしたので座ってるだけになった。

solution

回文$a$の周期性$d$で分類する。$O(d(N)^2)$。

回文$a$はちょうど$K^{\lceil \frac{N}{2} \rceil}$個存在する。 しかしこれを単に$N$倍しても答えにはならない。 何度か回転$f : a_0a_1a_2\dots a_{n-1} \mapsto a_1a_2\dots a_{n-1}a_0$すると他の回文と一致する場合がある。

ここで回文$a$をその周期で分類する。 回文の周期$d$とは、$f^d(a) = a$となるような最小の$d \ge 1$のこと。 ある周期$d$の回文の個数を(回転で一致する場合は同一視して)$\mathrm{num}(d)$とすると、 $\mathrm{ans} = \sum_{d | N} \mathrm{num(d)} \cdot d$となる。

$\mathrm{num}(d)$を求めよう。 単に$K^{\lceil \frac{d}{2} \rceil}$個だと$d’|d$な$d’ \lt d$を重複して数えること、$d$が偶数なら$\frac{d}{2}$回の回転で他の周期$d$の回文と衝突することから、$\mathrm{num}(d) = (K^{\lceil \frac{d}{2} \rceil} - \sum_{d’|d \land d’\lt d} \mathrm{num}(d’))\cdot \frac{1}{2 - d \bmod 2}$となる。

implementation

#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <cassert>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
typedef long long ll;
using namespace std;

vector<int> sieve_of_eratosthenes(int n) { // enumerate primes in [2,n] with O(n log log n)
    vector<bool> is_prime(n+1, true);
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i*i <= n; ++i)
        if (is_prime[i])
            for (int k = i+i; k <= n; k += i)
                is_prime[k] = false;
    vector<int> primes;
    for (int i = 2; i <= n; ++i)
        if (is_prime[i])
            primes.push_back(i);
    return primes;
}
vector<ll> list_prime_factrors(ll n, vector<int> const & primes) {
    vector<ll> result;
    for (int p : primes) {
        if (n < p *(ll) p) break;
        while (n % p == 0) {
            result.push_back(p);
            n /= p;
        }
    }
    if (n != 1) result.push_back(n);
    return result;
}
ll powi(ll x, ll y, ll p) { // O(log y)
    assert (y >= 0);
    x = (x % p + p) % p;
    ll z = 1;
    for (ll i = 1; i <= y; i <<= 1) {
        if (y & i) z = z * x % p;
        x = x * x % p;
    }
    return z;
}

const ll mod = 1e9+7;
int main() {
    int n, k; cin >> n >> k;
    set<int> ds { 1 };
    for (ll p : list_prime_factrors(n, sieve_of_eratosthenes(sqrt(n) + 3))) {
        set<int> prev_ds = ds;
        for (int d : prev_ds) {
            ds.insert(d * p);
        }
    }
    ll ans = 0;
    map<int,ll> num;
    for (int d : ds) {
        ll acc = powi(k, (d+1)/2, mod);
        for (int d2 : ds) if (d % d2 == 0 and d2 < d) {
            acc -= num[d2];
        }
        num[d] = (acc % mod + mod) % mod;
        ans += num[d] * d / (d % 2 == 0 ? 2 : 1);
    }
    ans %= mod;
    cout << ans << endl;
    return 0;
}

Yukicoder No.217 魔方陣を作ろう

,

http://yukicoder.me/problems/no/217

Wikipediaには奇数$\times$奇数か特殊な$n\times n$の場合しか載ってないじゃんと言ってぐぐって見つけてきたのを書いたが、よく見たらWikipediaのでちゃんと尽くされていた。日本語が読めてなかった。

solution

  • $(2n+1)\times (2n+1)$: 斜め上に進んでいくやつ
  • $4n\times 4n$: $2\times 2$ごとに区切って反転なやつ
  • $(4n+2)\times (4n+2)$: $4$倍に膨らませるやつ (LUX法) / 外枠だけ付けるやつ

それぞれ$O(N^2)$。 詳細はWikipedia見て。

implementation

#!/usr/bin/env python3
def magic_square(n):
    assert n >= 3
    f = [ [ None for _ in range(n) ] for _ in range(n) ]
    if n % 2 == 1: # http://d.hatena.ne.jp/ziom/20090619/p1
        y, x = 0, n//2
        for i in range(n**2):
            f[y%n][x%n] = i+1
            if f[(y-1)%n][(x+1)%n] is None:
                y, x = y-1, x+1
            else:
                y, x = y+1, x
    elif n % 4 == 0: # http://d.hatena.ne.jp/ziom/20090620/p1
        for y in range(n):
            for x in range(n):
                i = y*n+x+1
                if (y+1)&2 == (x+1)&2:
                    y = n-y-1
                    x = n-x-1
                f[y][x] = i
    else: # http://d.hatena.ne.jp/ziom/20090621/p1
        # [1,2n-2]
        f[  0][  0] = 1
        f[  0][n-1] = 2
        f[n-1][  1] = 3
        for i in range(4,2*n-1):
            if i <= n:
                x = i-2
                y = [n-1, 0][bool(i&2)]
                f[y][x] = i
                if i == n:
                    f[y][x] += 3
            else:
                y = i-n
                x = [n-1, 0][bool(i&2)]
                f[y][x] = i
                if i < n+4:
                    f[y][x] -= 1
        # [n^2-n+1,n^2]
        for i in range(1,n-1):
            for j in [ 0, n-1 ]:
                if f[  j][  i] is not None:
                    f[n-j-1][i] = n**2 - f[  j][  i] + 1
                if f[  i][  j] is not None:
                    f[i][n-j-1] = n**2 - f[  i][  j] + 1
        f[n-1][n-1] = n**2 - f[  0][  0] + 1
        f[n-1][  0] = n**2 - f[  0][n-1] + 1
        # recursion
        g = magic_square(n-2)
        for y in range(n-2):
            for x in range(n-2):
                f[y+1][x+1] = g[y][x] + 2*n-2
    return f
n = int(input())
for row in magic_square(n):
    print(*row)

Yukicoder No.23 技の選択

,

http://yukicoder.me/problems/no/23

ちゃんと考えれば$O(1)$になるのだろうなあと思って他人の提出等を見たが、だめそう。

solution

次に通常攻撃か必殺技かで場合分けして$\min{}$。$O(H)$。

通常攻撃の場合、$e(h) = 1 + e(h-A)$。 必殺技の場合、$e(h) = 1 + \frac{2}{3}e(h-D) + \frac{1}{3}e(h) = \frac{3}{2} + e(h-D)$。 合わせて$e(h) = \min \{ 1 + e(h-A), \frac{3}{2} + e(h-D) \}$。

implementation

再帰の方がきれいだからと再帰したらsetrecursionlimitが必要になった。

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10000+3)
h, a, d = map(int, input().split())
def e(i, memo={}):
    if i <= 0:
        return 0
    else:
        if i not in memo:
            memo[i] = min(1 + e(i-a), 3/2 + e(i-d))
        return memo[i]
print(e(h))

茶会 活動報告 20161206

,

茶会とは、神戸大学コンピュータ部が中心となって行っている競技プログラミング練習会。 部室は存在するが環境が悪く、食堂で行っているのでそう呼ばれ始めた。

問題

Yukicoderで主に星$3$からのおみくじ。$2$時間。

結果

oはAC、xはWA、-は既に解いてた場合。 oはこれを書いている間にACされた問題も含む。

  • sr*: oooox
  • ko*: oxooo
  • co*: o-ooo (online)
  • ku*: oxoox
  • ki*: ---oo
  • ni*: xxoxx
  • ta*: 不参加
  • iz*: 不参加
  • ku*: 最近見てない
  • uk*: 最近見てない

Geometry Dashが比較して難しいようだが、すごく難しいという問題はなかったらしい。

その他

CTFを始めた人が(複数)いるためその練習会もするかという話になった。 とりあえずは今週金曜の$4,5$限。 村人BはまだらしいがROPは理解してるぽいので時間の問題という感じだし放っておいても勝手に強くなるだろうが、まあせっかくなので。


この記事はKobe University Advent Calendar 2016の$6$日目の記事です。


DISCO presents ディスカバリーチャンネル コードコンテスト2016 本戦: D - シャツの部屋

,

http://ddcc2016-final.contest.atcoder.jp/tasks/ddcc_2016_final_d

私は気付かずだったが、「初日はTシャツを買いにいくためのTシャツがないのでは」「そもそもTシャツは貰うものでは」といった点が指摘されていた。

solution

大部分を最も効率のよいTシャツを使い細かい部分はDP。$O({(\max A_i)}^3)$。 $O(NM)$のDPでは明らかに間に合わない。

まず、洗濯回数$w$は$0 \le w \lt A_i$としてよい。 Tシャツは初日に全て買うとしてかまわないこと、まだ着れる服が残っているなら洗濯する必要がないことから言える。

洗濯回数$w$を固定する。 $M \le 10^9$と大きいので、最も効率のよいTシャツ$i = \operatorname{argmax}_i \frac{B_i}{\min \{ w+1, A_i \}}$を繰り返し使うことになる。

最も効率のよいTシャツ$i$以外のTシャツを使う回数を考える。$A_{\mathrm{eff}} = \min \{ w+1, A_i \}$とする。 Tシャツを$k$枚買ってそれぞれ$a_j = \min \{ w+1, A_{i_j} \}$ ($j \lt k$)回使ったとする。 順に使って累積和のようにすると$s_j = \sum_{k \lt j} a_k$と書け、もし$k \gt A_{\mathrm{eff}}$であれば$s_j \equiv s_k \pmod{A_{\mathrm{eff}}}$な$j,k$がある。 この$j \lt k$に関して、$j, j+1, \dots, k-1$番目のTシャツを使った回数は$A_{\mathrm{eff}}$の整数倍であり、最も効率のよいTシャツで置き換えてよい。 これにより枚数$k \le A_{\mathrm{eff}}$である。

最も効率のよいTシャツ以外の部分の費用について。 枚数$k$の議論より、使用回数は${(\max A_i)}^2$で抑えられる。 $O(N {(\max A_i)}^2)$のDPができるが、しかしこれを各$w$にすると間に合わない。 よってDP tableの部分更新をする。 $w$を増やすたびに、$w+1$回使えるTシャツ$i$で最も安いもの($A_i \ge w+1$)に関して$O({(\max A_i)}^2)$で更新すればよい。 ただし$w+1 \lt A_i$なTシャツでも$w+1$回のみ着ることができるので、Tシャツに関して前処理をして、$\max A_i$個のTシャツとして整理しておく。 よって全体で$O({(\max A_i)}^3)$となる。

implementation

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
#define whole(f,x,...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)
typedef long long ll;
using namespace std;
template <class T> void setmin(T & a, T const & b) { if (b < a) a = b; }
const ll inf = ll(1e18)+9;
int main() {
    int n; ll m, c; cin >> n >> m >> c;
    vector<int> a(n); vector<ll> b(n); repeat (i,n) cin >> a[i] >> b[i];
    const int a_max = *whole(max_element, a);
    ll ans = inf;
    vector<ll> dp(pow(a_max+3, 2), inf);
    dp[0] = 0;
    repeat (w, a_max) { // the number of washing
        ll step = inf;
        int best_a = 1; ll best_b = inf;
        repeat (i,n) {
            if (w+1 <= a[i]) setmin(step, b[i]);
            int cand_a = min(w+1, a[i]); ll cand_b = b[i];
            if (cand_b/(double)cand_a < best_b/(double)best_a) {
                best_a = cand_a;
                best_b = cand_b;
            }
        }
        repeat (t,dp.size()) {
            if (dp.size() <= t + w+1) break;
            setmin(dp[t + w+1], dp[t] + step);
        }
        ll k = max<ll>(0, (m -(ll) dp.size()) / best_a + 1);
        setmin(ans, c*w + k*best_b + dp[m-k*best_a]);
    }
    cout << ans << endl;
    return 0;
}

golfテクを4つ紹介する

,

適当な基準で$4$つ選びました。

C言語 三項演算子cast

三項演算子の第$2,3$項目の型が一致することを用いてcastできる。

main(ptr) {
    *ptr; // error: invalid type argument of unary ‘*’ (have ‘int’)
    *(0?"":ptr); // ok
}

http://golf.shinh.org/reveal.rb?Merge+Digits/nu%28tails%29_1461951633&c (tailsさん)

o;main(p,q){for(;~scanf("%ms%s"+o,&p,q);putchar(o?:10))o=*(0?"":bcmp(p,q)>0?p++:q++);}

perl/ruby/python 他言語経由での入力

読み取りに強い言語で入力を受けて処理本体が強い言語でevalすると短くなる場合がある。

http://atc002.contest.atcoder.jp/submissions/977052 (%20さん)

read N M P;python -c"print pow($N,$P,$M)"

参考として、普通に書くと:

n,m,p=map(int,input().split());print(pow(n,p,m))

bash 空白文字の差の利用

bashにとっては非空白文字だがwcにとっては空白文字であるといった認識の不一致がある文字が存在する。これを使えば'\の分を縮めることができる。

http://yukicoder.me/submissions/115983

垂直tab\vの例。tr n \ |wc -wから$1$byte縮む。

$ cat a.sh
tr n 
     |wc -w%

$ xxd a.sh
00000000: 7472 206e 200b 7c77 6320 2d77            tr n .|wc -w

sed等 改行文字の修正

いくらかのサービスでは提出時の改行コードが\r\nとなる。改行が他の文字で代替できない言語で問題になる。 しかし、(特にAtCoderでのそれは)ブラウザを介さず直接POSTすることで回避できる場合が多い。

つまりHTTP requestをブラウザを介さず発行すればよいため、適当な提出用scriptを借りてくるだけで回避できる。 いったん普通に提出しブラウザのDevelopper toolsのCopy as cURL機能を用いてcurlコマンドを得て%0D%0A%0Aに置換して実行するのでもよい。


AtCoder Regular Contest 064: E - Cosmic Rays

,

http://arc064.contest.atcoder.jp/tasks/arc064_c

なんでこれが$3$問目なんだICPC国内予選か?という印象。ABCの方の$4$問目の調整のために$2$問目とswapしたのだろうか。

solution

dijkstra。$O(V^2)$。

implementation

$O(E \log V)$でなく$O(V^2)$のオリジナルDijkstraが言及されていたので書いてみた。$E = V^2$なケースではこちらが単純かつ高速。

#include <cstdio>
#include <vector>
#include <algorithm>
#include <numeric>
#include <tuple>
#include <cmath>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
#define whole(f,x,...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)
using namespace std;
template <class T> void setmin(T & a, T const & b) { if (b < a) a = b; }
template <typename T>
vector<T> original_dijkstra(vector<vector<pair<int, T> > > const & g, int start, T inf) {
    int n = g.size();
    vector<double> dist(n, inf);
    vector<int> ixs(n); whole(iota, ixs, 0);
    dist[start] = 0;
    repeat (loop,n) {
        int i; {
            auto it = whole(min_element, ixs, [&](int i, int j) { return dist[i] < dist[j]; });
            i = *it;
            *it = ixs.back();
            ixs.pop_back();
        }
        for (auto it : g[i]) {
            int j; T cost; tie(j, cost) = it;
            setmin(dist[j], dist[i] + cost);
        }
    }
    return dist;
}
int main() {
    int sx, sy, gx, gy, n; scanf("%d%d%d%d%d", &sx, &sy, &gx, &gy, &n);
    vector<int> x(n), y(n), r(n); repeat (i,n) scanf("%d%d%d", &x[i], &y[i], &r[i]);
    x.push_back(sx); y.push_back(sy); r.push_back(0);
    x.push_back(gx); y.push_back(gy); r.push_back(0);
    vector<vector<pair<int, double> > > g(n+2);
    repeat (i,n+2) repeat (j,n+2) g[i].emplace_back(j, max(0.0, sqrt(pow(x[j] - x[i], 2) + pow(y[j] - y[i], 2)) - r[i] - r[j]));
    auto dist = original_dijkstra(g, n, double(INFINITY));
    printf("%.10lf\n", dist[n+1]);
    return 0;
}

AtCoder Regular Contest 064: D - An Ordinary Game

,

http://arc064.contest.atcoder.jp/tasks/arc064_b

しばらく考えて分からなかったのですぐに解法を見てしまった。

solution

最終結果の偶奇。$O(1)$。

文字列$s$から始めて最終的にどのような文字列で終わるかを考える。 文字がどれも消せないのは(元々消せない両端に依存して)abababaあるいはababababのような形。 消す順番で間に挟む文字や長さは変化しうるが、両端の文字が一致していれば奇数長、そうでなければ偶数長というのは変わらない。 毎ターン長さが$1$ずつ縮むので、始めの長さの偶奇と合わせて勝者は定まる。

つまり誰がどう戦っても勝者は$s$によって同じ。

implementation

#!/usr/bin/env python3
s = input()
g = (s[0] == s[-1]) ^ (len(s) % 2 != 0)
print(['Second', 'First'][g])

AtCoder Regular Contest 064: C - Boxes and Candies

,

http://arc064.contest.atcoder.jp/tasks/arc064_a

solution

貪欲。$O(N)$。

$i$番目まで条件を満たしていて$a_i + a_{i+1} \ge x$とする。 $a_i$と$a_{i+1}$のどちらかを減らすのだが、$a_i$を減らすことに意味はないため$a_{i+1}$を減らせばよい。 $a_{i+1} \ge 0$の制約があることに注意。

implementation

#!/usr/bin/env python3
n, x = map(int, input().split())
a = list(map(int, input().split()))
ans = 0
for i in range(n-1):
    delta = max(0, a[i] + a[i+1] - x)
    a[i+1] -= delta
    if a[i+1] < 0:
        a[i] += a[i+1]
        a[i+1] = 0
    ans += delta
print(ans)

Yukicoder No.453 製薬会社

,

http://yukicoder.me/problems/no/453

solution

線形計画問題。$O(1)$。

問題を整理すると: $$ \begin{array}{cc} \text{max:} & 1000a + 2000b \\ \text{sub to:} & \frac{3}{4}a + \frac{2}{7}b \le C \\ & \frac{1}{4}a + \frac{5}{7}b \le D \\ & a, b \ge 0 \end{array} $$

最適解になりうるのは多面体の頂点のみである。 つまり、以下の$4$本の直線の交点を全て試せば答えが見つかる。 $$ \begin{array}{c} \frac{3}{4}a + \frac{2}{7}b = C \\ \frac{1}{4}a + \frac{5}{7}b = D \\ a = 0 \\ b = 0 \end{array} $$

implementation

#!/usr/bin/env python3
c, d = map(int, input().split())
a0 = min(c * 4/3, d * 4/1)
b0 = min(c * 7/2, d * 7/5)
a = 4/13 * (5*c - 2*d)
b = 7/13 * (3*d - c)
if a < 0 or b < 0:
    a, b = 0, 0
print(max([ 1000*a0, 2000*b0, 1000*a + 2000*b ]))

Yukicoder No.452 横着者のビンゴゲーム

,

http://yukicoder.me/problems/no/452

solution

ビンゴになる行/列/対角線の組について全部試す。$O(N^3M^2)$。

$k \in mathbb{N}$で、任意の集合$X \subset \mathbb{N}$が$|X| \le k$ならばがふたり以上をビンゴさせない、を満たす$N$の最大値を求める。 人$i$のビンゴカードの行/列/対角線の集合を$B_i$とすると、$k$の条件は$i \ne j$として任意の$x \in B_i, y \in B_j$に対し$| x \cup y | \gt k$と書ける。 これは$i,j,x,y$を全て試すことができて$k$が求まる。 $0 \le i,j \lt M$かつ$x \in B_i,B_j$なら$|x| = N$なので、全体として$O(N^3M^2)$であり、$NM \le 400$の制約があるので間に合う。

implementation

#include <iostream>
#include <vector>
#include <algorithm>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
#define whole(f,x,...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)
using namespace std;
template <class T> void setmin(T & a, T const & b) { if (b < a) a = b; }
template <typename X, typename T> auto vectors(X x, T a) { return vector<T>(x, a); }
template <typename X, typename Y, typename Z, typename... Zs> auto vectors(X x, Y y, Z z, Zs... zs) { auto cont = vectors(y, z, zs...); return vector<decltype(cont)>(x, cont); }
int main() {
    int n, m; cin >> n >> m;
    auto c = vectors(m, n, n, int());
    repeat (i,m) repeat (y,n) repeat (x,n) cin >> c[i][y][x];
    vector<vector<vector<int> > > bingo(m);
    repeat (i,m) {
        repeat (y,n) {
            vector<int> row = c[i][y];
            bingo[i].push_back(row);
        }
        repeat (x,n) {
            vector<int> col(n);
            repeat (y,n) col[y] = c[i][y][x];
            bingo[i].push_back(col);
        }
        repeat (p,2) {
            vector<int> diag(n);
            repeat (z,n) diag[z] = c[i][z][p ? z : n-z-1];
            bingo[i].push_back(diag);
        }
        for (auto & it : bingo[i]) {
            whole(sort, it);
        }
    }
    int ans = 2*n;
    repeat (i,m) for (auto & x : bingo[i]) {
        repeat (j,i) for (auto & y : bingo[j]) {
            vector<int> z;
            set_union(x.begin(), x.end(), y.begin(), y.end(), back_inserter(z));
            setmin<int>(ans, z.size()-1);
        }
    }
    cout << ans << endl;
    return 0;
}

Yukicoder No.451 575

,

http://yukicoder.me/problems/no/451

まだアドベコン全体としては終わってないが、個々の問題の解説は公開されてるようだ。

solution

条件式を展開すると:

$$ \begin{array}{l} b_{2i } = a_{2i } - a_{2i+1} \\ b_{2i+1} = a_{2i+1} + a_{2i+2} \end{array} $$

整理して:

$$ \begin{array}{l} a_1 = a_1 \\ a_{2i+2} = - a_{2i+1} + b_{2i+1} \\ a_{2i+1} = a_{2i} - b_{2i} \end{array} $$

これに加えて制約 $$ \forall i. 1 \le a_i \le 10^{18} $$ があるので、$a_1$を適当に決めて各$a_i$がこの範囲に収まるようにしたい。

$a_1$を動かした時の他の項の変化を見ると:

$$ \begin{array}{l} a_1 = a_1 \\ a_2 = - a_1 + b_1 \\ a_3 = - a_1 + b_1 - b_2 \\ a_4 = a_1 - b_1 + b_2 + b_3 \\ a_5 = a_1 - b_1 + b_2 + b_3 - b_4 \\ a_6 = - a_1 + b_1 - b_2 - b_3 + b_4 + b_5 \vdots \end{array} $$

であるので、$\lfloor \frac{i}{2} \rfloor$の偶奇によって各項に対し$\pm 1$倍の線形で効いてくる。 適当な$a_1 = 0$としていったん計算して各項で$1 \le a_i + k a_0 \le 10^{18}$とすれば$a_0$の動く範囲が得られる。 この範囲が空であるかどうかを見て空でなければ適当に取り出して計算すればよい。

implementation

#!/usr/bin/env python3
n = int(input())
b = [ int(input()) for _ in range(n) ]
def f(a1):
    a = [ None ] * (n+1)
    a[0] = a1
    for i in range(n):
        if (i+1 + 1) % 2 == 0:
            a[i+1] = - a[i] + b[i]
        else:
            a[i+1] = a[i] - b[i]
    return a
lower = 1
upper = 10**18
a = f(0)
for i in range(n+1):
    if ((i+1) // 2) % 2 == 0:
        lower = max(lower, 1      - a[i])
        upper = min(upper, 10**18 - a[i])
    else:
        lower = max(lower, a[i] - 10**18)
        upper = min(upper, a[i] - 1     )
if lower <= upper:
    print(n+1)
    for ai in f(lower):
        print(ai)
else:
    print(-1)

Yukicoder No.450 ベー君のシャトルラン

,

http://yukicoder.me/problems/no/450

何も考えず愚直を書いたらTLE/WAしました。

誰かが引っかかってくれるかもしれないと思って作った問題でしたが、再考してみれば当たり前だろ・・・となりました。難しいものですね。引っかかってくれた人に(いらっしゃったら)感謝申し上げます。

はい。

#!/usr/bin/env python3
vl, vr = map(int, input().split())
d = int(input())
w = int(input())
t = d / (vl + vr)
print(w * t)

CODE FESTIVAL 2016 Elimination Tournament Round 2: A - 迷子の高橋君 / Takahashi is Missing!

,

http://cf16-tournament-round2-open.contest.atcoder.jp/tasks/asaporo_e

実績解除: editorialを撃墜

solution

漸化式を立てて解いて$O(1)$。

青木君が座標$0$、高橋君が座標$x$にいる状態からの期待値を$f(x)$とする。

自明に$f(0) = 0$である。 $0.01 \le p \le 1$であるようにしておいて、高橋君とすれ違う危険がない場合は近付くべきなので$f(x+2) = 1 + pf(x) + (1-p)f(x+2)$となる。 整理すると$f(x+2) = \frac{1}{p} + f(x)$である。偶数のときはこのまま$f(2x) = \underbrace{\frac{1}{p} + \frac{1}{p} + \dots + \frac{1}{p}}_{x \; \text{times}} + f(0) = \frac{x}{p}$。 $f(1)$のときは少し面倒であるが、すれ違ってしまうと必ずしも捕まえられなくなるので動くべきではなく、$f(1) = 1 + (1-p)f(2) = 1 + \frac{1-p}{p} = \frac{1}{p}$となる。 あるいは$x$が奇数の時は初手で$1$ターン足踏みして偶奇を揃えると考えてもよい。 両方を合わせると$f(x) = \lceil \frac{x}{2} \rceil \cdot \frac{1}{p}$となる。

implementation

#!/usr/bin/env python3
import math
x = int(input())
p = int(input())/100
print(math.ceil(x / 2) / p)