C. Nastya and Strange Generator (Codeforces Round #637 Div. 2)

問題

https://codeforces.com/contest/1341/problem/C

問題概要

幅nの区画が横一列に並んでいて、左から順に1, 2, 3, ..., nである。

各区画に改めて別の番号を1から順に振っていく。その番号を振る際のルールは以下の通り。

• 各区画について、自分を含めて自分より右側にあって、まだ番号が振られていない区画のうち最も左にあるものの元の番号をリストに入れる
• リストの中の最瀕値である区画に新しい番号を振る
  • 最瀕値が複数ある場合、その中で任意に選択可能

（よくわからない場合は、問題のNoteを参照してください）

さて、振り直した後の番号（順列）が与えられるので、上記のルールで構築可能かどうか答えよ。

考察

これは実際に試してみればわかるのですが、最初は1を任意の場所に入れることができます。しかし、2は1の右隣にしか入れられず、3は2の右隣にしか入れられず、というのを右端に来るまで繰り返すことになります。右端まで到達すると、次の数字は任意の場所に入れることができますが、その次はまた右隣、というのを繰り返します。

結局、構築可能な順列は、ある項から右隣を見た時、一つ増加しているか、あるいは減少しているかのいずれかでなければなりません。つまり、いずれかの項の右隣が2以上増加している場合、構築不可能となります。

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; i++) cin >> a[i];
        bool ok = true;
        for (int i = 0; i < n - 1; i++){
            if (a[i] + 1 < a[i + 1]) {
                ok = false;
                break;
            }
        }
 
        cout << (ok ? "Yes" : "No") << endl;
    }
}

B. Nastya and Door (Codeforces Round #637 Div. 2)

Nastya was very confused じゃあないんだよ。困惑してるのはこっちだよ。

問題

https://codeforces.com/contest/1341/problem/B

問題概要

峠を境に地区が分かれている地域がある。

その地域の幅nの区間ごとの標高と、幅kが与えられるので、幅kの中に含むことのできる最大の地区数と、その時のkの左端を答えよ。ただし候補が複数あるときは最も左側のものを採用すること。

考察

要するに、幅kの中に峠がいくつあるかを調べて、それが一番大きいものが答えとなります。

各地点が峠であるかどうかは、a[i-1] < a[i] and a[i] > a[i + 1]で判別可能です。

あとは左端から幅kの区間に峠がいくつ含まれるかを全探索していけばよいですが、都度峠であるかどうかを見ると計算量がO(nk)になって間に合いません。なので、峠の数を累積和で前処理しておいてO(1)で取り出せるようにしておけばよいです。

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, k;
        cin >> n >> k;
        vector<int> a(n);
        for (int i = 0; i < n; i++) cin >> a[i];
        vector<int> p(n);
        for (int i = 1; i < n - 1; i++) {
            // 峠なら1になる
            if (a[i] > a[i - 1] and a[i] > a[i + 1]) p[i] = 1;
        }
        vector<int> sum(n + 1);
        for (int i = 1; i < n; i++) {
            sum[i + 1] = sum[i] + p[i];
        }
        int ans = 0;
        int ansl = 0;
        for (int i = 0; i < n - k + 1; i++) {
            // 数える時、両端を含まないことに注意
            if (ans < sum[i + k - 1] - sum[i + 1]) {
                ans = sum[i + k - 1] - sum[i + 1];
                ansl = i;
            }
        }
        // 分割後の数は峠の数 + 1、座標は0-indexed -> 1-indexedなので、それぞれ1を足している
        cout << ans + 1 << " " << ansl + 1 << endl;
    }
}

A. Nastya and Rice (Codeforces Round #637 Div. 2)

問題

https://codeforces.com/contest/1341/problem/A

問題概要

n個の袋があり、袋一つの重さはa-bからa+bの間であり袋n個全体の重さはc-dからc+dの間であるという。

n, a, b, c ,dが与えられるので、上記の条件を満たしているかどうかを答えよ。

考察

(a-b) * nから(a+b) * nの区間がc-dからc+dの区間に重なっていれば満たすし、重なっていれば満たしません。

これを言い直すと、(a-b) * nがc+dより大きいか(a+b) * nがc-dより小さい場合満たさない、となります。なので、それを実装すればよいです。

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, a, b, c, d;
        cin >> n >> a >> b >> c >> d;
        cout << (n * (a - b) > c + d or n * (a + b) < c - d ? "No" : "Yes") << endl;
    }
}

反省

上記のコードはこの記事を書く時に改めて書き直したもので、実戦では慌ててもうちょっと複雑で不必要な場合分けをしてしまいました。

こういう条件はノータイムで出てくるようにならないと・・・。

B. Balanced Array (Codeforces Round #636 Div. 3)

問題

https://codeforces.com/contest/1343/problem/B

問題概要

偶数nが与えられる。以下の条件を満たす長さnの数列を一つ構築せよ。なお、構築可能であるかどうかは保証されない。

• 前半のn/2個の要素は偶数である
• 後半のn/2個の要素は奇数である
• すべての要素はすべて相異なる正数である
• 前半のn/2個の要素の和と後半のn/2個の要素の和が等しくなる

考察

n/2が奇数となる場合、前半のn/2個の要素の和は偶数で後半のn/2個の要素の和は奇数となるので構築不可能です。

n/2が偶数となる場合は適当に構築します。

私は前半を2, 4, 6, ...., nと並べて後半を1, 3, 5, ...., n - 1 + n/2と並べました。機械的に1, 3, 5, ...., n - 1と並べた時点で、n/2だけ少ないので最後にn/2を足すことで調整します。

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        if ((n / 2) % 2 == 1) {
            cout << "NO" << endl;
        } else {
            cout << "YES" << endl;
            for (int i = 1; i <= n / 2; i++) {
                cout << i * 2 << " ";
            }
            for (int i = 0; i < n / 2 - 1; i++) {
                cout << i * 2 + 1 << " ";
            }
            cout << n - 1 + (n / 2) << endl;
        }
    }
}

実は・・・

考え方自体は上の考察のとおりなのですが、実はn - 1 + n/2という式は立てておらず、ちょっと違う実装となっています。

Submission #77494353 - Codeforces

↑この実装、まずいところがあります。（この問題の制約だと最終的に答えは合うのですが）

お暇な方はどこがおかしいか見つけてみてください。

A. Candies (Codeforces Round #636 Div. 3)

問題

https://codeforces.com/contest/1343/problem/A

問題概要

のときを満たすようなxを一つ求めよ。

考察

与えられた式を変形するととなります。よってがnの約数となるようなkを見つけてきてをすればよいです。

kは2から順に一つずつ見ていけばよいです。なので、kはたかだか29までとなります。

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        int k = 2;
        while (n % ((int)pow(2, k) - 1) != 0) k++;
        cout << n / ((int)pow(2, k) - 1) << endl;
    }
}

個人的反省

算数力のなさを遺憾なく発揮して式変形に時間をかけてしまい、A問題なのに10分以上かかってしまいました。結果はともかくとして、立ち回りとしてはこれを後回しにしてまずBを見るべきでしたね。

B. Yet Another Meme Problem (Educational Codeforces Round #80)

問題

https://codeforces.com/contest/1288/problem/B

問題概要

conc(a, b)を、aとbを連結したものを返す関数として定義する。例えばconc(12,23) = 1223であり、conc(100,11) = 10011である。

2つの正の整数A, Bが与えられるので、1 <= a <= A, 1 <= b <= Bであるa, bの組のうち、a * b + a + b = conc(a, b)を満たすものの個数を答えよ。

考察

式変形をしていきます。

まず関数concは（|b|はbの文字数とする）と表すことができます。

なのでとなります。

両辺に+ bがあるので取っ払ってです。

左辺をaでくくるととなり、両辺をaで割ると（aは正数なので大丈夫です）となります。

ここで、式を成り立たせるためにaの値は実はなんでもいいことがわかります。また、右辺は10のべき乗であり、bは9, 99, 999のような数のみ取りうることがわかります。

よって答えるべき組み合わせの数は、Aと、B以下ですべての桁が9である数の個数をかけ合わせたものとなります。

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int t;
    cin >> t;
    while (t--) {
        long long a;
        string b;
        cin >> a >> b;
        long long l = b.size();
        for (char c : b) {
            if (c != '9') {
                l--;
                break;
            }
        }
        cout << a * l << endl;
    }
}

AtCoder Beginner Contest 163

うーん、Unratedですか・・・。まあ仕方なし。

各問題

A - Circle Pond

円の周長は直径×πで、与えられるのは半径Rなので、答えはR * 2 * πです。πは言語で提供されている定数があるならそれを使いましょう。定数がなければ、この問題は「絶対誤差または相対誤差が 以下であれば正解として扱われる」ので、3.1415くらいまで掛けておけば安心安全でしょう。

B - Homework

宿題をしなければならない日数を夏休みの期間から引いたものが遊べる日数なので、NからすべてのAを引けば答えです。ただし、これが負の数になった場合は夏休みの間に宿題が終わらなかったということなので、計算結果のかわりに-1を出力します。また0のときは0を出力するべきであることにも注意です。

C - management

与えられるのは上司の番号ですから、ある番号が出現した数がすなわちある番号の社員の直属の部下の数となります。なので、番号ごとに集計して、それを1から順に出力すればよいです。

見た目グラフの問題っぽいんですけど全然そんなことはなく、Bで出てもおかしくないようなレベルの問題でした。

D - Sum of Large Numbers

この問題、もし0からNまでのN+1個の数だとしたら話は簡単で、例えば入力例1の3 2の場合だと、2個で作れる最小の数0 + 1 = 1から、すべてを使って作れる最大の数0 + 1 + 2 + 3 = 6の間の数をすべて作ることができるので、答えは6通りとなります。

しかし、この問題はからN+1個の数が対象です。よって、出力例1の解説にあるとおり足す個数分のが余計に加算されます。なので、場合の数は足す個数ごとにわけて考える必要があります。

入力例1の場合、まず最低条件の2個で考えると、最小は小さい方から二つ取る0+1=1で、最大は大きい方から二つ取る2+3=5なので、5通りです。3個のときは最小が0+1+2=3で最大が1+2+3=6なので4通りです。最後に4個すべて取る場合は考えるまでもなく1通りです。よって合計すると10通りとなります。

やることは等差数列の和ですから、各個数毎にO(1)で求めることができて、最終的な答えはそれをKからN+1までについて求めて合計する必要があり、全体でO(N)で答えを求めることができます。

残りの問題

Unratedになっちゃったのでまだ見てません。（おい

まとめ

参加者の増加が想定を超えてしまっているっぽいので（先週のすぬけさんのツイートで、10000人を超えることがレート実装時（？）には想定されていなかったことが判明しました）、こういうこともありますかね。

自分としては参加し続けることくらいでしか貢献できないので、来週も当たり前に参加し続ける予定です。