yukicoder no.349/350/351/352 参加した

今回はコンテスタントとして参加。

結果

f:id:pakapa104:20160312133716p:plain

初の全完。イェイ。

今回は☆3までだったのでなんとかなったという部分もある。

No.349 干支の置き物

12種類の干支の置物がある。それぞれの個数が与えられたとき、同じ種類の置物が隣り合わないように横1列に並べることができるか判定せよ、という問題。

最も個数が多い種類の個数をmaxnとすると、その間に他の種類の置物を1つずつ置ければ題意を満たします。よってN - maxn >= floor(n / 2)であるかを判定すればOK。

from collections import Counter

n = int(input())
a = [input() for i in range(n)]
cnt = Counter(a)
ma = max(cnt.values())
if n - ma >= n // 2:
    print("YES")
else:
    print("NO")

No.350 d=vt

誤差ゲー。floatでそのまま計算すると答えがずれるっぽかったので、vの小数部分を整数として読み込む(×10000に相当)→v × t / 10000としました。

v, t = input().split()
t = int(t)
v = int(v.split('.')[1])
d = v * t // 10000
print(d)

No.351 市松スライドパズル

盤面全体をシミュレーションしていると間に合わない。最後に必要なのは左上のマスだけなので、このマス最初どこにあったかを逆順にシミュレーションすることで求め、その最初の位置の色を答えればOK。

int H, W;
int N;
char q[1000010];
int a[1000010];

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    cin >> H >> W;
    cin >> N;
    rep(i, N) {
        cin >> q[i] >> a[i];
    }

    int r = 0, c = 0;
    rrep(i, N) {
        if (q[i] == 'R' && a[i] == r) {
            c = (c + W - 1) % W;
        } else if (q[i] == 'C' && a[i] == c) {
            r = (r + H - 1) % H;
        }
    }
    if ((r + c) % 2 == 0) {
        printf("white\n");
    } else {
        printf("black\n");
    }
}

No.352 カード並べ

期待値の問題だが、DPせず数学だけで解ける。まず期待値の線形性より、E(1からNまでのカードを置くのにかかるコスト) = E(1のカードを置くときにかかるコスト) + ... + E(Nのカードを置くときにかかるコスト) です。E(X) = (Xのカードを置くときにかかるコスト) とすると、E(X)はX - 1までの並べ方によらず計算することができます。なぜならカードの置き方はすべてランダムなので、例えば3枚目までのカードを並べたとき123, 132, 213, ...となる確率は等しいからです。

E(X)は以下のように求められます。まず、両端に置くときのコストは1 * 2 / Xです。カードの間に置くときは、1と2の間、1と3の間、...、1とXの間、2と3の間、...が等確率で起こることを用いればO(X^2)で計算できます。今回はNが20までなのでこれで十分間に合います。

signed main() {
    int N;
    cin >> N;
    double ans = 2;
    rep2(k, 3, N + 1) {
        ans += 2.0 * 1 / k;
        double temp = 0;
        rep2(j, 1, k) {
            rep2(i, 1, j) {
                temp += i * j;
            }
        }
        temp /= 1.0 * (k - 1) * (k - 2) / 2;
        temp *= (1 - 2.0 / k);
        ans += temp;
    }
    printf("%.10f\n", ans);
}