Mister雑記

競プロ記事がメインになりますが、内容は気分次第です。

ARC100 (ABC102) 解説

いつもよりちょっとだけ早かった1週間振りのABC/ARC。 配点は先週同様violence、果たしてMisterの人権やいかに......?

まぁ言ってしまうとC, Dの2完だったのでいつも通りA〜Dの4問を解説します。

目次

本編

A - Multiple of 2 and N

概要

問題リンク

 2 Nのどちらでも割り切れる最小の正整数を出力せよ。

制約

  •  1 \leq N \leq 10^{9}

解説

まず Nで割り切れるという条件の時点で答えは Nの倍数となる。

よって答えの最小値は Nなわけで、 N 2で割り切れる場合(つまり Nが偶数の場合)はそれが答えになる。

一方奇数の場合はより小さい値を掛けて偶数にしたいわけだから、 2を掛けて 2Nが答えとなる。

回答例

#include <iostream>

using namespace std;

int main() {
    int N;
    cin >> N;
    if (N % 2 == 0) {
        // Nが偶数の場合はNが答え
        cout << N << endl;
    } else {
        // Nが奇数の場合は2Nが答え
        cout << N * 2 << endl;
    }
    return 0;
}

ちなみに今後はA,B問題に関しては、define系のマクロを一切使わないコードを載せることにする。

B - Maximum Difference

概要

問題リンク

長さ Nの数列 Aが与えられる。 Aの異なる2要素の差で、絶対値が最大のものを求めよ。

制約

  •  2 \leq N \leq 100
  •  1 \leq A_i \leq 10^{9}

解説

2要素の絶対値が最大となるのは、 A中の最大値と最小値を取ったときになる。よって Aの最大値と最小値を求めればその差が答えとなるわけだが、これは

  • 最大値と最小値を更新していく
  • ソートして先頭と末尾の要素を取る

の2つの方法が主に考えられる。計算量を比較すると前者は O(N)、後者は O(N \log N)で後者の方が若干遅いが、どちらにせよ余裕で通るので問題ない1

回答例その1: 最大値と最小値の更新

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    int N;
    cin >> N;
    
    int ma = 0, mi = 1e9 + 10;
    // maが最大値、miが最小値
    
    for (int i = 0; i < N; i++) {
        int A;
        cin >> A;
        
        // 最大値、最小値を更新
        ma = max(ma, A);
        mi = min(mi, A);
    }
    cout << ma - mi << endl;
    return 0;
}

制約から最大値は0以上、最小値は 10^{9}以下と確定しているので上のような初期値で問題ない。ただし最小値の初期値を 10^{10}とかにするとint型ではオーバーフローを起こすので注意。

なおmaxminはalgorithmライブラリに入っているのでわざわざ実装する必要はない。

回答例その2: ソート

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
    int N;
    cin >> N;
    
    vector<int> A(N);
    // 入力を記録する配列
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }
    
    sort(A.begin(), A.end());
    // Aを昇順にソート
    
    cout << A.back() - A.front() << endl;
    // A.back()でAの末尾、A.front()でAの先頭が取り出せる
    
    return 0;
}

vectorは言うなれば「長さを変えられる配列」で、配列の上位互換と言っても過言ではない(果たしてそうでしょうか)。B問題レベルではvectorはまだ難しいかもしれないが、D問題以降では使用頻度が格段に増すので今のうちに使えるようになっておくと後々有利。Google先生を頼っていこう。

なおsortもalgorithmライブラリに入っていて、引数にイテレータを渡すことで範囲を指定する。第3引数に関数を渡せば並び替え方の指定も出来たりしてとても便利。

C - Linear Approximation

概要

問題リンク

長さ Nの数列 Aが与えられる。 bに対して「悲しさ」 s(b) \displaystyle
s(b) = \sum_{i=1}^{N} \left| A_i - (b + i) \right|
によって定めたとき、悲しさの最小値を求めよ。

制約

  •  1 \leq N \leq 2 \times 10^{5}
  •  1 \leq A_i \leq 10^{9}

解説

 s(b) A_iのindex2に依存しているが、上の定義式は書き直すと  \displaystyle
s(b) = \sum_{i=1}^{N} \left| (A_i - i) - b \right|
となるため、 B_i = A_i - iなる数列 Bを新たに作れば  \displaystyle
s(b) = \sum_{i=1}^{N} \left| B_i - b \right|
となり、indexに依存しない形になる。これでソートなどの順番を変える操作も行えるようになるので、以降 Bソート済みとする。

あとはこの「各要素の bからの距離」の総和を最小化したいわけだが、ここで Bの各値を二次元平面にプロットしてみる。横軸を i、縦軸を B_iとすると、以下のような具合になる。

f:id:misteer:20180702204749j:plain

さて、 bが上のように B_k B_{k+1}の間にあるとき、 bを1増やすと s(b)はどれだけ変化するだろうか?

f:id:misteer:20180702204806j:plain

結果は上のように、

  •  i \in [1, k]については距離が1増加
  •  i \in [k + 1, N]については距離が1減少

となるため、 s(b+1) - s(b) = k - (N - k)となる。ここで d(k) = 2k - Nとしておこう。

 k \dfrac{N}{2}前後で場合分けすると以下のようになる。

 k \lt \dfrac{N}{2}  k \gt \dfrac{N}{2}
 d(k) \lt 0  d(k) \gt 0
 s(b+1) \lt s(b)  s(b+1) \gt s(b)
 bを増やした方が得  bを減らした方が得

ここから k \fallingdotseq \dfrac{N}{2} s(b)が最小になることが分かるが、厳密にはどうなるだろうか。これは Nが偶数のケースと奇数のケースで場合分けする必要があるが、結論だけ言うと3どちらの場合も b = B_{\frac{N + 1}{2}}で最小となる(分数は切り捨て)。あとはこのときの s(b)を実際に計算すればACとなる。

計算量はソートがボトルネックとなり O(N \log N) O(N)中央値を出すアルゴリズムもあるらしいが、そこまでする必要はないだろう。

回答例

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

template <typename T>
using V = vector<T>;
using ll = long long;

#define FOR(i, a, b) for (ll i = (a); i < (b); i++)
#define NREP(i, n) FOR(i, 1, n + 1)
// Natural REP runs from 1 to n

/* ---------- ここまでマクロ ---------- */

int main() {
    ll N;
    cin >> N;
    
    V<ll> B(N + 1);
    // 入力ではなく、上で変換したBの方を記録(1-indexed)
    
    NREP(i, N) {
        ll A;
        cin >> A;
        B[i] -= A - i;
    }

    sort(B.begin() + 1, B.end());
    // B[0]はソート対象外
    
    ll b = B[(N + 1) / 2];
    // Bの中央値がbの最適値

    ll ans = 0;
    NREP(i, N) {
        ans += abs(B[i] - b);
    }

    cout << ans << endl;
    return 0;
}

分かってしまえば実装はさして苦でもない。0-indexedの場合はb = B[N / 2]で通るはず(私は本番そっちでやったので)。

別解1: 三分探索

先に上げた表を基準に s(b)のグラフを書いてみると、これは下に凸のグラフになっていることが分かる。こういった「凸性があるグラフについて極値を求めたい」というときに使えるのが「三分探索」というアルゴリズムである。ここでは詳しく解説しないが、興味がある方は調べてみるといいだろう。

このアルゴリズムを使う問題を1つ載せておく(ネタバレになるので問題名は伏せておく)。実のところ数学でも殴れる。

ちなみにこの解法でも探索で使う値を求めるのに O(N)、探索は二分探索同様 O(\log N)かかるので全体計算量は O(N \log N)となり、上の解法と同じになる。

別解2: 累積和

「最適な b B_1 \sim B_Nのどれかだろう」と目星をつければ、累積和を利用することで全探索が可能。具体的には b = B_kの場合 
s(B_k) = ((sum_N - sum_k) - (N - k)B_k) + ((k - 1)B_k - sum_{k - 1})

となる。ただし Bはソート済み、 sum_i = B_1 + \dots + B_iとする。

計算量は多少多いが問題となるレベルではないし、十分現実的な解法である。

D - Equal Cut

概要

長さ Nの数列 Aを3箇所で切って出来た4つの空でない数列について、それぞれの総和を P, Q, R, Sとする。このとき、「 P, Q, R, Sの最大値と最長値の差」の最小値を求めよ。

制約

  •  4 \leq N \leq 2 \times 10^{5}
  •  1 \leq A_i \leq 10^{9}

解説

まず何となく「 P, Q, R, S Aの総和を大体4等分するんだろうな〜」と考えて、

  • 和が Aの総和の1/4になるまで数列を伸ばして、超えたらその前後で切る

みたいな解法を思いつく。しかしそれではサンプルにあるケースがどうにも上手くいかないことに気づき、ここで行き詰まる。

次に注目したのが問題文。いわゆるメタ解きというやつ。

  • なぜカット数は変数ではなく3で固定なのか?
  •  Nの制約的に解法は O(N \log N)くらいだろう

の2点に注目した結果、

  1. まず Aの2つの切り方を全探索する。
  2. 各パートについて、なるべく2等分するような切断位置を二分探索で探す。

という解法に至った。これなら O(N \log N)で間に合うし、 先程考えた解法は4つだと上手くいかないが2つなら上手くいくことも証明できる4のでここで実装に移る。

二分探索する上でカットしたときの数列の区間和を O(1)で求める必要があるが、これは累積和を作っておけば大丈夫。

あと注意点として、数列をなるべく均等に2つに切ったときのそれぞれの和を前から P, Qとしたとき、  P \leq Q P \gt Qの2パターンを考える必要がある。 これは二分探索で境界となった値をどっちに入れるかを実際に試せばいい。

回答例

#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>

using namespace std;
template <typename T>
using V = vector<T>;
template <typename S, typename T>
using P = pair<S, T>;
using ll = long long;

#define FOR(i, a, b) for (ll i = (a); i < (b); i++)
#define NREP(i, n) FOR(i, 1, n + 1)
// Natural REP runs from 1 to n 

/* ---------- ここまでマクロ ----------- */

ll N;
V<ll> A(200010), sum(200010, 0);


// 閉区間[b, e]をできるだけ均等に2等分したときの、
// 各配列の総和をペアで返す
P<ll, ll> divide(ll b, ll e) {
    ll ok = b, ng = e;
    ll ds = sum[e] - sum[b - 1];

    // 二分探索で[b, ok]の和が[b, e]の半分以下になる最大のokを探す
    while (ng - ok > 1) {
        ll mid = (ok + ng) / 2;
        ll ps = sum[mid] - sum[b - 1];
        if (ps * 2 <= ds) {
            ok = mid;
        } else {
            ng = mid;
        }
    }

    // P <= Qの場合
    P<ll, ll> ret1 = make_pair(sum[ok] - sum[b - 1], sum[e] - sum[ok]);
    // P > Qの場合
    P<ll, ll> ret2 = make_pair(sum[ok + 1] - sum[b - 1], sum[e] - sum[ok + 1]);
    
    // 両者を比較
    if (ret1.first - ret1.second > ret2.second - ret2.first) {
        return ret1;
    } else {
        return ret2;
    }
}


// [0, itr)と[itr, N)に分割したときの最適解
ll cut(ll itr) {
    V<P<ll, ll>> psum(2);
    
    psum[0] = divide(1, itr);        // (P, Q)
    psum[1] = divide(itr + 1, N);    // (R, S)

    V<ll> elem;    // [P, Q, R, S]
    
    for (auto p : psum) {
        elem.push_back(p.first);
        elem.push_back(p.second);
    }

    sort(elem.begin(), elem.end());
    return elem.back() - elem.front();
    // 最大値と最小値の差を返す(B問題その2を参照)
}


int main() {
    cin >> N;
    NREP(i, N) {
        cin >> A[i];
        sum[i] = sum[i - 1] + A[i];
        // 同時に累積和も計算
    }

    ll ans = sum[N];

    FOR(i, 2, N - 1) {
        // 全ての2分割を試す(ただし分割後の要素数>=2)
        ans = min(ans, cut(i));
    }

    cout << ans << endl;
    return 0;
}

もう少しキレイに実装したいな〜という感じ。ちなみに上のコードをそのまま投げると通る。

確かに実装は重いが、「こどふぉに比べればマシか...」とか思いながら実装していた。バグがほとんど生まれなかったのはこどふぉ様々だろうか。

別解?: 尺取り法

別解というよりこちらがEditorialに載っていた解法なので上が別解なのだが、二分探索の部分は尺取り法で代用できる。 というのも2つに切ったあとでさらに2つに切るとき、切るべき位置は単調性があるため前回切った位置を覚えておけば続きから探索できるからだ。 この解法は O(N)で、上の方法より僅かだが速い。

この問題に限った話ではなく、累積和で境界を探す問題のときはにぶたんと尺取り法がどちらも使えることが多い。 尺取り法の方が \logの分だけ速いが例によって大した問題にはならないので、どちらを使うかはお好みで。

感想

前回D500が解けなかった翌週で今回D600と知ったときには死を悟ったが、なんとかなって助かった。 欲を言えばE700も解きたかったが、良い解法が浮かばず。パフォは2000乗ったので上々といったところか。

それにしても先週は学問と競プロに対するモチベが尋常じゃなく低かった。 睡眠不足か、栄養不足か、はたまたストレスか。分からん。


  1. そもそも競技プログラミングにおいて計算量 \logの差が致命的になることはほとんどないので、定数倍程度に思っていい。

  2. 数列中での位置。要素を A_iと表記したときの iのこと。

  3. ここに書いても助長な感じがしたので省きました。詳しい証明はHackMD版を見てください。

  4. 証明と言えるほど堅いものではないが、まぁ任意のケースでより優れてることを言うだけ。ちなみに A_i \leq 0の場合は成り立たない。その場合は O(N^{3})でしか解けないんじゃないかね。

Educational Codeforces Round #46

MacbookProの以前から若干イカレ気味だったreturnキーより先に、なぜか予告なくxキーが死んでしまいました。Misterです。

文字が消せないし何よりtmuxが起動できません。外付けキーボード買うか...。

何はともあれえでゅこんの解説です。今回は現実世界での実装が重かったセットでした。解説は私が本番中に通せたA~Dの4問まで。

HackMD版はこちら

目次

本編

A. Codehorses T-shirts

問題リンク

概要

服のサイズに関するデータが N個セットで2つ与えられる。

服のサイズは

  • Mのみ
  • X 0 \sim 3個続いたあとでSL

という計9種類の文字列によって表される。

一方のデータセットを、データの一部の文字を書き換えることでもう一方のデータセットに一致させるとき、書き換える必要のある最小の文字数を求めよ。

ただし各入力について、文字を消したり追加することなく2つのデータセットを一致させられることが保証されている。

制約

  •  1 \leq N \leq 100

解説

例によって問題文がとても読みづらい。というか導入が長い。 まぁその中から必要な情報をすばやく汲み取るのも一種のスキルなのかもしれないが。

本題に戻ろう。まず書き換えるべき文字はSMLの三種のみで、Xを書き換える必要は一切ない。さらに前についているXの数が同じものにのみ書き換えられるので、Xの数とSMLでふるい分けすればあとは各要素数を比較するだけ。

回答例

using namespace std;

template <typename T>
using V = vector<T>;

#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
// Usual REP runs from 0 to n-1 (R: n-1 to 0)

/* ---------- ここまでマクロ ----------- */

int main() {
    const string sml = "SML";
    
    int N;
    cin >> N;
    V<V<V<int>>> cnt(2, V<V<int>>(4, V<int>(3, 0)));
    // cnt[k][i][j]
    // = k番目のセット中で、Xがi個ついていて接尾語がsml[j]のものの数

    REP(k, 2) {
        REP(_, N) {
            string S;
            cin >> S;
            
            // ここからSをふるいにかける
            REP(i, 3) {
                if (sml[i] == S.back()) {
                    cnt[k][SIZE(S) - 1][i]++;
                    // 文字列の長さでXの個数
                    // 最初に定義したsmlで接尾語を判定
                }
            }
        }
    }

    int ans = 0;
    REP(i, 4) {
        REP(j, 3) {
            ans += abs(cnt[0][i][j] - cnt[1][i][j]);
            // はみ出ている分(?)を書き換える必要がある
            // この時点では2回分重複してカウントしていることに注意
        }
    }

    cout << ans / 2 << endl;
    // 重複してカウントした分2で割る
    return 0;
}

工場の製造ラインで、商品をサイズ別に分ける機械に似ている気がする。

問題自体は簡単なのだが、実装が怠いタイプの問題。 ま、今回のセットの中では実装は軽いほうなのだが。

B. Light It Up

問題リンク

概要

素数  Nの狭義単調増加列  a_i (  0 \lt a_1 \lt a_2 \lt \dots \lt a_N \lt M )がある。

ここにランプがあり、時刻0に点灯後、各  iについて時刻  a_iにオンオフが入れ替わって、時刻  Mで状態にかかわらず消灯する。

さて、あなたは上の条件を満たし続けるように数列 a_iに値を高々1つ挿入できる。このとき、ランプの点灯時間の最大値を求めよ。

図解するとこういうこと。

f:id:misteer:20180630111919p:plain

制約

  •  1 \leq N \leq 10^{5}
  •  2 \leq M \leq 10^{9}

解説

以降、便宜上 a_0 = 0, a_{N+1} = Mとする。

挿入しない場合

まず、何も挿入しない場合について考える。 時刻 a_i時点での総点灯時間を s_iとすると、これは累積和DPで求まる。具体的には iが奇数のときだけ a_i - a_{i-1}を足していけばいい。

これにより、値を何も挿入しない場合の総点灯時間は s_{N+1}で求まる。これが答えの下限である。

挿入する場合

次に、値を挿入していく場合を考える。

例えば a_i a_{i + 1}の間に新しい値を挿入するとする。このときの最長点灯時間を求めよう。

  • 区間 [0, a_i]では上の何も挿入しない場合と点灯時間は同じで、 s_iで求まる。

  • 区間 [a_{i+1},M]では全体のオンオフが切り替わることになる。区間の長さは M - a_{i+1}、元の点灯時間は s_{N+1} - s_{i+1}なので、反転した場合の点灯時間は(M - a_{i+1}) - (s_{N+1} - s_{i+1})となる。

  • 区間 [a_i, a_{i+1}]。もし a_iでオンになった場合は、極力長引かせた後 a_{i+1} - 1でオフ。 逆に a_iでオフになった場合は、即 a_i+1でオンにするのが最も効率的となる。このとき、点灯時間はどちらのケースも a_{i+1} - a_i - 1で与えられる。

以上より、この場合の最長点灯時間は 
s_i + (M - a_{i+1}) - (s_{N+1} - s_{i+1}) + (a_{i+1} - a_i - 1)
となる。これを全ての i \in [0, N]で網羅して最大値を更新すればよい。

ここで「 a_{i+1} - a_i = 1の場合は?」というのは至極真っ当な疑問で、このケースは値を挿入できないので省くべきである。1

回答例

using namespace std;

template <typename T>
using V = vector<T>;
using ll = long long;

#define FOR(i, a, b) for (ll i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define NREP(i, n) FOR(i, 1, n + 1)
// Usual REP runs from 0 to n-1 (R: n-1 to 0)
// Natural REP runs from 1 to n

/* ---------- ここまでマクロ ----------- */

int main() {
    ll N, M;
    cin >> N >> M;

    V<ll> a(N + 2);
    a[0] = 0;
    NREP(i, N) {
        cin >> a[i];
    }
    a[N + 1] = M;

    V<ll> sum(N + 2, 0);
    // 挿入しないときの点灯時間

    NREP(i, N + 1) {
        sum[i] = sum[i - 1];
        if (i % 2 == 1) {
            sum[i] += a[i] - a[i - 1];
        }
    }

    ll ans = sum[N + 1];

    REP(i, N + 1) {
        // 区間長が1なら挿入できないのでスルー
        if (a[i + 1] - a[i] == 1) continue;
        
        // a[i]とa[i - 1]の間に挿入したときの点灯時間
        ll t = 0;
        
        t += sum[i];
        t += (M - a[i + 1]) - (sum[N + 1] - sum[i + 1]);
        t += a[i + 1] - a[i] - 1;

        ans = max(ans, t);
    }

    cout << ans << endl;
    return 0;
}

ただの累積和DPなのだが、実装というより計算が重い。本番では上のように筋道立てて式を導出していなかったので頭が割れるかと思った。メモ媒体の使用、大事。

C. Covered Points Count

問題リンク

概要

 N個の区間 [l_i, r_i]が与えられる(両端を含み l_i = r_iになることもある)。 このとき、各 k = 1,2, \dots ,Nについて、丁度 k個の区間で覆われている頂点の数を出力せよ。

制約

  •  1 \leq N \leq 2 \cdot 10^{5}
  •  0 \leq l_i \leq r_i \leq 10^{18}

解説

問題がとてもシンプルで好き。でも実装は重い。

まず問題文からぱっと出たのが「imos法」による解法。内容が「imos法を使え」と言わんばかりのテーマだからね2

じゃあ例によって区間の始点と終点の要素をイジって...ってとこで l, rの制約がデカすぎることに気づく。空間も時間もまるで足りない。

一昔前の私ならここで諦めていたが、今は違う。区間がデカすぎるなら圧縮すればいいじゃない。というわけで「区間の端点を座標圧縮して十分記録できるサイズにして、それからimos法を適用する」というのが私の方針だった。正直座圧はそれほど慣れていなかったので不安があったが、通ったので良し。

ただ1つ注意することとして、imos法を使うときは区間を半開区間として扱う必要がある。閉区間 [l, r]全体に1を加算するとき、imos法では

imos[l]++;
imos[r + 1]--;

という形の処理を行うのだが、2行目でr+1としてるのが重要。なんとも説明しづらいが、要は閉区間 [l, r]の rをこのまま扱って座圧すると上手くいかないよって話。 r+1に変えておこう。

回答例

using namespace std;

template <typename T>
using V = vector<T>;
template <typename T, typename U>
using P = pair<T, U>;
template <typename T>
using ll = long long;

#define fst first
#define snd second
#define pb push_back

#define LL(n) static_cast<ll>(n)

#define ALL(v) (v).begin(), (v).end()
#define SIZE(v) (LL((v).size()))
#define SORT(v) sort(ALL(v))

#define FOR(i, a, b) for (ll i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define NREP(i, n) FOR(i, 1, n + 1)
// Usual REP runs from 0 to n-1
// Natural REP runs from 1 to n

/* ---------- ここまでマクロ ---------- */

// 与えられた区間の両端を全部まとめて圧縮する
V<ll> compress(const V<P<ll, ll>>& seg) {
    V<ll> val;
    
    // 1.値を全部突っ込む
    for (auto p : seg) {
        val.pb(p.fst);
        val.pb(p.snd);
    }

    // 2.sortする
    SORT(val);
    
    // 3.被りを消す
    // 以下の文はイディオムみたいなもの
    val.erase(unique(ALL(val)), val.end());
    
    // 4.被りのなくなったものを配列として返す
    return val;
}


int main() {
    ll N;
    cin >> N;
    
    V<P<ll, ll>> seg(N);
    REP(i, N) {
        cin >> seg[i].fst >> seg[i].snd;
        seg[i].snd++;
        // ここで閉区間を半開区間に変えている
    }

    // 区間の端点を圧縮したものを受け取る
    V<ll> com = compress(seg);
    ll M = SIZE(com);

    map<ll, ll> mp;
    // comの各要素がcom内でどこにあるかを記録
    
    REP(i, M) {
        mp[com[i]] = i;
    }

    V<ll> imos(M + 1);
    // imos[i] = [com[i], com[i+1])を覆う区間の数
    
    // 1. 差分をカウント
    for (auto p : seg) {
        imos[mp[p.fst]]++;
        imos[mp[p.snd]]--;
    }

    // 2. 累積和で集計
    NREP(i, M) {
        imos[i] = imos[i - 1] + imos[i];
    }

    V<ll> ans(N + 1, 0);
    
    // 3. 答えをカウント
    REP(i, M) {
        ans[imos[i]] += com[i + 1] - com[i];
    }

    NREP(k, N) {
        cout << ans[k] << " ";
    }
    cout << endl;
    return 0;
}

ちなみにこの解法、Editorialと九割方同じ方針だった。 Editorial中では文で事細かに説明されているが、あれだけ汎用的なアルゴリズムにグローバルな名前がついていないのが不思議。

他の解法として「区間の端点をソートして頭から順に見ていく」というのも考えられる。実装は出来てないので机上の空論だが、どうなんだろう。

D. Yet Another Problem On a Subsequence

問題リンク

概要

 a_1 > 0かつ長さが a_1+1であるような数列 a_igood arrayと呼ぶことにする。 例えば [3, 3, -4, 0]は a_1=3で長さ4なのでgood arrayである。

さらに、数列のうち1つ以上のgood arrayに分割できるようなものをgood sequence3と呼ぶことにする。

長さ Nの数列 a_iが与えられるので、その部分列(連続でなくていい)でgood sequenceであるものの個数を 998244353 (素数)で割った余りを求めよ。

ただし、要素が全て同じ部分列同士であっても、元の数列の異なるindexから取ってきた要素が1つでも存在する場合は別としてカウントする。

制約

  •  1 \leq N \leq 10^{3}
  • -10^{9} \leq a_i \leq 10^{9}

解説

第一成分と長さだけで定義された、少し変わった数列に関する問題。裏を返せば第一成分以外は全部無視できるので扱いやすいとも言える。

ではどうやって考えていくかというと、頭から要素を見ていって「この要素をgood sequencesに入れるか?」を試していくのが一番シンプルだろう。

そこで、「 i文字目以降の部分列から、いくつのgood sequencesを作れるか」を計算する関数を rec(i)としよう。ちなみに iは0-indexedとする。明らかに i \geq Nにて rec(i) = 0である。

使わない場合

まず i文字目を使わない場合。少し考えれば分かるが、この場合の総パターン数は rec(i + 1)で求まる。それはそう。

 a_i \leq 0の場合はこっちだけ考えればいい。

使う場合

本題はこっちで、この場合はgood arrayの定義から i+1文字目以降から a_i文字取ってくる必要がある。good sequencesを作るとき、部分列は連続してなくてもいいことに注意。

 a_iを先頭として長さ Lのgood arrayを作るとすると、総パターン数は以下のように求められる。

f:id:misteer:20180630112829j:plain

つまり 
{}_{L-1} C_{a_i-1} \times (rec(i + L + 1) + 1)
通りである。これを a_i \leq Lかつ i+L \lt N の範囲の Lで全て足せば、使う場合の総パターン数が求まる。

あと再帰回数がエゲツないため、ちゃんとメモして高速化しないとTLEになるので注意。

回答例

随分長いけど内40行はライブラリが原因なので、そこは読み飛ばしていただくと良いかと。

using namespace std;

template <typename T>
using V = vector<T>;
using ll = long long;

#define FOR(i, a, b) for (ll i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define NREP(i, n) FOR(i, 1, n + 1)
// Usual REP runs from 0 to n-1
// Natural REP runs from 1 to n

/* ---------- ここまでマクロ ----------- */

/* ---------- ここから二項係数ライブラリ ---------- */

const ll MOD = 998244353;
const ll MAX_V = 10000;

V<ll> fact(MAX_V + 1), invfact(MAX_V + 1);
// 階乗とその逆元

// 繰り返し二乗法でn^kを計算
ll calc_pow(ll n, ll k) {
    if (k == 0) return 1;
    if (k == 1) return n;

    if (k % 2 > 0) {
        return calc_pow(n, k - 1) * n % MOD;
    } else {
        return calc_pow(n * n % MOD, k / 2);
    }
}

// 事前呼び出しで階乗と逆元のテーブルを埋める
void precalc() {
    invfact[0] = fact[0] = 1;
    NREP(i, MAX_V) {
        fact[i] = fact[i - 1] * i % MOD;
    }

    invfact[MAX_V] = calc_pow(fact[MAX_V], MOD - 2);
    RREP(i, MAX_V) {
        invfact[i] = invfact[i + 1] * (i + 1) % MOD;
    }
    return;
}

// aCbを計算
ll comb(ll a, ll b) {
    if (a < b) return 0;
    if (a == 0) return 1;  // a = b = 0

    return fact[a] * invfact[a - b] % MOD * invfact[b] % MOD;
}

/* ---------- ここまで二項係数ライブラリ ---------- */

ll N;
V<ll> a(1010);
// 入力受け取り

V<ll> dp(1010, -1);
// メモ化再帰用 メモされていなければ-1

// i文字目以降での総パターン数を返す
ll rec(ll i) {

    // 終端判定
    if (i >= N) return 0;
    
    // 計算済みならメモを使う
    if (dp[i] >= 0) return dp[i];

    ll ans = 0;

    if (a[i] > 0 && a[i] < N) {
        // a[i]を使う場合
        NREP(l, N) {
            if (i + l + 1 > N) break;
            
            // l<a[i]では二項係数が0になるのでカウントされない
            ans += comb(l - 1, a[i] - 1) * (rec(i + l + 1) + 1) % MOD;
            ans %= MOD;
        }
    }

    // a[i]を使わない場合
    ans += rec(i + 1);
    ans %= MOD;

    // 計算結果をメモ
    dp[i] = ans;
    
    return dp[i];
}

int main() {
    precalc();
    // 階乗と逆元を全部計算する

    cin >> N;
    REP(i, N) {
        cin >> a[i];
    }

    ll ans = rec(0);

    cout << ans << endl;
    return 0;
}

mod問題ということで、お手製ライブラリのお披露目となった。ペーストするだけで勝手に計算してくれるので楽。しばしばprecalcを呼び忘れる。

わざわざ演算後にmodで剰余取るのがめんどくさいし何度かバグってるので、専用のクラスとか作りたいな〜とか思ったり思わなかったり。

感想

今回のセットはコンテスト中は「実装めっちゃ重いな〜」と思っていたが、振り返ってみると「もっとちゃんと紙に書けばそれほど混乱せずに済んだのでは?」という感じがしている。現実世界でのメモの大切さを思い知った。今後はもっとキレイにメモを書こう。

ちなみに今回解けなかった残りの3問だが、E問題は「強連結成分潰すんだろうな〜」と思いながら潰し方を知らなかったので断念。F問題は愚直なTLE解しか分からず。G問題はにゃーんって感じ。まだまだだね。

ちなみにレートは昭和61年まで上がった。早く現代になりたい。


  1. 本番ではそのケースも統一的に扱うコードを提出したのだが、なぜか通ってしまった。おそらく前後の区間に値を挿入するケースに吸収されたと考えられる。

  2. ここではimos法の説明はしない。いもす研HPに詳しく説明されているので、これを読めば私が想定している解法がなんとなく分かるだろう。

  3. good arrayとgood sequence、和訳するとどっちも「良い数列」になってしまうので諦めてそのままにした。コンテスト中も最初はこんがらがってしまって何がなんだかという状態だったり。

Codeforces Round #492 (Div.1) 振り返り

初のDiv.1コンテスト。渡る世間はプロばかり。

コンテストリンク

本記事のHackMD版はこちら

目次

A. Tesla (※自動車会社名)

問題リンク

概要?

スライドパズルの要領で駐車場に車を入れよう!

解説

概要が雑だが気になる人は本文を読んでほしい。ここで説明する分量ではない。

本番で思いついたのが以下のようなアルゴリズムで、Editorialもこれと全く同じ解法だった。

  1. 駐車場に接している車は入れてしまう。
  2. 車を全部反時計回りに移動させる(キャタピラの要領)。
  3. 1に戻り、全ての車が入ったら終わる。

2の時点で車が移動できない、つまり K = 2Nで全ての車が駐車場に隣接していない場合だけ-1と出力すればよい。 そうでない場合、各車は多くても1周=2Nしか移動しないので、制約から最悪でも10000回程度の移動で終わる。

と、言うのは簡単だが実装がアホみたいに重い。特に実装が難しいのが

  • ループが回しにくい
  • 2で適当に1周回してしまうと車が衝突してしまう可能性があり、空きマスから移動させなければならない

の2点。最初はループを4分割して管理性最悪の継ぎ接ぎコードを書いていたが、結局バグに対処しきれずうんざり。

こういったコードを書いているときは、すぐに書くのを中断してもっと効率的な書き方を考えるのが大切。実際、そのあと「ループを配列にしちゃえばいいじゃーん」ってことに気づいて全部書き直したら、コード量は格段に減ったし一発で通った。

回答例

using namespace std;

template <typename T>
using V = vector<T>;
template <typename T, typename U>
using P = pair<T, U>;

#define fst first
#define snd second
#define pb push_back
#define mp make_pair

#define SIZE(v) (LL((v).size()))

#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define NREP(i, n) FOR(i, 1, n + 1)
// Usual REP runs from 0 to n-1
// Natural REP runs from 1 to n

/* ---------- ここまでマクロ ---------- */

int main() {
    int N, K;
    cin >> N >> K;
    V<V<int>> place(5, V<int>(N + 1));
    // 1-indexedで記録
    NREP(i, 4) {
        NREP(j, N) {
            cin >> place[i][j];
        }
    }

    V<P<int, P<int, int>>> ans;
    // 手順を記録 (id, (c, r))
    
    V<P<int, int>> loop(N * 2 + 1);
    // ループの回る順番を記録する配列
    
    REP(i, N) {
        loop[i] = mp(2, i + 1);
        loop[i + N] = mp(3, N - i);
    }
    loop[N * 2] = loop[0];
    // [(2,1),(2,2), ... ,(2,N),
    //  (3,N),(3,N-1), ... ,(3,1),(2,1)]

    while (true) {
        bool finish = true;

        // 1. 格納できる車を格納
        NREP(j, N) {
            if (place[1][j] > 0 && place[1][j] == place[2][j]) {
                ans.pb(mp(place[2][j], mp(1, j)));
                place[2][j] = 0;
            } else if (place[2][j] > 0) {
                finish = false;
            }
        }

        NREP(j, N) {
            if (place[4][j] > 0 && place[4][j] == place[3][j]) {
                ans.pb(mp(place[3][j], mp(4, j)));
                place[3][j] = 0;
            } else if (place[3][j] > 0) {
                finish = false;
            }
        }
        // 上のコードは1,2行目と,3,4行目で2つに分けているが、
        // place[i][j] == place[i^1][j]的な方法もある

        if (finish) break;
        // 全部格納できたら終了、出力へ

        // 2. 車を反時計回りにローテーション
        // まずは空きマスを探す
        int begin = -1;
        REP(i, N * 2) {
            auto p = loop[i];
            if (place[p.fst][p.snd] == 0) {
                begin = i;
                break;
            }
        }

        // 空きマスがない->車が移動できないので不可能
        if (begin < 0) {
            cout << -1 << endl;
            return 0;
        }
        
        // 次いで手順を記録する
        // 空きマスを始点として、時計周りに1周見ていく
        FOR(i, begin, 2 * N) {
            auto p = loop[i + 1];
            if (place[p.fst][p.snd] > 0) {
                ans.pb(mp(place[p.fst][p.snd], loop[i]));
            }
        }

        REP(i, begin) {
            auto p = loop[i + 1];
            if (place[p.fst][p.snd] > 0) {
                ans.pb(mp(place[p.fst][p.snd], loop[i]));
            }
        }
        
        // それから実際に移動する
        // 移動自体は空きマスとかガン無視でいい
        // リアルタイム更新みたいな破壊的な方法は、やめようね!
        V<V<int>> to = place;
        REP(i, N * 2) {
            auto p = loop[i], sp = loop[i + 1];
            to[p.fst][p.snd] = place[sp.fst][sp.snd];
        }
        place = to;
    }

    // 最後に手順を出力
    cout << SIZE(ans) << endl;
    for (auto p : ans) {
        cout << p.fst << " " << p.snd.fst << " " << p.snd.snd << endl;
    }

    return 0;
}

メインパートがコメント抜きでも約80行、これは重い。

実際この問題は点数の割に重すぎるため、どう考えても飛ばすのが正解。この問題に50分くらい掛けてしまったために、10分で解けるB問題の点数が下がったのが悔やまれる1。問題の識別眼がまだまだ鍛えられてないなぁと実感した。実践経験不足だろうか。

B. Suit and Tie2 (集合写真)

問題リンク

概要

 1 \sim Nがそれぞれ2個ずつ入った長さ 2Nの配列がある。 隣り合う要素を何度かswapして同じ数字が隣り合うようにするとき、最小のswap回数を求めよ。

制約

  •  1 \leq N \leq 100

解説

先程「10分で解ける」と言ったが、実際AtCoderでも300点くらいの問題である。というのも、貪欲に頭の要素からペアを作るだけで事が済む。 下手に真ん中の方からペアを作ると、そのペアをまたぐように分かれているペアについて、操作数が2増えてしまうことからも分かるだろう。

回答例

using namespace std;

template <typename T>
using V = vector<T>;
using ll = long long;

#define pb push_back

#define SIZE(v) (LL((v).size()))

#define FOR(i, a, b) for (ll i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define NREP(i, n) FOR(i, 1, n + 1)
// Usual REP runs from 0 to n-1
// Natural REP runs from 1 to n

/* ---------- ここまでマクロ ---------- */

int main() {
    ll N;
    cin >> N;
    V<ll> A(2 * N);
    REP(i, N * 2) {
        cin >> A[i];
    }

    ll ans = 0;
    // 総swap回数
    
    while (!A.empty()) {
        NREP(i, N * 2 - 1) {
            if (A[i] == A[0]) {
                // swap回数は転倒数、ここでは移動距離と同じ
                ans += i - 1;
            }
        }

        V<ll> tmp;
        // A[0]以外の要素を順番通りに抽出
        // 下手にeraseとか使うとバグりそうなのでやめといた
        REP(i, N * 2) {
            if (A[i] != A[0]) {
                tmp.pb(A[i]);
            }
        }
        A = tmp;
        N--;
    }

    cout << ans << endl;
    return 0;
}

私が本番中に解けたのはこの2問まで。

C. Leaving the Bar (千鳥足)

問題リンク

概要

N個の二次元ベクトル \vec{v_i}が与えられる。

Allenは最初原点にいて、各ベクトルについて \vec{v_i} -\vec{v_i}だけ移動する。言い換えるなら、最終的に

 \displaystyle{
\vec{p} = \sum_i c_i \vec{v_i} \hspace{2ex} (c_i = \pm 1)
}

にいることになる。このとき、 | \vec{p} | \leq 1.5 \times 10^{6}を満たすように各 c_iを決めよ。 ちなみに、以下の制約下では条件を満たす c_iのパターンが必ず存在する。

制約

  •  1 \leq N \leq 10^{5}
  •  |\vec{v_i}| \leq 10^{6}

解法

最初「ノルムが大きい順にソートして、絶対値ができるだけ小さくなるように c_iを決める」という脳筋解法をぶん投げたら案の定通らなかった。その時点ではAがまだ解けてなかったので即諦めたが、気になってEditorialを見たら中々に面白い解法だった。

Editorial解法の肝は

3つのベクトルについて、そのノルムの最大値を rとする。 このとき、3つから適切に2つのベクトルを選ぶと、その和差でノルムが r以下になるものが必ず存在する。

という定理。正三角形を思い浮かべるとなんとなく分かるのだが、詳しくはEditorialを見ていただきたい。

これをN個のベクトルに順番に適用すると、制約から最終的にノルムが 10^{6}以下の2つのベクトルが残る。これらの和差のノルムの最小値は高々 \sqrt{2} \times 10^{6}なので、条件を満たすようにできる。

上の定理は大学入試でも出てきそうな感じはある。幾何問題難しいね。

回答例?

Coming soon...

D. Game (ゲーム)

問題リンク

概要

関数 f: (0, 1)^{N} \rightarrow \mathbb{R} (N桁のbit列に実数を対応させるような関数)がある。

AllenとBessieはランダムに決められた順番でN桁からなるbit列の各桁の値を決めていき、最終的に得られたbit列を xとして f(x)を最終的なスコアとする。

Allenはスコアを最大化するように、Bessieはスコアを最小化するようにするとき、スコアの期待値を求めよ。

ちなみにこの問題は fの一部が変わる r回のクエリ制になっている。

制約

  •  1 \leq N \leq 18
  •  0 \leq f(x) \leq 10^{9}
  •  0 \leq r \leq 2^{18}

解法

ゲーム系かと思ったら点数がバラバラだし、順番はランダムだしでなんかよく分からない問題。無論 2^{N}の全順番を試していては余裕でTLEだし、実装方法もよく分からない。

まぁ答えを言ってしまうと、期待値は

 \displaystyle{
\frac{1}{2^{N}} \times \sum_{x=0}^{2^{N}-1} f(x)
}

つまり  fの平均で出せてしまう。えぇ...。

Editorialでの説明はだいたい以下の通り:

 x番目のbitを tにしたときのスコアの期待値を v_{x, t}とおく。このとき、 \frac{v_{x,0}+v_{x,1}}{2} = \mathbb{E}(f)が成り立つ。

さて、最初がAllenの番だったとする。このときAllenは v_{x, t}が最大となるような x, tについて操作を行うことになる。

このとき、 v_{x,1 - t} = 2 \mathbb{E}(f) - v_{x,t}より v_{x, 1-t} vの最小値となる。よって最初がBessieの番である場合、Bessieは {x, 1-t}について操作を行うことになる。

したがってスコアの期待値は \frac{v_{x,t}+v_{x,1 - t}}{2} = \mathbb{E}(f)となる。

なんか分かるような分からないような...。確率論難しいね。

回答例

using namespace std;

template <typename T>
using V = vector<T>;
#define DOUBLE(n) static_cast<double>(n)

#define FOR(i, a, b) for (ll i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
// Usual REP runs from 0 to n-1

#define fcout cout << fixed << setprecision(10)

/* ---------- ここまでマクロ ---------- */

int main() {
    ll N, R;
    cin >> N >> R;
    ll sum = 0;
    V<ll> A(1 << N);
    REP(i, 1 << N) {
        cin >> A[i];
        sum += A[i];
    }

    fcout << DOUBLE(sum) / (1 << N) << endl;

    // ここからクエリ
    REP(i, R) {
        ll z, g;
        cin >> z >> g;
        sum -= A[z];
        A[z] = g;
        sum += g;
        fcout << DOUBLE(sum) / (1 << N) << endl;
    }

    return 0;
}

感想

なんか最近、問題の難易度を見極める力が試されている気がする。しかし私の実力で解けるのはA,Bだけ(運がよければDも)だったし、Aの実装が遅かった時点でまぁ実力もそんなもんなんだろうか。

結果はこんな感じ。ラッキーセブン。でもレートは2下がった。

初のDiv1コンテストだったが、早くもDiv2への郷愁の念に駆られている。しかし私は決してくじけない。


  1. 覆水盆に返らずとは言うが、もし最初に解いてればもう100点は稼げていた。それでもAが遅すぎて20位くらいしか変わんないけど。

  2. タイトルの「Suit and Tie」は直訳すると「スーツとネクタイ」だが、慣用句的に「格調高い」という意味があるらしい。

ARC099(ABC101) 振り返り

ARC094以来の悪夢再来。

例によってHackMD版のリンクを貼っておきますが、今回は数式が使えるようになったのでそれほど見にくくは無いはず(長いけど)。

目次

A - Eating Symbols Easy (記号を食べる高橋君: Easy)

問題リンク

概要

+-からなる文字列Sが与えられる。0に対して、Sの頭から順に

  • 文字が+なら1増やす
  • 文字が-なら1減らす

という操作を行ったとき、最終的に得られる値を求めよ。

制約

  •  |S| = 4

解説

実際にSを頭から見ていって操作を行えばいい。文字列の処理方法に注意ってところだろうか。

ちなみに操作自体は順不同なので、別にどこから見ていっても結果は変わらない(やる意味はないと思うが)。

回答例

using namespace std;

/* ---------- ここまでマクロ ----------*/

int main() {
    string S;
    cin >> S;

    int ans = 0;
    // この値に記号を作用させていく
    
    // Sを頭から順に見ていく
    // 記法については後ほど
    for (char c : S) {
        if (c == '+') {
            ans++;
        } else {
            ans--;
        }
    }

    cout << ans << endl;
    return 0;
}

日頃から使ってない人には14行目の

for (char c : S) {
    ...
}

という記法は見慣れないかもしれない。これは「範囲for文」と呼ばれていて、本質的には

for (int i = 0; i < S.size(); i++) {
    char c = S[i];
    ...
}

とやってることはほとんど同じ。PythonRuby経験者なら慣れていると思うが、C++だけって方の中には今まで知らなかったという方もいるかもしれない1。mapの要素を全列挙したいときとかに便利なので、身につけておくべし。

B - Digit Sums (桁和)

問題リンク

概要

自然数 Nが与えられる。 Nを10進法表記したときの各桁の和を S(N)としたとき、 N S(N)で割り切れるか判定せよ。

制約

  •  1 \leq N \leq 10^{9}

解説

実際に S(N)を計算して、割り切れるかどうか判定するのが早いし色々考えなくていいので楽。普通に実装すれば O(\log N)で行けるはず。

回答例

using namespace std;

/* ---------- ここまでマクロ ----------*/

// digit sum: Nの桁和を返す
int dsum(int N) {
    int ret = 0;
    
    while (N > 0) {
        ret += N % 10;
        N /= 10;
        // 1の位をretに足してNを10で割る、を繰り返すだけ
    }
    
    return ret;
}

int main() {
    int N;
    cin >> N;
    
    int d = dsum(N);
    if (N % d == 0) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}

桁和を求める問題は競プロでも非常によく出るので、スラスラ書けるようにしておきたいところ。以下のように再帰関数で書くともっと楽。

int dsum(int N) {
    return N == 0 ? 0 : N % 10 + dsum(N / 10);
}

再帰関数は上のようにとても短く書けるのが魅力的だが、

  • 慣れていないと読みづらい
  • 終端判定を間違えやすい
  • 裏で尋常じゃない呼び出し量になってしまうことがある(Fibonacci数列とか)

のが短所でもある。逆にこれらさえ気をつければとても有用な武器となりうる。

ちなみにこの問題は後のD問題の伏線的な問題でもあるのだが、それはまた後ほど。

C - Minimization (最小化)

問題リンク

概要

数列 (1, 2, \dots , N)を並び替えた長さNの数列Aがある。 この数列に対して以下の操作を何度か行うことで、全ての要素を同じにしたい。

連続するK個の要素を選ぶ。これら全てをその中の最小値で置き換える。

このとき、必要な操作の最小回数を求めよ。

制約

  •  2 \leq K \leq N \leq 10^{5}

解説

概要でも太字にしたが、数列Aが数列 (1, 2, \dots , N)を並び替えたものであるということを見逃すとどツボにハマる。というのも、この条件から全要素の最終的な値が1であることが決まるからだ。これは、1という要素はどのような操作を行っても消すことができないことから明らかである。

では実際にどういった操作をすればいいのか。結論を言ってしまうと、操作をした区間全体の集合は、

  • 区間は途中で途切れてはならない
  • 区間は数列全体を覆っていなくてはならない

という2つを満たしていなければならない。

これは、上の操作を「区間全体に1を広げる操作」と考えると直感的にもわかりやすいだろう。各条件が満たされていないと、

  • 区間が区切れているところから先に1を広げることができない
  • 覆われていない要素に1を広げることはできない

ことになり、条件を達成することができない。

逆に、上の2条件さえ満たされていれば適用順序を工夫することで必ず全要素を1にできる。具体的には、1が含まれている区間から順番に操作していけばいい。

抽象的すぎて分からないという方は、以下の図が参考になれば幸いである。

f:id:misteer:20180627095750j:plain

では実際に答えを求めよう。区間の数=答えだから、区間同士の重なりは1にするのが最も効率的である。このとき、m個の区間が覆える範囲は [1, (K - 1)m + 1]となる。これが区間 [1, N]を覆っていればいいわけだから、答えは  (K - 1)m + 1 \geq N \Leftrightarrow m \geq \dfrac{N - 1}{K - 1} を満たす最小のmとなる。これは、右辺の分数を切り上げることで計算できる。

回答例

using namespace std;

/* ---------- ここまでマクロ ----------*/

int main() {
    ll N, K;
    cin >> N >> K;

    ll ans = (N - 2) / (K - 1) + 1;
    // a/b の切り上げは (a-1)/b+1 で求まる
    cout << ans << endl;
    return 0;
}

切り上げ処理に関してはコード中に書いた通り2。覚えておくと楽なのだろうが、私はいつも導出している。

そして今まで見てきた通り、実は答えはNとKのみに依存していて具体的な数列の要素は一切不要である。こういう場合、上のように標準入力を受け取らずにコードを終了しても問題はない。

D - Snuke Numbers (すぬけ数)

問題リンク

概要

正整数nに対して、nを10進法表記したときの各桁の和を S(n)とし、関数gを g(n) = \dfrac{n}{S(n)}と定義する。

そして任意の正整数 m > nに対して g(n) \leq g(m)が成立するようなnを「すぬけ数」と呼ぶことにする。

このとき、すぬけ数を小さい方から順にK個出力せよ。

制約

  •  K \geq 1
  • K番目のすぬけ数は 10^{15}以下である。

解説

ちょっと制約が変わっているが、これはすぬけ数が具体的にどれくらいの分布になっているかを悟られないようにするためのものだろう。

この問題の方針だが、大きく分けて2つある。1つはちゃんと計算してすぬけ数を順番に求める、言わば「正統派」。もう1つはある程度すぬけ数を求めるプログラムを作ってそこから法則を強引に見出す、言わば「エスパー派」である。

ここでは前者の方針をEditorialにしたがって解説するが、すぬけ数は列挙してみると結構面白い規則性があるらしいので調べてみるといいだろう。

方針

この問題でまず躓くのが、最初にどう一歩を踏み出すかというところである。

結論を言ってしまうと、今回の場合は以下のように漸化的にすぬけ数を求めるのがベターな方針らしい。

  •  snuke(n) =「n以上で最小のすぬけ数」という関数 snukeを作る、
  • 1はすぬけ数なのでまず n = 1とする。
  •  n \leftarrow snuke(n + 1)として、nを更新する。

言われてみればそりゃそうだって感じだが、言われなければ踏み出せない。こういった方針立ても経験からくるものなのだろう。

というわけで次の課題は、上でサラッと出てきた関数 snuke(n)を作るということになる。

問題の有限化

すぬけ数の定義には「任意の正整数」が使われているが、これをプログラミングで扱うことはもちろんできない。 そこで、 snuke(n)上限というのを考えてみる。

mがある程度大きいとき、100m付近におけるgの最小値はm付近に比べて十分大きいことはなんとなく分かるだろうか。mの桁数をdとすると、100倍したところで桁和はせいぜい20程度しか増えないので、分母のように100倍になるということはまずない3

というわけで、具体的に m \in [n, 100n]の範囲で g(m)が最小となるmを求めればすぬけ数が求まることになる。随分大雑把な議論だが、実際これで正しく求まる。

この「問題の有限化」がこの問題を解く上での1つの鍵である。これによって、「任意の m' > m \geq nに対して g(m) \leq g(m')」というプログラムでは到底扱えない性質が、まだ範囲こそ大きいが「 m \in [n, 100n]で g(m)が最小」というプログラムでも力技で扱える性質に帰着されたことになる。

ふるいにかける

上の議論によって「時間を気にしなければ一応は解ける」という状態にはなったが、まだ g(m)を求める対象が多すぎてとてもじゃないが現実的ではない。

そこで、すぬけ数となりうる値をある程度絞り込む必要がある。言うなれば調査対象を「ふるいにかける」というわけだ。

例えば、 n = 1000のとき snuke(1000) = 1234となりうるだろうか?答えはNOである。 これはなぜかというと、例えば「 1199」という値は 1234 > 1199かつ S(1199) > S(1234)を満たすため明らかに g(1234) > g(1199)を満たすからだ4

このように、大半の値は「小さい方の桁は全部9」という値が言わば上位互換として存在する。逆に、この性質を満たす値には自明な上位互換というのは存在しないため調べる必要がある。

具体例として、 n = 1234のときの調査対象を列挙すると以下のようになる。

4桁 3桁 2桁 1桁  0桁
1234 1235 1249 1399 2999
- 1236 1259 1499 3999
- ... ... ... ...
- 1239 1299 1999 9999
- - - - 10999
- - - - 11999
- - - - ...
- - - - 122999

1行目はnとの一致桁数である。0桁が分かりにくいかもしれないが、この辺りの値が返り値になることはほぼないのでそこまで細かい値を気にする必要はない。「一致する桁の下に1つ1~9まで網羅する桁があって、それ以降は全部9」というのが重要である。

そして上のリストに入る値は n \leq 10^{15}で300個にも満たないため、十分 g(m)を調べることが可能である。以上でようやく準備が整った。

回答例

using namespace std;

template <typename T, typename U>
using P = pair<T, U>;
template <typename T>
using GPQ = priority_queue<T, vector<T>, greater<T>>;

using ll = long long;

#define DOUBLE(n) static_cast<double>(n)

#define FOR(i, a, b) for (ll i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define NREP(i, n) FOR(i, 1, n + 1)
// Usual REP runs from 0 to n-1 (R: n-1 to 0)
// Natural REP runs from 1 to n (R: n to 1)

/* ---------- ここまでマクロ ----------*/

// bのn乗を再帰的に求める
ll mypow(ll b, ll n) {
    return n == 0 ? 1 : b * mypow(b, n - 1);
}

// 桁和を求める(B問題を参照)
ll dsum(ll n) {
    ll ret = 0;
    while (n > 0) {
        ret += n % 10;
        n /= 10;
    }
    return ret;
}

// n以上で最小のすぬけ数を求める
ll snuke(ll n) {
    GPQ<P<double, ll>> val;
    // 逆順priority_queue, 一番上が最小の要素
    // (g(m), m)

    ll dig = 0;
    // 9が連続する桁数

    while (mypow(10, dig) <= n) {
        NREP(i, 9) {
            ll v = n - n % mypow(10, dig + 1) + i * mypow(10, dig) - 1;
            // 下dig桁が9
            // 1つ上は1~9
            // それより上はnと一致

            if (v >= n) {
                val.push(make_pair(DOUBLE(v) / dsum(v), v));
            }
        }
        dig++;
    }
    
    dig--;
    
    // 1桁もnと一致しないものを列挙
    NREP(i, 100) {
        ll v = i * mypow(10, dig) - 1;
        if (v >= n) {
            val.push(make_pair(DOUBLE(v) / dsum(v), v))
        }
    }

    auto ret = val.top();
    // g(m)とmが最小となる(g(m), m)の組

    return ret.second;
}


int main() {
    ll K;
    cin >> K;
    ll pre = 1;
    REP(_, K) {
        cout << pre << endl;
        pre = snuke(pre + 1);
    }
    return 0;
}

上のコードではsnukeの実装において、nと1桁も一致しない値の扱いが雑になっている。実際に計算すれば分かるのだが、このエリアの値が返り値になるのは n = 99 \dots 9の場合くらいなもので、わりかし雑に扱っても答えは出せる。

あと調査対象の列挙方法も少しトリッキーではある。

ll v = n - n % mypow(10, dig + 1) + i * mypow(10, dig) - 1;

これは前半のn - n % mypow(10, dig + 1)でnの上位桁だけを取り出して、後半のi * mypow(10, dig) - 1で9が連なる値を加えている。正直自分でも気持ち悪いが、他にいい方法が浮かばなかった。

点数について

ちなみにこのD問題、500点である。「700点の間違いでは?」って感じだが、本来500点というのはそういうもんなんだろうか。「Two Sequences」も500点だし。う〜ん、よく分からない。

しかしABCでRatedが21人通しているのがすごい。君たちもうARC行っていいよ。

感想

やはりDに尽きる。どうすりゃええねんこんなん。

ちなみに終わったあとでE問題も見たが、多分時間内に解くのは無理だっただろう。完全グラフの頂点同士は補グラフでは非接続(直接繋ぐ辺が存在しない)ってのが肝らしい。どっから補グラフ出てきた5

まぁ全ては精進不足が元凶なので、経験を積むより他にない。もっと真面目な人間に育ちたかったと怠惰に暮らしながら常々思う。


  1. 私はC++始めて半年くらいで初めて知りました。ググりにくいので意外と知る機会が少ない。

  2. 上の方法以外に \dfrac{a + b - 1}{b}という計算方法もある。式の値はどっちも同じだからどっちでもいいかと思っていたが、実はこっちは a = 0のケースにも安全に対応できるというメリットがある。

  3. 厳密には100倍でも大きく取り過ぎで、実際は10倍くらいで十分である。ただ個人的に10倍では不安があったので、ここでは以降も100倍の範囲を取り続けることにする。

  4. ここで違和感を覚える方は、問題の有限化によって「 snuke(n)= m \in [n, 100n]で g(m)が最小となるようなm』」と定義が変わっていることに注意していただくといいだろう。

  5. とか思ってたら最近のこどふぉで似た傾向の問題に遭遇してびっくり。

Codeforces Round #489 (Div2) 振り返り

一昨日と同様、深夜25:35から2時間に渡って行われたDiv2コンテスト。 前回の反省を活かして眠気ほぼなしの状態で挑みましたが、何か大切なものを犠牲にしているような気がしています。

今回まともに手を付けられたのはC問題まで。というわけで、さっそくA~Cの3問を振り返っていきましょう。

(例によって数式が丸々使えないので、HackMD版のリンクを貼っておきます。なんとかならんかね。)

目次

A. Nastya and an Array (ナーシャと数列)

問題リンク

概要

任意の整数を選び、数列の0でない要素全てにその整数を加える。

与えられた数列に対して、上の操作を繰り返して数列の全要素を0にする。 この最小手数を求めよ。

解説

一例としてはこんな感じ。この場合はあと4回で全部0にできるので、答えは6回となる。

f:id:misteer:20180619152554p:plain:w500

上を見ての通り、一度の操作では数列中の同じ値の要素を全部0に出来る。

操作する様子を色々考えれば、答えが数列の異なる要素の数であることが分かるだろう。 これはカウント配列やsetを使えば容易に実装できる。

ただし0を要素としてカウントしないように注意。サンプルに含まれていたのが良心的。

回答例

int main() {
    int N;
    cin >> N;

    set<int> used;
    // 出てきた要素を突っ込む
    // 重複は取り除かれるので要素数=答え
    
    REP(_, N) {
        int a;
        cin >> a;
        if (a != 0) {
            used.insert(a);
        }
    }

    cout << SIZE(used) << endl;
    return 0;
}

上の9行目では、for文の内部でループ変数を使わないことをREP(_, N)とすることで明示的にし、さらに変数名を節約している。 以前AtCoderで見かけて以来、愛用している記法だったりする。

B. Nastya Studies Informatics (ナーシャ、情報科学を学ぶ)

問題リンク

概要

整数l, r, x, yが与えられるので、

  • l ≦ a, b ≦ r
  • GCD(a, b) = x, LCM(a, b) = y

を満たす(a, b)の数を求めよ。

ただし、a ≠ bならば(a, b)と(b, a)は別としてカウントする。

(1 ≦ l ≦ r ≦ 109, 1 ≦ x ≦ y ≦ 109)

補足
GCD 最大公約数 (Greatest Common Divisor)
LCM 最小公倍数 (Least Commom Multiple)

解説

(数学Aの整数の知識を存分に使います。お覚悟を。)

まず、上の条件下でa = a'x, b = b'xとおくとa',b'は互いに素となる。

GCDとLCMの性質から、ab = xy。

ここでy' = y / xとおけばy' = a' b'と表せるので、このa'を全探索すればいい。

ただし、愚直に1 ≦ a' ≦ y'を全探索すると上の制約から余裕でTLEとなる。 じゃあどうすればいいかというと、a' ≦ b'と仮定して1 ≦ a' ≦ √y'の範囲に絞ればいい。素数判定で定番のやつである。

さらに気をつけるべきこととして、a' = b'の場合が挙げられる。この場合はa = bなので2つではなく1つとしてカウントしなくてはならない。

さらにさらに危険なのが、そもそもyがxの倍数でないケース(y % x > 0)。この場合は条件を満たす(a, b)がそもそも存在しないので答えは0となる。 実装方法によってはこれで落ちる可能性もあるので、最初に弾いておくのが吉。

回答例

ll gcd(ll a, ll b) {
    // Euclidの互除法で、aとbの最大公約数を求める
    
    if (a > b) return gcd(b, a);
    // 常にa<=bが保たれるようにする

    return a == 0 ? b : gcd(b % a, a);
}

int main() {
    ll l, r, x, y;
    cin >> l >> r >> x >> y;

    if (y % x > 0) {
        cout << 0 << endl;
        return 0;
    }

    ll y' = y / x;

    ll ans = 0;
    for (ll a' = 1; a' * a' <= y'; i++) {

        if (y' % a' > 0) continue;
        // 条件: a'はy'の約数
        
        ll a = x * a', b = x * y' / a';
        
        if (gcd(a, b) > x) continue;
        // 条件: a'とb'は互いに素
        // ここでは既にxをかけてしまっているので上の通り
        // (gcd > 1で1WA)

        if (l <= a && a <= r && l <= b && b <= r) {
            // 条件: l <= a, b <= r
            if (a != b) {
                ans += 2;
            } else {
                // a=bのケースに注意
                ans++;
            }
        }
    }

    cout << ans << endl;
    return 0;
}

見た目の通り完全に整数の問題。Xor Sumとどことなく似た空気を感じるが、無論こっちの方が全然簡単。

AtCoderなら内容的には300点レベル、さらに実装で+50点くらいか。

しかし絶妙にバグが発生しやすい構造をした問題である。 事実、コンテスト終了時点でB,Cの正解者はそれぞれ1,324人、1,341人となり、なんとCの方が正答者数が多いという異例の事態に。

Bとしては難問の部類に入るだろう。TLでも哀しみの声が観測された。

C. Nastya and a Wardrobe(ナーシャとタンス)

問題リンク

概要

服を入れると1ヶ月後に服が2倍になるという不思議なタンスがある。 しかしそのタンスは服を2倍にした後、50%の確率で中の服を1着だけ食べてしまう。 ただし1年の最後の月だけは、服が食べられることはない。1

例えばタンスに3着の服が入っていたとする。 この1ヶ月後にはタンスの中の服は2倍の6着になっているのだが、50%の確率でそのうちの1着が食べられてしまう。 つまり1ヶ月後の服の数は50%の確率で5着、50%で6着ということになる。

ナーシャは新年にこのタンスを貰い、x着の服をその中に入れた。ナーシャの国では1年がk + 1ヶ月であるという。

このとき、年末時点でタンスの中にある服の数の期待値を109 + 7で割った余りを求めよ。

(0 ≦ x, k ≦ 1018)

解説

先に言ってしまうが、この問題も完全に数学である。

計算過程リンク

解説にも数式を大量に使うわけで、いかんせんここに書くのは不可能なレベルとなってしまった。 というわけで、計算過程を書いたHackMD版のリンクをここに貼っておきます。考察ノートとかも載せてあります(要るか?)

f:id:misteer:20180619145444p:plain:w300

結論だけ先に言ってしまうと、上の計算式を109 + 7で割ったものを出力すればACとなる。

値の累乗は「ダブリング」というテクニックを使うことで対数オーダーで計算することができるので、バカみたいにデカいkの制約にも余裕で対応できる。詳しくは回答例にて。

コーナーケース

ただし、これをそのまま実装すると落ちてしまう(pretestが通るかは分からない)。 色々試せば分かるのだが、実はx = 0がコーナーケースなのだ。

x = 0のときは明らかに答えは0だが、上の式に代入してもそうならない。 これは式を立てる時点で、「そもそも食べられる服がない」という状況を考慮していないために起こる。 存在しない服を食べ続けてしまうことになるため、期待値が負に発散してしまうわけだ。

というわけで、ちゃんと最初に弾いておこう。

回答例

const ll MOD = 1e9 + 7;

ll calc_pow(ll n, ll k) {
    // ダブリングでn^kを求める
    
    if (k == 0) return 1;
    if (k == 1) return n;
    // 終端条件

    if (k % 2 > 0) {
        // kが奇数 -> n^k = n*n^(k-1)
        // 下の偶数の場合に帰着させる
        return calc_pow(n, k - 1) * n % MOD;
        
    } else {
        // kが偶数 -> n^k = (n^2)^(k/2)
        // これで指数を半分にすることで、計算量がlogkとなる
        return calc_pow(n * n % MOD, k / 2);
    }
}

int main() {
    ll x, k;
    cin >> x >> k;

    if (x == 0) {
        // さっき述べたコーナーケース
        cout << 0 << endl;
        return 0;
    }

    ll X = (x * 2 - 1 + MOD) % MOD;
    // X = 2x - 1
    // 少しまどろっこしいが、x<0の状態を防いでいる

    ll ans = (X * calc_pow(2, k) + 1 + MOD) % MOD;
    // ans = x_{k+1} = (2x - 1) 2^k + 1

    cout << ans << endl;
    return 0;
}

実装は軽い方だが、現実世界での前計算が慣れてないと大変。

ダブリングは毎回実装するのは少し面倒な上、modの逆元2を求めるのにも使うので私はライブラリ化している。

感想

記事を読んでいただければ分かる通り、数学色の強いコンテストだった。 D問題も連続部分列の積と和とかいう話だったので、全体としてもそういう傾向だったのだろう。

しかし私も伊達に東大に受かってないので、この手の問題は得意な方。前回の雪辱を果たし、無事3完を達成できた。でもDは残念ながら歯が立たず。

次のコンテストは実質4日後の6/24深夜。次こそはキッチリ決めて紫に上がりたいところ。


  1. なんで最後の月だけ例外扱いかというと、単に答えが小数になってしまうためだと思われる。

  2. na ≡ 1 (mod M)が成立するとき、aをnの逆元と呼び、a = n-1と書いたりする。「nで割る」という演算はmod系ではそのまま出来ないのだが、これを「n-1を掛ける」という演算で代用することができる。(一般にはもっと条件は緩いが)Mが素数の場合、Fermatの小定理から「n-1 ≡ nM - 2」で逆元が求められ、この累乗計算にダブリングを使う。

Codeforces Round #488 (Div2) 振り返り

ABC100が終わって3時間後に行われたCodeforces。 いい子はとっくに寝てる時間ですが、大学生の特権と言わんばかりの夜更かしで参戦しました。

教訓としては、「眠気がある状態でコンテストは参加するもんじゃない1。 個人的に初めて大きくレートを落としたコンテストになってしまいましたが、Dまでの解説はします。

(例によって幾分見やすいHackMD版のリンクも貼って置きます。今回は数式も少ないので大差ないかも。)

目次

A. Fingerprints (指紋)

問題リンク

概要

あなたの目の前にはテンキー式のロックが掛かったドアがあり、手元にはその暗証番号を部分列(連続でなくてよい)として含む数列が書かれた紙がある。

さらにテンキーの一部には指紋がついている。指紋がついた数字は必ず暗証番号に使われており、暗証番号はそのようなものの中で最長のものであることが分かっている。

このとき、暗証番号を正しい順番に出力せよ。

解説

紙の数列を順番に見ていって、暗証番号とマッチしたら出力するだけ。 制約が非常に小さいので毎回全探索で十分間に合う。

回答例

int main() {
    int N, M;
    cin >> N >> M;
    
    V<int> pap(N), fin(M);
    // paperとfinger

    REP(i, N) {
        cin >> pap[i];
    }
    REP(j, M) {
        cin >> fin[j];
    }

    REP(i, N) {
        REP(j, M) {
            if (pap[i] == fin[j]) {
                cout << pap[i] << " ";
                break;
            }
        }
    }
    cout << endl;
    return 0;
}

B. Knights of a Polygonal Table (多角形卓の騎士)

問題リンク

概要

騎士たちの強さがpi、所持金がciで与えられる。

騎士たちは他の騎士を殺すことで相手の所持金を手にすることができるが、自分より真に弱い(pが真に小さい)騎士しか殺せない。

さらに良心の呵責から、各騎士は高々k人しか他の騎士を殺すことはできない。

このとき、各騎士について他の騎士を殺した後に所持しうる最大金額を出力せよ。

解説

ずいぶんと物騒な問題文だが、お察しの通り「円卓の騎士」がモチーフになっている。私は円卓の騎士の元ネタを知らないのでなんとも言えないが。

それはさておき、やるべきことを簡潔にまとめると以下の通り。

  1. 騎士のデータを強さについて昇順になるようソートする。
  2. 弱い騎士から順に以下の操作を行う。
    1. 自分の1つ前の騎士の所持金を配列(coinとする)に挿れて降順ソート。
    2. coinの長さがkになるまでpop_back()する。
    3. coinの総和を答えとして記録。

今回はkの制約が小さい(k ≦ 10)ので、毎回ソートしても十分間に合う。

ただし上はあくまでも「強さが互いに固有(distinct)である」場合の方法であり、実際は「同じ強さの騎士が来たら一旦配列(stockとする)に記録して、真に強い騎士がきたらstockを全部coinに突っ込む」みたいな処理が必要になる。

回答例

int main() {
    int N, K;
    cin >> N >> K;
    
    V<P<P<int, int>, int>> data(N);
    // ((p, c), id)
    // idは入力時の順番を記録する

    REP(i, N) {
        data[i].snd = i;
        cin >> data[i].fst.fst;
    }
    REP(i, N) {
        cin >> data[i].fst.snd;
    }

    SORT(data);
    // pについて昇順ソート

    V<ll> coin, stock;
    V<ll> ans(N, 0);

    ans[data[0].snd] = data[0].fst.snd;
    // 一番弱い騎士は誰も殺せないので所持金=答え

    NREP(i, N - 1) {
        stock.push_back(data[i - 1].fst.snd);
        // 1つ前の騎士のcを一旦stockに入れる
        
        // 強さが同じ場合はstockに残ったまま
        if (data[i].fst.fst > data[i - 1].fst.fst) {
        
            // stockの中身を全部coinに移す
            while (!stock.empty()) {
                coin.push_back(stock.back());
                stock.pop_back();
            }
        }

        // coinを降順ソートし、長さがK以下になるまで末尾を消す
        GSORT(coin);
        while (SIZE(coin) > K) {
            coin.pop_back();
        }

        ll v = data[i].fst.snd;
        for (ll c : coin) {
            v += c;
        }

        ans[data[i].snd] = v;
    }

    REP(i, N) {
        cout << ans[i] << " ";
    }
    cout << endl;

    return 0;
}

下手な実装をすると絶対バグる、Codeforces恒例の実装系問題。

私は苦手なタイプの問題だが、今回は幸いにもバグらなかった。 大分慣れてきた感じがある。

C. Two Squares (2つの正方形)

問題リンク

概要

座標軸に平行な辺を持つ正方形Aと、座標軸と45度に交わる辺を持つ正方形Bが与えられる。

正方形の辺上も内部として扱うとき、AとBが共有部分を持つか判定せよ。

解説(未完)

問題自体は至って簡潔なのだが、考えてみると結構難しい。

まず、1つでも頂点が一方の正方形内部にある場合は明らかにYES。

Bの頂点がAの内部にあるかはgridの探索でもよくやる境界判定で簡単に出来るのだが、問題はもう一方。 これは幾何問題ではたまに出てくるテクニック「座標回転」(造語)を行えば上手くいく。

座標回転というのは「(X, Y) = (x - y, x + y)という座標変換を行うことで、(X, Y)は元のグラフを45度時計回りに回転させて原点中心に拡大したものになる」というテクニック。回転行列を使えば簡単に証明できる。

これを適用することで、Bが座標軸に直交するようになって先の境界判定をそのまま使えるようになる。

解説(完全)

しかし、未完とあったように先の方針では漏れがある。それが以下のようなケース2

f:id:misteer:20180617142717p:plain

これを網羅する方針で間違えたために、私はサーバージャッジで落とされた。悲しい。

ではどうすればこのようなケースを網羅できるかというと、答えは意外と簡単で「一方の中心が他方に含まれているか」を調べるだけ。 解説見て「たったそんだけでいいのか......」と嘆くなどした。

回答例

int main() {
    V<int> x1(4), y1(4), x2(4), y2(4);

    ll xmin = 1000, xmax = -1000, ymin = 1000, ymax = -1000;
    // 境界判定用のやつ(工夫すれば多分要らない)

    REP(i, 4) {
        cin >> x1[i] >> y1[i];
        xmin = min(xmin, x1[i]);
        xmax = max(xmax, x1[i]);
        ymin = min(ymin, y1[i]);
        ymax = max(ymax, y1[i]);
    }

    REP(j, 4) {
        cin >> x2[j] >> y2[j];

        // 頂点がAに入っているか判定
        if (xmin <= x2[j] && x2[j] <= xmax && ymin <= y2[j] && y2[j] <= ymax) {
            cout << "YES" << endl;
            return 0;
        }
    }
    
    // Bの中心がAに入っているか判定
    if (xmin * 2 <= x2[0] + x2[2] && x2[0] + x2[2] <= xmax * 2 && ymin * 2 <= y2[0] + y2[2] && y2[0] + y2[2] <= ymax * 2) {
            cout << "YES" << endl;
            return 0;    
    }
    
    xmin = 1000, xmax = -1000, ymin = 1000, ymax = -1000;
    // 境界判定の変数を再び初期化
    
    REP(j, 4) {
        // ここで座標回転をする
        ll x = x2[j], y = y2[j];
        x2[j] = x - y;
        y2[j] = x + y;
        xmin = min(xmin, x2[j]);
        xmax = max(xmax, x2[j]);
        ymin = min(ymin, y2[j]);
        ymax = max(ymax, y2[j]);
    }

    REP(i, 4) {
        ll x = x1[i], y = y1[i];
        x1[i] = x - y;
        y1[i] = x + y;

        // 頂点がBに入っているか判定
        if (xmin <= x1[i] && x1[i] <= xmax && ymin <= y1[i] && y1[i] <= ymax) {
            cout << "YES" << endl;
            return 0;
        }
    }
    
    // Aの中心がBに入っているか判定
    if (xmin * 2 <= x1[0] + x1[2] && x1[0] + x1[2] <= xmax * 2 && ymin * 2 <= y1[0] + y1[2] && y1[0] + y1[2] <= ymax * 2) {
            cout << "YES" << endl;
            return 0;    
    }

    cout << "NO" << endl;
    return 0;
}

残念ながら不正解だったが、経験は得られた。 今度AtCoderにでも類題出ないかな。

あと上のコードが汚いのはなんとかならないのか。

D. Open Communication (公開通信)

問題リンク

概要

2人が1~9の数からなるペアを1つずつ持っており、2つのペアには1つだけ共通の数が含まれている。

2人は自分のペアは知っているが相手のペアは知らない。この状況下で以下のような通信を交互に1回ずつ行い、共通の数を当てることが目標となる。

  • 一方がもう一方へ1~9の数からなるペアをいくつか伝える。
  • ペアは異なる数字から成り、かつ同じものを含んではならない。
  • 伝えるペアの中には自分が持つペアが必ず含まれていなければならない。

三者であるあなたもこの通信だけを見て、2人と同様に共通の数を当てることが目標となる。

やり取りされた情報が与えられるので、

  • 共通の数が分かればその数
  • 共通の数は分からないが、どんなケースでも2人とも共通の数が分かっているなら0
  • 共通の数は分からず、1人でも共通の数が分かっていないケースがあれば-1

を出力せよ。

My方針

一目すると「何言ってんだこいつ」って感じの問題。 要は論理パズルみたいなもので、眠気で支配された頭には堪えた。

ざっくりと私の方針を説明すると、

  1. どちらか一方の視点に立ち、「もし自分がこのペアを持っているなら」と仮定する。
  2. 相手についても「もし相手がこのペアを持っているなら」と全パターン仮定し、以下のように可能性を模索する。

    • もしもペアの要素が2つとも違うor同じなら、相手がそのペアを持つ可能性はないのでスルー
    • もしペアの要素が1つだけ一致するなら、その一致する数が「共通の数」となる可能性があるのでset(posとする)に突っ込む
  3. 相手について全パターン模索し終わった時点で、posの要素数

    • 0なら、自分がこのペアを持つことはないのでスルー。
    • 1なら、その要素が共通の数としてあり得るのでset(ansとする)に突っ込む。
    • 2なら、自分がそのペアを持っているケースについて自分は共通の数が分からないので、-1を出力して終わり
  4. 以上を自分の伝えた全ペアに対して行った後、ansの要素数

    • 0になることは条件から絶対にない。
    • 1ならそれが唯一「共通の数」になりうる数なので、それを出力。
    • 2以上なら、どのケースでも本人は「共通の数」を1つに絞れているはずなのに自分は分からないということで0を出力。

これをそのまま実装してなんとかpretestまでは通ったのだが、案の定サーバーテストで落とされる始末。

ちなみに一方からの視点だけから見ていたのがまずかった模様。 ちゃんと両者の視点に立って考えてれば合ってたと思うと悲しいね。

提出コード

int main() {
    int N, M;
    cin >> N >> M;

    V<P<int, int>> A(N), B(M);
    REP(i, N) {
        ll a, b;
        cin >> a >> b;
        A[i] = make_pair(a, b);
    }
    REP(i, M) {
        ll a, b;
        cin >> a >> b;
        B[i] = make_pair(a, b);
    }

    set<int> ans;
    // Aの視点に立ったとき、「共通の数」として考えうる数全てを記録
    
    REP(i, N) {
        set<int> pos;
        // AがA[i]を持っていると仮定した場合、「共通の数」として考えうる数を記録
        REP(j, M) {
            REP(_, 2) {
                swap(B[j].fst, B[j].snd);
                
                if ((A[i].fst == B[j].fst) == (A[i].snd == B[j].snd)) {
                    // ペアの共通要素数が0か2なので、
                    // 相手がB[j]をもつことはない
                    continue;
                }

                if (A[i].fst == B[j].fst) {
                    pos.insert(A[i].fst);
                } else {
                    pos.insert(A[i].snd);
                }
            }
        }

        // 1つも「共通の数」として考えうる数がない
        // = AがA[i]を持つ可能性はない
        if (pos.empty()) continue;
        
        if (SIZE(pos) == 1) {
            auto itr = pos.begin();
            ans.insert(*itr);
            
        } else {
            // 2つとも「共通の数」として考えうる
            // = AがA[i]を持つ場合、Aは「共通の数」を判別できない
            cout << -1 << endl;
            return 0;
        }
    }

    if (SIZE(ans) == 1) {
        // Aがどのペアを持っていようと、
        // 全ケースについて「共通の数」は同じ
        auto itr = ans.begin();
        cout << *itr << endl;

    } else {
        // Aはどのケースでも「共通の数」を1つに絞れるが、
        // 私からはどのケースが正しいのか分からない
        cout << 0 << endl;
    }
    return 0;
}

コメントを書いてて「私がやっているのはプログラミングではなく論理学なのでは?」と思い始めた。説明がとても難しい......。

感想

A,Bは順調だったんだが、C,Dの全ケースに対応しきれず死亡。やはりコーナーケースを考える練習が足りてないなぁと実感した。

特にこどふぉは最後までコーナーケースがあるかどうかも分からないコンテスト形式なので、その能力は今後の大きな課題になりそう。

f:id:misteer:20180617142606p:plain

結果は上の通り。紫から一歩遠ざかってしまった。

f:id:misteer:20180617142635p:plain

今月は上の通りなんかいっぱいコンテストがあるっぽいので、巻き返すチャンスはある。 しかし時間帯...。次回からは十分に仮眠をとることを心がけよう。


  1. 眠気がなかったら解けていたかというと、そうでもない気はする。

  2. この図はCSAのAppで簡単に作れます。geometry_widget

AtCoder Beginner Contest 100 振り返り

6/16に行われた記念すべき100回目のABC。 問題の内容もAtCoder社の方々が出てきてお祭り騒ぎ1って感じでしたね、楽しかったです。 問題としては、前回ほどの難易度ではなかったものの一部クセがある問題だった、という印象ですかね。

それでは、振り返っていきましょう。

※今回の記事は数式が多い一方で、はてなブログMarkdown記法ではtex記法がバグって使えないため一部大変見づらいです。 個人的にもこちらのHackMD版の方を推奨します。

目次

A - Happy Birthday! (お誕生日おめでとう!)

問題リンク

概要

中心から放射状に16等分された円形のケーキがある。 16個のピースから隣接した要素を選ばないように2人でそれぞれM個、N個取ることが可能か判定せよ。

ちなみに可能な場合は「Yay!」、不可能な場合は「:(」と出力するように。

解説

まず2人のうち一方でも9個以上のピースを取ろうとすると、2つの隣接した要素を選んでしまうのはお分かりだろう。俗に言う「鳩の巣理論」というやつ。

したがってM,N ≦ 8が必要条件となるのだが、実はこれが必要十分条件となる。

というのも、ケーキのピースを時計回りにA,B,A,B ...と割り振っていき、1人目がAからM個、2人目がBからN個取れば条件は自動的に達成されるからだ。

回答例

int main() {
    int A, B;
    cin >> A >> B;
    if (A <= 8 && B <= 8) {
        cout << "Yay!" << endl;
    } else {
        cout << ":(" << endl;
    }
    return 0;
}

A問題にしては少しひねりがあるが、落ち着けばなんとかなる。

出力にも要注意。この形式はさすがに初めて見た。FA対策?

あと問題内容読んで思ったんだが、今日は双子くんの誕生日なのかな? だとしたらおめでとうございます。

B - Ringo's Favorite Numbers (りんごさんの好きな数)

問題リンク

概要

100で丁度D回割り切れる数で、N番目に小さいものを出力せよ。

(0 ≦ D ≦ 2, 1 ≦ N ≦ 100)

解説?

例えばD=1の場合、当てはまる数は

100, 200, 300, 400, ...

といった具合になる。 ここからもお察しの通り、Nを100D倍したやつがまんま答えになる。

回答例?

int main() {
    int D, N;
    cin >> D >> N;
    
    // hund = 100^D
    int hund = 1;
    REP(i, D) {
        hund *= 100;
    }

    cout << N * hund << endl;
    return 0;
}

Bにしては簡単かな? とりあえず提出しましょ。

f:id:misteer:20180616235126j:plain

はい、という訳でこの手の回答を提出した方々はまんまと双子くんの罠にハメられたのでした。無論僕もハメられた1人。

コーナーケース

では何がいけなかったのか? 答えを言ってしまうと、N=100の場合がコーナーケース。

例えばD=1, N=100では上のコードだと10000を出力するが、条件は「100で丁度D回割り切れる」ことなのでこれは条件を満たさない(2回割り切れるため)。

という訳で、N=100の場合だけNをインクリメントする必要があるのでした (そこさえ直せば通るので、回答例は省略)。

いや〜、いい問題作るね。これに引っかかったか否かで順位が結構変わるので、ある意味で今大会の鍵を握る問題。

C - *3 or /2 (×3 or ÷2)

問題リンク

概要

数列a_1, a_2, ... , a_Nが与えられる、これらの全要素に対して、

  • 2で割る
  • 3を掛ける

のいずれかを行う操作を考える(ただし前者は最低でも1要素に対して行い、操作後の値は整数でなければならない)。

この操作が最大で何回できるかを求めよ。

解説

まず、「3を掛ける」という操作は任意の要素に対して何度でも行える。 したがって操作が行えなくなるのは「2で割る」という操作が全要素に対して行えなくなる、つまり全要素が奇数となる場合である。

これを極力先延ばしにしたいんだから、1回の操作で2要素以上を2で割るのは明らかに無駄(2ターンに渡って1要素ずつ2で割った方が長持ちするため)。

従って答えは、各要素の2で割れる回数の総和ということになる。 これはa_iが偶数である間a_iを2で割り続ければ簡単に求まる。

回答例

int main() {
    int N;
    cin >> N;
    
    int ans = 0;
    REP(i, N) {
        ll a;
        cin >> a;
        
        // aが偶数の間2で割り続ける
        while (a % 2 == 0) {
            ans++;
            a /= 2;
        }
    }
    cout << ans << endl;
    return 0;
}

aは配列に代入してもいいけど、どのみち使わないので上のコードではローカル変数にしている。

D - Patisserie ABC (ABC洋菓子店)

問題リンク

概要2

ABC洋菓子店ではN個のケーキが1個ずつ売られており、各ケーキのデータはx[i], y[i], z[i]の3整数(負も含む)で与えられる。

この中からケーキをM個選び、S = |選んだケーキのx[i]の総和|+|選んだケーキのy[i]の総和|+|選んだケーキのz[i]の総和|を定義する。

Sの最大値を求めよ。

解説

全部正なら

例えばx[i], y[i], z[i]が全て0以上ならどうなるかというと、答えは以下のような貪欲法3で簡単に求まる。

  • 各iについて、data[i] = x[i] + y[i] + z[i]を求める。
  • dataを降順にソートする
  • dataを上からM個足していったのが答え。

しかし問題は負の値が含まれている場合。もう少し深く考えてみる必要がある。

負が混ざる

ここでSx = | 選んだケーキのx[i]の総和 |と定義する(Sy,Szも同様)。

例えば最適の選び方においてSx < 0 < Sy, Szの場合、S = - Sx + Sy + Szで答えが求まる。

このとき、上のアルゴリズムdata[i] = - x[i] + y[i] + z[i]のように書き換えてみる。 すると、最適にM個選んだ場合のSは選んだ要素のdataの総和で求められる。

ではどのようにM個選べばいいかといえば、先と同様の貪欲法でいい。 したがって、dataの計算式を上のように書き換えただけでそのままアルゴリズムを適用すれば、答えが求まるわけである。

この発想こそが本問の肝で、x, y, zの符号を全探索して上のアルゴリズムを適用すれば、実は答えが求まるのだ4

符号の全探索は3bitのbit全探索5を使えば比較的楽に実装できる。

回答例

int main() {
    ll N, M;
    cin >> N >> M;
    V<tuple<ll, ll, ll>> cake(N);
    // tupleは2つ以上の値を持つPairみたいなもの
    
    REP(i, N) {
        ll x, y, z;
        cin >> x >> y >> z;
        cake[i] = make_tuple(x, y, z);
    }

    ll ans = 0;
    // 最悪のケースでもS>=0なのでこの初期化でよい
    
    REP(pat, 8) {
        // patが+,-の状態を管理するbit
        // 例えばbit=101なら
        // data[i] = - x[i] + y[i] - z[i]
        
        V<ll> data(N);
        
        REP(i, N) {
            ll x[3];
            tie(x[0], x[1], x[2]) = cake[i];
            // cake[i]の値を取り出し
            
            REP(j, 3) {
                if (pat & (1 << j)) {
                    // ここでbitが1の位置に当たる値の符号を反転
                    x[j] = -x[j];
                }
            }
            data[i] = x[0] + x[1] + x[2];
        }
        
        GSORT(data);
        // 降順ソートで上から貪欲に選んでいく

        ll val = 0;
        REP(i, M) {
            val += data[i];
        }
        ans = max(ans, val);
    }

    cout << ans << endl;
    return 0;
}

bit全探索の部分は慣れてないと実装しにくいし読みづらいので、実装経験がない方は今のうちに練習しておくことをオススメする。

400点は妥当かな、という印象はあるが証明が難しい。 私は証明していないが直感で正しいと信じて提出したため、数分に及ぶWJの間ずっとソワソワしていた。通った瞬間の安堵感たるや。

感想

冒頭でクセがあると言っていたのはA,B問題のことで、どちらも点数の割には難しかったような。代わりにC問題が簡単めだったので打ち消しかな。

Dは発想自体は浮かぶのだが証明が難しく、最後の一歩をためらいそう。一目ではbit全探索とは気づかないし、面白い問題だと思う。

f:id:misteer:20180617001155p:plain

一方で私の戦果は上の通り全体で36位。私にしてはとても良くできた方。 しかしUnratedなのが残念。来週は3週間振りのARCなので思う存分暴れてやりたいところ。


  1. ジャッジもお祭り騒ぎでしたね…(AtCoder社の方々お疲れ様でした)。

  2. 説明の便宜上、本文とは大きく異なる部分があります(でも問題の内容は同じです)。

  3. 後先のことを何も考えず、常に最善の状態を取るように行動するような手法のこと。

  4. ここで「Sx < 0と仮定しても上の方法じゃSx ≧ 0になる場合もあるのでは?」と思った方はよく考えてらっしゃる。証明は私には難しいので省くが、その場合でも-S_x ≦ 0となることによってその振り分けが最適でないことが包意される(多分)。

  5. 値を2進数表記したときの、各桁の値を状態とみなすことで全パターンを調べる技法。上の問題では(0, 1) ↔ (+, -)と対応付けることで、(+, -)の全パターンを調べている。