yukicoder 星1.5〜2をランダムに解いた

2019-03-24

題名通り、ジャンル・時系列バラバラ。

体感的にAtCoderのレベルに例えればABCのB〜Cぐらいだと思われる。おれのようにC問題が安定せずくすぶっている人は、気晴らしに解いてみるといいかもしれない。

問題リスト

No.8 N言っちゃダメゲーム

コメントを見てもらえればいいと思う。外側のifブロックはたぶんいらない。

signed main() {
    int n;
    cin >> n;
    rep(i, 0, n) {
        int n, k;
        cin >> n >> k;
        string ans;
        if (n <= k) {
            ans = "Win";
        } else {
            // ゲーム開始前、後攻は0を宣言しているものとする。
            // 相手に負けさせるには、n-1を宣言したい。
            // offset：k+1
            // そのためにはn-1-offsetを宣言したい。そのためには...宣言したい数字が0以下になるまでループ。
            // 0未満になったら先行が勝者。0ちょうどなら後攻が勝者。
            ans = ((n - 1) % (k + 1) == 0 ? "Lose" : "Win");
        }
        cout << ans << endl;
    }
}

No.47 ポケットを叩くとビスケットが2倍

叩く回数をT回だとすると、2 ^ (T-1) 〜 2 ^ T の範囲内にあるビスケットを生み出せる。ポケットの中身から任意の枚数取り出して、2倍する元手を好きなように制御できるからだ。

signed main() {
    int n;
    cin >> n;
    if (n == 1) {
        puts("0");
        return 0;
    }
    rep(i, 1, INF) {
        if (1 << i <= n && n <= 1 << (i + 1)) {
            cout << i + 1 << endl;
            return 0;
        }
    }
}

No.51 やる気の問題

愚直にシミュレーション。

signed main() {
    int w, d;
    cin >> w >> d;
    for (int i = d; i > 0; i--) {
        int a = w / pow(i, 2);
        if (i != 1) w -= a;
    }
    cout << w << endl;
}

No.57 ミリオンダイス

サンプルからなんとなく 3.5 * N かなと思ったが通ってしまった。
こういうのを期待値の線型性というらしい。期待値計算は苦手だ。

signed main() {
    double n;
    cin >> n;
    cout << 3.5 * n << endl;
}

No.88 次はどっちだ

駒の色は関係ない。総数を見ることで次の手番が誰なのかがわかる。

signed main() {
    string first;
    cin >> first;
    string second = (first == "oda" ? "yukiko" : "oda");
    int k         = 0;
    rep(i, 0, 8) rep(j, 0, 8) {
        char c;
        cin >> c;
        if (c != '.') k++;
    }

    cout << (k % 2 == 0 ? first : second) << endl;
}

No.83 最大マッチング

タイトル詐欺。これをめっちゃ難しくした類題は https://atcoder.jp/contests/abc118/tasks/abc118_d 。
桁数を最大化すればそれだけ数字をデカくできるから、コストの一番低い1を並べていく。ただし、マッチの総数が奇数の場合は1本余ることになるので、3本で作れる7を先頭の1と取り替える。

signed main() {
    int n;
    cin >> n;
    string ans;
    int one = n / 2;
    if (n % 2 != 0) {
        ans += '7';
        one--;
    }
    rep(i, 0, one) {
        ans += '1';
    }
    cout << ans << endl;
}

No.149 碁石の移動

AからBに移動させる石にはすべての黒を含めるようにし、それでも補填しきれない場合に限り白を含める。同様に、BからAに移動させる石にはできるだけの白を含める。簡単な問題のはずなのに延々とバグらせていた。何やってんだか。

signed main() {
    int aw, ab, bw, bb;
    cin >> aw >> ab >> bw >> bb;
    int c, d;
    cin >> c >> d;
    if (c > ab) {
        int diff = c - ab;
        aw -= diff;
        bw += diff;
    }
    aw += min(d, bw);
    cout << aw << endl;
}

No.477 MVP

これもサンプルを見て直感的に通した。注意すべきは確実にK位以内に入るために+1余計にダメージを与えること…って見りゃわかるか。

signed main() {
    int n, k;
    cin >> n >> k;
    cout << n / (k + 1) + 1 << endl;
}

No.657 テトラナッチ数列 Easy

漸化式をメモ化再帰してからクエリに高速に答える。この発想を難易度の高い問題にもすぐに応用できたら、もっとましな成績になるのだろうが。

vector<int> tetra(1000100, 0);

void init() {
    tetra[0] = tetra[1] = tetra[2] = 0;
    tetra[3]                       = 1;
    rep(i, 4, (int)tetra.size()) {
        tetra[i] = (tetra[i - 1] + tetra[i - 2] + tetra[i - 3] + tetra[i - 4]) % 17;
    }
}

int at(int n) {
    return tetra[--n];
}

signed main() {
    init();
    int q;
    cin >> q;
    rep(i, 0, q) {
        int n;
        cin >> n;
        cout << at(n) << endl;
    }
}