Mister雑記

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

TSG LIVE! 2 競技プログラミング反省

この記事はTSG Advent Calendar 2018の10日目に書かれたものです。

先日はdaiさんによる「キーボード盗聴の話?」でした。


初めましての方は初めまして、Misterと申します。

私は東京大学のTSG(理論科学グループ)というサークルに所属しているのですが、TSGは今年の駒場祭1で「TSG LIVE! 2」という企画を3日に渡って開催しました。

TSGの部員達が「競プロ」「AI実装」「コードゴルフ」「CTF」を実際にやる様子をYouTubeniconicoの生放送で実況するというもので、私はそのうち「競プロ」「AI実装」でプレイヤーとして参加しました。本記事ではそのうち「競プロ」の方について語ります。

なお一口に競プロと言いましたが、今回行われたのは「アルゴリズム」ではなく「マラソン」でした。とはいえ時間が75分なのでマラソンの中ではとても短い部類ではありました2

目次

問題概要

イワシの収穫祭」

壁がまばらに配置されている H \times Wのグリッドがある。

グリッド上にいるfiordくんは、毎ターンいずれかの方向へ1マスずつ移動する(あるいは移動しない)ことで、 Tターンに渡って N匹の「イワシ」を収穫する。

イワシは特定のターンにグリッド上に生えてくる。そして毎ターン、fiordくんか他のイワシの中で、自分に最も近いものに近づくように移動する(細かい動き方は割愛)。なおイワシは複数匹が同一のマス上に存在することができる。これを「群れ」と呼ぶことにする。

fiordくんはイワシの群れに接触することでイワシを回収できる。しかしイワシは集団になると凶暴になる性質がある。fiordくんは6体以上のイワシの群れに接触すると、回収できない上に怪我をして5ターン行動不能になる。

最初にグリッドの配置と各イワシの出現するターン及び位置が与えられる。このとき、fiordくんの動きを出力せよ。

制約と点数

  • 全ケース共通

    •  H = W = 22
  • tiny (1ケース)

    •  N = 50
    •  T = 150
    • 壁は全体の 15\%
  • little (6ケース)

    •  N = 250
    •  T = 1000
    • 壁は全体の 25\%
  • much (6ケース)

    •  N = 3000
    •  T = 1000
    • 壁は全体の 25\%
  • challenge (3ケース)

    •  N = 1000
    •  T = 1000
    • 壁は全体の 47.5\%、作為的に生成

challengeのケースは以下のようになっており、盤面が実質直線になっている。

f:id:misteer:20181209220631p:plain:w400

各ケースごとにイワシの収穫率がそのままスコアとなり、その合計が最終スコアとなる。

本番の流れ

事前にfiordさんから聞いていたので覚悟はしていましたが、まぁまぁ問題文が長い。特にイワシの動きの部分が曲者なのですが、「一番近いfiordくんとイワシに近づく」ということだけ頭に入れて読み流しました。実はサンプルコードに動きをシミュレートするコードが入っているので、イワシの動きが細かく分からなくてもなんとかなります。

乱択厳選

ラソンということで、最初にしたのが乱択です。ランダムに方向を決めて、実際にシミュレートします。

しかしここで競プロerにあるまじきミス。fiordくんの移動は自身でシミュレートするのですが、その際に壁判定と場外判定を両方飛ばしまいました。結果として範囲外参照が出たり出なかったりすることになり、しばらく唸っていました。

それに気づいてバグを修正したのが大体25分頃。そこから少しだけ工夫をして、この生成を7回繰り返して最適なやつを選択するコードを提出したのが35分頃でした。

しかしこのスコアが4.99点とあまり芳しくありませんでした。なぜか前に出したバグ有り乱択の方が5.29点とスコアが高いという有様。この時点で対戦相手のdaiさんは5.73点を出しており、内心焦っていました。

中心へ

ここで初めてビジュアライザを起動。すると、想像していた以上にイワシがfiordくんへ吸い寄せられていることが分かりました。

「これ下手に動かない方が良いのでは?」と勘付き、試しに一度も動かないコードを提出してみると5.56点と最高記録が出ました3

そして特にスコアが高かったやつ(これ)をビジュアライザで眺めていると、「グリッドの中心に近いほどイワシが効率的に吸い寄せられるのではないか」と思い始めました。以降それを実装することになります。

逆辺張りBFS

後は中心へ移動するプログラムを組むだけです。具体的には「逆辺張りBFS」をします。

まずfiordくんの初期位置を始点としてBFS(幅優先探索)をします。このとき、「どの方向の移動によってそのマスへ移動したか」を同時に記録します。

f:id:misteer:20181209220713j:plain

次に目的地を決めます。今回は到達可能な中で (H / 2, W / 2)とのマンハッタン距離が一番小さい場所を目的地にしました。

最後に経路を求めます。今度は目的地を始点として、先程の遷移を逆走するようにします。すると最終的にはfiordくんの初期位置へたどり着きます。その際通った文字を反転させれば、これが目的地へ移動するような文字列になるわけです。以下の例ではNEENNがそれに当たります。

f:id:misteer:20181209220731j:plain

このアルゴリズムを思いつくのは秒なのですが、実装に地味に時間がかかりました。その根底のミスが「queueへのpushし忘れ」というしょうもないもので、これに気づかないまま終わっていたら競プロ引退案件でした。

それでもなんとかそれに気づいて終了2分前に提出。これが無事バグ0で真ん中へ移動してくれて、6.38点という最高得点を叩き出しました。

結果

終結果は私のスコアが最終提出の6.38点、daiさんのスコアが最初の提出の5.73点でなんとか勝つことができました。

後でコードを読んだところ、daiさんは「10手先読み」を実装していたようです。具体的には、「あと n手ある状態で各方向へ移動した場合の最高スコア」を再帰的に求めて、一番いい方向へ動くというものです。

ただし今回の問題はシミュレーションにとても時間がかかるため、TLE(15sec超過)になっていたことに気づかなかったそうです。それにしてもあれだけの量を75分で実装していたのは驚嘆という他ありません。

想定解法

ライブ終了後、fiordさんに想定解法を訊いたところ「影響マップ」という単語が出てきました。

fiordくんはできるだけイワシを収穫したいので、当然ながらイワシに近づきたいことになります。一方で6匹以上のイワシの群れには当たると怪我してしまうため、できるだけ近づきたくありません。

そこで、5匹以下のイワシの群れからは「正のオーラ」、6匹以上の群れからは「負のオーラ」が周り全体へ広がっていると考えます。これらのオーラは発信源から遠くへ行くほど小さくなり、重ね合わせると互いに打ち消し合います。そして全てのオーラを重ね合わせたとき、一番正のオーラが強い方に移動すると得ということになるわけです。

これが「影響マップ」という考え方だそうで、「なるほど確かに実装も楽そうだなぁ」と思いました。マラソンと言えば「焼きなまし法」と「ビームサーチ」しか知らなかったので、良い知見が得られました。

反省

ラソンと言っておきながら最終的には「真ん中に移動するだけ」になりましたが、それはそれで競プロらしくて良いんじゃないかなと思います。

ただ範囲外参照やBFSのバグについては要反省ですね。緊張して大分焦ってコードを生んでいたので、もう少し落ち着きを持てるようになりたいです。

ラソンも楽しいのですが、次にTSG LIVEがあれば作問に挑戦してアルゴリズムも開きたいなぁと思いました。今回のCTFの点数形式がアルゴに近い感じで、アルゴ勢はTSGにもそれなりにいるので楽しそうです。まぁ作問ができればの話ですが。


本記事は以上になります。最後まで読んでいただきありがとうございました。

明日の記事はmoratoriumさんの「駒場祭AIコンテストで作ったゲーム」です。冒頭に述べた通り、私はAIコンテストの方にもプレイヤーとして参加したので楽しみです。ちなみにAIの方の反省記事は20日目に書く予定ですので、そちらも読んでいただけると幸いです。





  1. 東京大学には年に2回学校祭が開かれていて、そのうち秋に開かれる方が「駒場祭」です。ちなみにもう1つは春に開かれる「五月祭」。

  2. 作問者のfiordさん曰く、「400m走」的な感覚だそうで。実際75分間に渡って、アルゴリズム並のスピードで考察、実装することが求められました。

  3. 後から分かったことですが、バグ有り乱択はバグが起きたときに何も出力されず、それが「何も動かない」と解釈された結果それなりの点数が出たわけです。daiさんが最初に出したコードもサンプルコードそのままで、これが何も出力しないものだったので5.73点という点数が出ていたようです。

ABC115 解説 (未完)

2週間早いクリスマスコンテスト。

beta.atcoder.jp

A. Christmas Eve Eve Eve (100)

beta.atcoder.jp

概要

今日の日付( 12 D日)が与えられる。

Christmasに続けて、今日からクリスマス( 12 25日)までの日数分だけEveをスペース区切りで出力せよ。

制約

  •  22 \leq D \leq 25

解説

まずはChristmasを出力、その後 D - 25回だけfor文なりでEveを出力すればいい。while文で D 25になるまでインクリメントするのもよい。

Christmasは手で打つとタイプミスしやすい。これでWAを食らうと目も当てられないので、安全をとって問題文からコピペするといいだろう。

実装例

#include <iostream>
using namespace std;

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

    cout << "Christmas";

    for (int i = 0; i < D - 25; ++i) {
        cout << " Eve";
        // Eveの前にスペースが入っていることに注意
    }

    cout << endl;
    return 0;
}

ちなみにABCのA問題はforやwhileといったループ構文を使わなくても解けるようになっているらしい。今回の場合、各 Dの値に応じて埋め込みをするのも立派な解法である。

B. Christmas Eve Eve (200)

beta.atcoder.jp

概要

高橋くんはデパートで N個の商品を買おうとしている。 i個目の商品の値段は p_i円である。

高橋くんは割引券を1枚持っており、最も値段の高い商品を半額で買うことができる。このとき高橋くんが支払う金額を求めよ。

制約

  •  2 \leq N \leq 10
  •  100 \leq p_i \leq 10,000
  •  p_iは偶数

解説

問題文通りに実装しようとすると、以下のようになる。

  1. 長さ Nの配列 \{p_i\}を用意し、標準入力を受け取る。
  2. ソートする。
  3. 一番値段の高いやつを 2で割る。
  4. 配列の総和を求め、出力する。

あるいは少し工夫をすると、以下のようにもできる。

  1.  p_iの総和と最大値を持つ変数を用意する。
  2. 標準入力から p_iを受け取り、総和に加えながら最大値を更新していく。
  3. 得られた総和から、最大値の半分を引いたものを出力する。

まぁどっちが悪いというものでもないと思う。前者はバグらせにくい一方、後者は計算量が時間、空間ともに少ない。

実装例

今回は私が本番で実装した後者の実装例を上げる。

#include <iostream>

using namespace std;

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

    int sum = 0, pmax = 0;
    for (int i = 0; i < N; ++i) {
        int p;
        cin >> p;
        sum += p;
        pmax = max(pmax, p);
    }

    cout << sum - pmax / 2 << endl;
    return 0;
}

C. Christmas Eve (300)

beta.atcoder.jp

概要

高羽氏の庭には N本の木が植えられている。 i本目の高さは h_iである。 高羽氏はこれらの木のうち K本を選んでクリスマスツリーにしたい。

ここでクリスマスツリーの「美しさ」は、選んだ木の高さの最大値と最小値の差となる。 クリスマスツリーの「美しさ」の最小値を求めよ。

制約

  •  2 \leq K \lt N \leq 10^5
  •  1 \leq h_i \leq 10^9

解説

数列 \{h_i\}の並び順はどうでもいいので、例によってソート済みとする。

 \{h_i\}からどんなふうに K個選ぶと、「最大値と最小値の差」を小さくできるか?これは直感的にも「連続した K個を選ぶ」のが最適だと分かるだろうか。

証明

これを簡単に証明すると以下の通り。

連続していない K個を選んだとしよう。このとき一番小さい要素が i個目、大きい要素が j個目だったとする。  K個が連続していないことから、 i \lt k \lt j k個目が選ばれていないようなものが存在する。このとき i個目を捨てて代わりに k個目を選んだとする。 すると木の高さの最小値は変わらないか大きくなる一方で、最大値は変わらない。よってこれがより良い選び方となる。  \square

こんな具合に「理想的な状態でなければより良い状態が存在する」というのは、主に貪欲法の証明でよく使われる手法である。

それと本番でここまでの証明を書きつける必要はない。頭の中に大枠が描ければ十分である。


あとは連続する K個の選び方を全パターン試せばいい。具体的には、 i 1から N - K + 1まで回して h_{i + K - 1} - h_iの最小値を更新していけばいい。

実装例

上は1-indexedなのに対し、以下の実装例は0-indexedなので若干ズレがある。

#include <algorithm>
#include <iostream>

using namespace std;

const int INF = 1 << 30;
// INF >= 10^9 - 1

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

    int h[N];
    for (int i = 0; i < N; ++i) {
        cin >> h[i];
    }
    sort(h, h + N);

    int ans = INF;
    for (int i = 0; i + K - 1 < N; ++i) {
        ans = min(ans, h[i + K - 1] - h[i]);
    }

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

ansの初期値に注意。解の最大値は 10^9 - 1なので、これ以上でなくてはならない。かといって余り大きくしすぎるとintではオーバーフローを起こす。無難にlong longを使うのも手。

D. Christmas (400)

beta.atcoder.jp

概要

TBU...

解説

TBU...

実装例

多分解説を書くのに相当時間がかかるので、先に実装例だけ載せておく。

long longにしないとオーバーフローを起こすので要注意(5分ロス)。

#include <iostream>
using namespace std;
using ll = long long;


ll l[51], p[51];
// l[i] = レベルiのハンバーガーの層数
// p[i] = レベルiのハンバーガーに含まれるパティの数


// レベルNのハンバーガーの、下からX層にパティは何枚入っているか?
ll rec(int N, ll X) {
    if (X <= 0) return 0;

    // レベルNのハンバーガーを丸々食べるケース
    // これで計算量が落ちる
    if (X >= l[N]) return p[N];

    ll ret = 0;

    // 下にあるレベルN-1のハンバーガーの分
    ret += rec(N - 1, X - 1);

    // 真ん中のパティの分
    if (X > l[N - 1] + 1) ++ret;

    // 上にあるレベルN-1のハンバーガーの分
    ret += rec(N - 1, X - l[N - 1] - 2);

    return ret;
}


int main() {
    // l, pを埋める
    l[0] = 1, p[0] = 1;
    for (int i = 1; i <= 50; ++i) {
        l[i] = l[i - 1] * 2 + 3;
        p[i] = p[i - 1] * 2 + 1;
    }

    ll N, X;
    cin >> N >> X;

    cout << rec(N, X) << endl;
    return 0;
}

感想

  • DはABC onlyにしては難しめかなという印象。
  • それでもDの実装に時間掛けすぎた(15分強)。
  • ちなみに結果は22:49で49位。

Codeforces Round 525 (Div.2) A-D

codeforces.com

4完3886点で323位(Rated内260位)。

f:id:misteer:20181205154326p:plain

なんとか紫に戻ることができました。

f:id:misteer:20181205154357p:plain

目次

A. Ehab and another construction problem

codeforces.com

概要

整数 xに対して、以下を全て満たす整数 a, bが存在すれば出力せよ。

  •  1 \leq a, b \leq x
  •  a bで割り切れる
  •  ab \gt x
  •  \frac{a}{b} \lt x

制約

  •  1 \leq x \leq 100

解法

一番素直なのが a, bの全探索。条件の中身を深く考えなくていいので楽。

しかし少し考察をしてみると、 x \gt 1の場合は簡単な解が存在することが分かる。それが a = b = xである。これが上の性質を満たすことは確かめれば分かる。

私は本番では後者で通したのだが、考察に時間がそれなりにかかってしまったので前者の方が実践寄りと言えそうな気がする。もっとプログラムの力に頼っていきたいところ。

実装例

#include <iostream>

using namespace std;

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

    if (x == 1) {
        // 解無し
        cout << -1 << endl;
    } else {
        // a = b = x
        cout << x << " " << x << endl;
    }
    return 0;
}

B. Ehab and subtraction

codeforces.com

概要

長さ Nの数列 \{a_i\}が与えられる。これに対して以下の操作を K回したときの出力を求めよ。

  1.  \{a_i\}で正の最小の要素( dとおく)を出力する。
    • 全要素が 0の場合は 0を出力して操作を終了する。
  2.  \{a_i\}の各正要素から dを引く。

制約

  •  1 \leq N, K \leq 10^5
  •  1 \leq a_i \leq 10^9

解説

まずこの問題ではindex(数列中の位置のこと)は関係がないので、最初に分かりやすいように数列を昇順にソートしてしまうことにする。

具体例として、 a = \{ 3, 1, 4, 1, 5, 9, 2, 6, 5 \}の場合を考えると以下の通り。

 \displaystyle \{ 3, 1, 4, 1, 5, 9, 2, 6, 5 \} \\
\downarrow sort \\
\{1, 1, 2, 3, 4, 5, 5, 6, 9\} \\
\downarrow print(1) \\
\{0, 0, 1, 2, 3, 4, 4, 5, 8\} \\
\downarrow print(1) \\
\{0, 0, 0, 1, 2, 3, 3, 4, 7\} \\
\downarrow print(1) \\
\vdots

このように操作を考えると、以下の操作と同値であることが分かる。

  1.  \{a_i\} 0を挿入してソートする。
  2.  \{a_i\}から重複を取り除き、各値が高々1度ずつ現れるようにする。
  3. 前から順番に、隣り合う項の差を出力していく。

最初に 0を挿入したのは、最初の要素を出力するときに都合が良いためである。

上と同じ aで考えると、以下の通り。

 \displaystyle \{ 3, 1, 4, 1, 5, 9, 2, 6, 5, 0 \} \\
\downarrow sort \\
\{0, 1, 1, 2, 3, 4, 5, 5, 6, 9\} \\
\downarrow unique \\
\{0, 1, 2, 3, 4, 5, 6, 9\} \\
\downarrow diff \\
\{1 - 0, 2 - 1, 3 - 2, 4 - 3, 5 - 4, 6 - 5, 9 - 6\} \\
= \{1, 1, 1, 1, 1, 1, 3\}

あとはこれの先頭から K個を出力し、足りない分は 0を出力すればOK。

実装例

上のをそのまま実装すると以下のようになる。

std::uniqueを使って重複要素を消す方法については、こちらの記事が参考になるだろう。

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

using namespace std;

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

    vector<int> a(N + 1);
    for (int i = 0; i < N; ++i) {
        cin >> a[i];
    }
    a[N] = 0;

    sort(a.begin(), a.end());
    a.erase(unique(a.begin(), a.end()), a.end());
    // これでaから重複要素が消える

    for (int k = 0; k < K; ++k) {
        if (k < a.size() - 1) {
            cout << a[k + 1] - a[k] << endl;
        } else {
            cout << 0 << endl;
        }
    }
    return 0;
}

なお私は本番ではsetを使って実装した。ただsetを使うとイテレータとかをイジる必要が出てきて、少しC++の知識が必要となる。

C. Ehab and a 2-operation task

codeforces.com

概要

長さ Nの数列 \{a_i\}が与えられる。これに対して以下のいずれかの操作を合わせて N + 1回以下行い、 \{a_i\}狭義単調増加となるようにしたい。

  1.  1 \leq i \leq N 0 \leq x \leq 10^6を指定する。各 1 \leq j \leq iについて、 a_j xを加算する。
  2.  1 \leq i \leq N 1 \leq x \leq 10^6を指定する。各 1 \leq j \leq iについて、 a_j xで割った余りで a_jを置き換える。

これを実現する操作列を出力せよ。

なお、任意の長さ Nの数列は N + 1回以下の操作で狭義単調増加となるようにできることが証明できる。

制約

  •  1 \leq N \leq 2 \times 10^3
  •  0 \leq a_i \leq 10^5

解説

いわゆる構築系の問題、といってもそこまで発想色が強いわけではない。

まず考えられる特異な操作として、「全体を 1で割る」ことが挙げられる。これをするとどんな数列だろうと全要素を 0にできる。 しかし考察をすれば分かるが、この操作が使えるのは狭義単調「減少」にしたいケースである。今回は残念ながら使えない。

構築系は自由度が高いので、できるだけシンプルなケースを構築する方針で考察を進めると上手く行きやすい。そこで今回は目的の数列を \{0, 1, \cdots , N - 1\}に固定して、それを実現する操作を考えることにする。

そしてこれを実現する操作手順の1つが以下の通り。

  1. 後ろから順に、 Nで割った余りが最後の数列と一致するように値を加える。
  2. 全体を Nで割る。

この操作回数は N + 1回とぴったりになりOKとなる。本番はこっちで実装した。

もう1つの解法として、以下のようなものがある。

  1. 全体に Nより大きい適当な値(例えば 5 \times 10^5)を加える。
  2. 先頭から余りが目的の数列と一致するように割っていく。

手前の方はすでに N未満になっているので、大きい数で割れば影響を受けないことを利用した巧い解法。できればこっちも思いつけるようになりたい。

実装例

今回は実装が短くて済む後者を実装することにする。

#include <iostream>

using namespace std;

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

    cout << N + 1 << endl;
    // 操作数はN+1で固定

    cout << 1 << " " << N << " " << 500000 << endl;
    // 最初に全要素に500000を足してしまう

    for (int i = 0; i < N; ++i) {
        int a;
        cin >> a;
        a += 500000;

        // aをiにしたい
        // aが十分大きいのでa - iで割ってしまえばいい
        cout << 2 << " " << i + 1 << " " << a - i << endl;
    }
    return 0;
}

もはや競プロあるあるだが、操作数の出力忘れに注意

あと最初に足す値を 10^6にしてしまうと、割る値が 10^6を上回ってWAになるので注意(多分サンプルで落とされる)。

D. Ehab and another another xor problem

codeforces.com

概要

ある固定された整数 a, bがある。あなたはクエリとして整数 c, dを投げることで、以下の返答を受け取ることができる。

  •  a \oplus c \gt b \oplus dなら 1
  •  a \oplus c = b \oplus dなら 0
  •  a \oplus c \lt b \oplus dなら -1

ここで \oplus排他的論理和を指す。

クエリを高々 62回投げることで、 a bを特定せよ。

制約

  •  0 \leq a, b \leq 2^{30}
  • 各クエリについて 0 \leq c, d \leq 2^{30}

解説

上から各bitを決めていくという方針で考える。

 kbit目より上は特定済みとしよう。このとき、 c, dをこの特定済みのものにすることで kbit目より上を全て0にできる。

このとき kbit目を求めたい。そこで、 (c + 2^k, d + 2^k)をクエリに投げてみる。このとき、加える前と後で大小関係が変化したか否かで場合分けをする。


大小関係が変化した場合

このとき kbit目は a, bで異なるものになっている。 (c, d) a \oplus c \gt b \oplus dなら a, b kbit目はそれぞれ 1, 0となる。逆もまた然り。

大小関係が変化しなかった場合

このとき kbit目は a, bで同じものになっている。これが 0 1かを決めるために、追加で (c, d + 2^k)を投げる。 a \oplus c \gt b \oplus (d + 2^k)なら 1、そうでなければ 0であることが確定する。


こんな具合に c, dを更新していくと、各bitを 2回のクエリで特定できるため最初に (0, 0) a, bの大小比較をする分と合わせて 61回のクエリで答えが求まる。

実装例

自画自賛だがこの実装はスマートな方だと思う。具体的な大小関係をあまり気にしなくていいのが大きい。

#include <iostream>

using namespace std;

// クエリを投げる関数
int question(int c, int d) {
    cout << "? " << c << " " << d << endl;
    int ret;
    cin >> ret;
    return ret;
}

int main() {
    int c = 0, d = 0;

    // 現在のc, dでのa^cとb^dの大小関係を保持
    int stat = question(c, d);

    for (int k = 29; k >= 0; --k) {
        int ret = question(c + (1 << k), d + (1 << k));

        if (ret == stat) {
            // 大小関係に変化なし = k桁目は同じ

            int ret = question(c, d + (1 << k));
            if (ret == 1) {
                c += (1 << k);
                d += (1 << k);
            }
            // この更新で大小関係に変化はないのでstatはそのまま

        } else {
            // 大小関係が変化 = k桁目は異なる
            // 元の大小関係でどちらが1かが分かる
            if (stat == 1) {
                c += (1 << k);
            } else {
                d += (1 << k);
            }

            // この更新では大小関係が変化しうるのでstatも更新
            stat = question(c, d);
        }
    }

    cout << "! " << c << " " << d << endl;
    return 0;
}

感想

  • Cがあまりにも遅かった。
  • その分Dが考察、実装ともにスムーズにいったので無事紫に戻れた。
  • 深夜は集中力が続かない。

超自己流! 競プロ解説記事の書き方

この記事はCompetitive Programming (2) Advent Calendar 2018の6日目の記事になります。

先日はiwashi31さんによるWhat COMPETITIVE PROGRAMMING Gives You の日本語訳でした。

はじめに

初めましての方は初めまして、Misterと申します。競技プログラミング(アルゴリズム)が趣味のしがない大学生です。 精進の一環として、はてなブログにて主にAtCoderという競技プログラミングサイトの問題の解説記事をいくつか上げています。

解説記事というのは、簡単に言うと「その問題をどう考察し、どう実装して解いたか?」を主題にした記事のことです。 本記事ではそんな解説記事をどうやって、そして何を意識して書いているかを解説します。いわゆる「解説記事の解説記事」です。

注意事項として、タイトルに「超自己流」とある通り私の解説記事の書き方は完全に自己流となっています。そのため一般的な解説記事にはそぐわないような性質があるかもしれませんが、ご了承ください。

目次

解説記事の構成

今まで何度か解説記事を書いてきた上で、記事全体の構成というのはある程度テンプレ化されてきています。 ここではそのテンプレの各項目、

  1. イントロ
  2. 問題概要
  3. 解説
  4. 実装例
  5. 感想

について簡単に紹介していきます。

イントロ

解説に入る前の導入及び雑談的なものです。例えば下のような一言コメントがそれに当たります。

コンテスト記事などでは入ることがよくありますが、最近はあまり入れていません。

それとここに問題ページへのリンクを貼るようにしています。

問題概要

問題文を要約したものと制約です。

AtCoderは元の問題文がかなり短くてそもそも要約できないことが多々ありますが、Codeforcesのような英語かつ長い問題文のときは読者の負担を減らすことができます。

ただ要約しすぎて原文とは全く趣が異なる文章が生成されることもよくあるので、その辺は悩みどころです。 私は問題を解く上で不要な要素は極力省いていますが、問題空間を把握しやすくする要素は残すようにしています。

そして忘れてはいけないのが制約です。制約は解法を考える上で決定的になりうる要素なので、毎回欠かさずに書くようにしています。 その方が後々考察を述べる上でも好都合です。

解説

考察の過程、及び論理的な解法の導出です。

これはあくまで個人的な意見ですが、解説記事の読者が求めているのは主に以下の2点だと考えています。

  • どのような考察の流れで解法に辿り着いたか
  • Editorialのギャップを埋める補足、あるいはより分かりやすい解法

上の2点はできるだけ入れるようにしていますが、一方でこれらは言語化が難しいことが多いです。場合によっては潔く言語化を諦めて文章量を減らしたりしています。

解説での重要なテクとして、図を挿入することが挙げられます。図は情報量が文章の比ではないので、上手く使えば解説の量を減らしつつ質を高めることができます。

特にグラフ問題では強力なケースが多く、例えばこの記事は図に相当力を入れています。

ただし図を描くには相応の労力がかかるので、費用対効果と要相談です。図を描かなくて済むならそれが一番いいです。

やるだけ?

よくコンテスト後のTLを見ていると「はい」「やるだけ」といった感想がよく流れてきます。本人にとっては考察をするまでもない、自明な解法という意味です(多分)。 精進ログ的な記事ならそれだけでもいいのですが、解説記事と銘打っている以上これらの単語で済ませることだけは絶対にしないように心がけています1

とはいえABC-A,Bではそう感じる問題も少なくありません。そういった問題の解説では、実装する上で便利なテクニックなんかをもしあれば書くようにしています。

実装例

解説に基づいたプログラムの実装例です。ここのやり方については解説記事でも大きく以下の2つに分けられます。

  • コードを本文に埋め込む
  • 提出ページへのリンクを貼る

前者は流れが自然になる一方で、後者は記事全体の文章量が減ってスッキリするといった利点があります。私は前者派です。

マクロ

私が実装例を載せる上で独自に心がけていることがあります。それは「マクロを一切使わない」ことです。 というのも知らない構文に会う度に定義元を探すという作業は、読み手にとって非常に高コストかつストレスになると思っているからです。

ということで私が実装例に書くコードは

  • using namespace std
  • using ll = long long

以外のマクロは一切使っていません。それに加えて必要以上のincludeもしないようにしています。

それでも本番で出したコードをわざわざ整形するのは手間です。というわけで私はこれを意識し始めてから、コンテスト本番でもほとんどマクロを使わなくなりました。可読性が上がって一石二鳥ですね。

感想

その問題の難易度推定や知見、反省を3行くらいでまとめたものです。

正直なくても全然いいのですが、気分で書いてます。

解説記事ができるまで

以上で解説記事の枠組みの解説は終わりです。

続いて、1つの解説記事ができるまでに私がどういった作業工程を踏んでいるかを大まかに解説します。

問題を解く

当然ながら解けない問題の解説は書けません。解けたとしても解説記事を書くか否かは正直モチベ次第です。2

それでもABC onlyはできるだけ解説記事を書くようにしています。コンテスト終了時刻に投稿できるのが一番の理想なので、20〜40分で全完して残り時間でせっせと書くというのが最近のパターンです。くれぐれもコンテスト終了前に投稿しないようにしましょう。

下書き

解説を書くと決まったら次は下書きです。

書く順序は基本的に上から順番です。概要と実装例はそこまで手間ではないのですが、解説の項は難儀することがよくあります。実装例も解説次第で変わることがあるので、やはり上から書くのが一番やりやすいでしょう。

一通り書き上げるまでにかかる時間ですが、全容を把握できている問題なら30分、図が入るとプラス30分くらいです。一方で解説が難しかったり図が大量に入るときは2時間程度もザラにあります。

HackMD

解説記事の下書きですが、私ははてなブログの執筆ページで直書きしているわけではありません。 ではどこで下書きを書いているかというと、HackMDというツールです。

HackMDはオンラインのmarkdown専用テキストエディタのようなものです。書き始めるのが楽で、リアルタイムプレビューができたり自動保存もしてくれる優れものです。3 今ではHackMDで一旦全部書き上げてから、それを整形したものをブログに投稿するという形式を採っています。整形方法については後で述べます。

そしてこの記事も例外ではありません。下書きのHackMDリンクを貼っておくので、参考までにどうぞ。https://hackmd.io/s/SkfUg7mk4

それとHackMDで下書きをする上で注意点が1つ。HackMDのドキュメントはeditableの状態で公開してしまうと、全世界のユーザーがアクセス可能になります。それがコンテスト中なら盛大なネタバレになってしまうわけです。それを防ぐためにも、公開範囲は毎回editableからprivateに変更しておきましょう。

Illustrator

構成の解説の項でも述べた通り、効果的に解説をするために図を挿入することがよくあります。私は図を描くのにAdobe Illustratorというソフトを使っています。有料でお値段もそこそこしますが4、イラスト描画ツールの中では相当高性能なものです。

ただし個人的にこのソフトを競プロの解説に使うのはあまり気に入っていません。というのも、新規にファイルを作って描画して保存して書き出して...というのが結構手間だからです5。こればかりはどうしようもないと割り切っていますが、もっと手軽に使えるツールがあればぜひ教えていただきたいです。

整形、投稿

HackMDで書き上げた下書きは、はてなブログのフォーマットに合うように整形しなくてはなりません。 私ははてなブログmarkdown記法を選択しているので、大部分は下書きのままでも大丈夫です。しかし問題なのは数式で、全ての$$[tex:]に変えるなんて作業を毎回手でしていたら気が狂います6

そこで「退屈なことはPythonにやらせよう」よろしく、専用のプログラムを自作しました。それがこちら。

import sys

in_code_block = False
in_math_block = False
in_math_line = False

lines = sys.stdin.readlines()

output = ""

for s in lines:
    if s[:2] == "$$":
        if in_math_block:
            output += "]</div>\n"
        else:
            output += "<div style=\"text-align: center\">[tex: \displaystyle "
        in_math_block ^= True
        continue

    if s[:3] == "```":
        in_code_block ^= True
        output += s.replace("=", "")
        continue

    if in_math_block or in_code_block:
        output += s
        continue

    for c in s:
        if c == "$":
            if in_math_line:
                output += "]"
            else:
                output += "[tex: "
            in_math_line ^= True
        else:
            if in_math_line:
                if c == "^" or c == "_" or c == "\\":
                    output += "\\"
            output += c
print(output)

このプログラムにHackMDで書いた下書きを標準入力として与えると、はてなブログのフォーマットに合わせたものが標準出力として出てきます。使いたい方はご自由に使っていただいて構いませんが、いかなる不具合があっても責任は取りません。

後はURL、カテゴリ、トップ画像を設定して投稿ボタンを押せば投稿完了です。

最後に

以上で本記事の内容は終わりになります。ここまで読んでいただきありがとうございました。

また重ね重ねになりますが、あくまでこの記事の内容は「超自己流」です。 日頃の精進のログを取るのなら各個人に合った書き方というのがありますし、その方が長続きするでしょう。 それでも「精進ログをつけてみたいけど、どうやって記事を書けばいいか分からない」という方々にとって、本記事の内容が少しでも参考になれば幸いです。

明日はty70jの「競プロにおける Processing の利用+おまけ」です。お楽しみに!


  1. あと個人的にこの表現が好きじゃないというのもあります。

  2. 本ブログの投稿頻度からお察しの通り、最近はモチベが低めです。

  3. 難点を挙げるとすれば、オンラインでないと使えないこととプレビューの都合上時々重くなることでしょうか。それを差し引いてもとても優秀なツールだと思います。

  4. 学生は安めの年1万強で買えます。大学生協なりで取り扱っていると思うので、学生のうちにいかがでしょうか。

  5. あと正直言って操作方法が分かりにくい。

  6. 昔は全て手作業で整形していました。今考えると正気ではないです。

ABC114 解説

※各問題名は表記ミスではありません。

beta.atcoder.jp

目次

A. 753 (100)

beta.atcoder.jp

概要

 X歳の高橋くんが七五三で祝われる(つまり7歳、5歳、3歳のいずれかである)かどうかを判定せよ。

制約

  •  1 \leq X \leq 9

解説

if文なり3項演算子で言われた通りに判定をする。or演算子を上手く使いたいところ。

実装例

#include <iostream>

using namespace std;

int main() {
    int X;
    cin >> X;
    if (X == 3 || X == 5 || X == 7) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }
    return 0;
}

あるいは3項演算子を使うと以下のようになる。

#include <iostream>

using namespace std;

int main() {
    int X;
    cin >> X;
    cout << (X == 3 || X == 5 || X == 7 ? "YES" : "NO") << endl;
    return 0;
}

B. 754 (200)

beta.atcoder.jp

概要

各桁が 1 \sim 9からなる文字列 Sが与えられる。

 Sから連続する3桁を取り出し、それと 753との差の絶対値を取ることを考える。

この絶対値の最小値を求めよ。

制約

  •  4 \leq |S| \leq 10

解説

考えうる全ての部分列について、それと753との差の絶対値を実際に計算する。

部分列を取る方法は色々ある。Pythonならスライスを使えば簡単なのだが、C++にはスライスはない。

そこで便利なのがsubstr関数。始点のindexと長さを引数として与えれば、簡単に部分文字列を求めることができる。ただし使うには#include<string>をしなくてはいけないので注意。

実装例

#include <cmath>
#include <iostream>
#include <string>

using namespace std;

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

    int ans = 1000;
    for (int i = 0; i < S.size() - 2; ++i) {
        // substrでi文字目から始まる長さ3の部分列を抽出
        // それをstoiで整数に変換
        int diff = 753 - stoi(S.substr(i, 3));

        // 最小値を更新
        ans = min(ans, abs(diff));
    }
    cout << ans << endl;
    return 0;
}

無論解が求まればば何でも良いので、絶対substrを使わなくてはならないわけではない。ただ存在だけでも覚えておくといざというときに役立つだろう。

C. 755 (300)

beta.atcoder.jp

概要

10進法表記したときに 7 5 3が最低1回ずつ現れ、他の数字が現れないような数を七五三数と呼ぶことにする。

このとき 1以上 N以下の七五三数はいくつあるか求めよ。

制約

  •  1 \leq N \leq 10^9

解説

まず考えられるのは 1から Nまで全部判定する方法。しかし Nが大きすぎてあまり現実的ではない。

桁DPも考えられるが、C問題にしては高度すぎるし何より実装したくない。

そこで逆に七五三数を全列挙することを考える。サンプル3を見れば分かるのだが、実は七五三数というのは結構少なくて十分全列挙できる。

と言うのは簡単だが、全列挙するのはそこまで簡単ではない。私は以下のように実装した。

  1. 桁数 d 3から 9まで回す。
  2.  b 0から 3^d - 1まで回す。
  3.  bを3進数表記したときの i桁目を 7 5 3に対応させて、長さ d 7 5 3のみからなる数を作る。
  4.  7 5 3が出現したかをチェックして、一度も出てこないものがあったらその数はパスする。
  5. その数が N以下なら答えをインクリメントする。

3について補足しておく。例えば b = 57のとき、 bを3進数表記すると 2010となるので 0 \rightarrow 7 1 \rightarrow 5 2 \rightarrow 3と対応させることで 3757が作れる。

実装例

上の手順の3なのだが、以下の実装例では bを3進数表記して反転させたのちに変換したことになっている。どちらにせよ全列挙はできるので問題はない。

あとmypow関数は普段から持っているテンプレートで、その場で実装した訳ではない。

#include <iostream>
#include <map>
#include <string>

using namespace std;

// b^nを計算する関数
int mypow(int b, int n) {
    if (n == 0) return 1;
    if (n == 1) return b;
    if (n % 2 == 0) {
        return mypow(b * b, n / 2);
    } else {
        return mypow(b, n - 1) * b;
    }
}

// 012と753を変換する変数
const string i2c = "753";
const map<char, int> c2i = {{'7', 0}, {'5', 1}, {'3', 2}};

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

    int ans = 0;

    // dは桁数
    for (int d = 3; d < 10; ++d) {
        for (int b = 0; b < mypow(3, d); ++b) {
            string S;

            int cb = b;
            // 1の位から753に変換してpushしていく
            for (int i = 0; i < d; ++i) {
                S.push_back(i2c[cb % 3]);
                cb /= 3;
            }

            // 7, 5, 3の出現回数を数える
            bool cnt[3];
            fill(cnt, cnt + 3, false);

            for (char c : S) {
                cnt[c2i[c]] = true;
            }

            bool judge = true;
            for (int i = 0; i < 3; ++i) {
                if (!cnt[i]) judge = false;
            }
            if (!judge) continue;

            // N以下ならカウントする
            if (stoi(S) <= N) ++ans;
        }
    }
    cout << ans << endl;
    return 0;
}

大分長い実装になってしまった、実際300にしては難しいと思う。あるいはもっとスマートに実装する方法があるのだろうか。

D. 756 (400)

beta.atcoder.jp

概要

正の約数をちょうど 75個もつ正整数を七五数と呼ぶことにする。

 N!の約数で七五数であるものの個数を求めよ。

制約

  •  1 \leq N \leq 100

解説

まずは正の約数の個数に関する知識が必要となる。

ある正整数 N素因数分解したら N = {p_1}^{a_1} {p_2}^{a_2} \cdots {p_m}^{a_m}と表せたとする( p_iは互いに異なる素数)。 このとき Nの正の約数の個数は (a_1 + 1) (a_2 + 1) \cdots (a_m + 1)で求められる。この解説は偉大なる高校数学の美しい物語様に投げさせていただく。

 75 = 3 \cdot 5^2 (a_1 + 1) (a_2 + 1) \cdots (a_m + 1)の形で表すことを考えると、七五数は以下の4パターンしかない事が分かる。

  •  p^{74}
  •  p^2 q^{24}
  •  p^4 q^{14}
  •  p^2 q^4 r^4

したがって N!素因数分解して、 p,q,rを全パターン調べると答えが分かる。  100以下の素数の数は25個なので、パターン数は 25^3 = 15625程度になって余裕で間に合う。

ただし p^2 q^4 r^4のパターンは注意が必要で、 q rで重複して数えてしまうことがある。これは q \lt rとすることで防げる。

実装例

エラトステネスの篩を実装するのが面倒だったので、ネットから引っ張ってきた素数一覧をそのままコピペしている。

#include <iostream>

using namespace std;

// 100以下の素数一覧
const int prime[25] = {
    2, 3, 5, 7, 11,
    13, 17, 19, 23, 29,
    31, 37, 41, 43, 47,
    53, 59, 61, 67, 71,
    73, 79, 83, 89, 97};

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

    int cnt[25];
    fill(cnt, cnt + 25, 0);
    // cnt[i] = N!を素因数分解したときのprime[i]の指数

    for (int n = 1; n <= N; ++n) {
        int m = n;

        // mを素因数分解する
        for (int i = 0; i < 25; ++i) {
            while (m % prime[i] == 0) {
                ++cnt[i];
                m /= prime[i];
            }
        }
    }

    int ans = 0;

    // p^74の形
    for (int p = 0; p < 25; ++p) {
        if (cnt[p] >= 74) ++ans;
    }

    // p^2 q^24とp^4 q^14の形
    for (int p = 0; p < 25; ++p) {
        for (int q = 0; q < 25; ++q) {
            if (p == q) continue;
            if (cnt[p] >= 4 && cnt[q] >= 14) ++ans;
            if (cnt[p] >= 2 && cnt[q] >= 24) ++ans;
        }
    }

    // p^2 q^4 r^4の形
    for (int p = 0; p < 25; ++p) {
        for (int q = 0; q < 25; ++q) {
            // 重複カウントを防ぐためにq < rにしている
            for (int r = q + 1; r < 25; ++r) {
                if (p == q || r == p) continue;
                if (cnt[p] >= 2 && cnt[q] >= 4 && cnt[r] >= 4) ++ans;
            }
        }
    }

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

数学が得意な人なら多分Cよりも簡単な一方、約数の個数の性質を知らないと詰むというとても数学寄りな問題。

感想

  • Dで最初 p^2 q^4 r^4しか頭に無かったのが情けない。
  • 全体的にABCらしい難易度だと思った。
  • 最初「AtCoderがついに問題名を誤植したか......」と思いませんでしたか?私は思いました。

CODE FESTIVAL 2018本戦 参戦記

11/17、CODE FESTIVAL 2018の本戦へ行ってきました。本記事はその体験記です。

起床〜会場入り

今年のこどふぇすは開場が8時でコンテスト開始が9時半と非常に健康的。正直寝不足でしんどかったです。

会場であるUDXに着くやいなや、ネームパスを貰って早速会場入り1。席にはこどふぇすオリジナルTシャツが掛けられていて、いよいよ本番という実感が湧いてきました2

その後続々とプロ達が入場。やはりTwitterで見かける人々が多かったです。まぁ初対面で声を掛けるコミュ力はないわけですが。

本戦

それから開会式の後、いよいよ当日のメインであるCODE FESTIVAL本戦が始まりました。

問題構成はこちらの通り。パーカーを獲得するには300点3問に加えてもう1問解き計1,400点を獲得する必要があるという、とてもハードな戦いでした。

開始後はとりあえず300点3問に専念。A, Cは実装は少しばかり重いだけで大したことはありませんでした3が、Bが曲者で確率の式は出たのにそれを評価する方法をしばらく考えあぐねていました。やがて常用対数を取ることに気づき、30分強で3問を突破。

あとはD以降を1問解けばパーカー獲得ですが、この時点でD500よりE600の方が正答者数が多いということに気づき、Eに意識を寄せつつDとEの考察を進めました。

Eは最初貪欲かと思ったが上手く行かず、DP解法を思いついたと思ったら計算量が減らせない上に誤解をしていて、結局貪欲に行き着くというなんか大回りな考察をしてしまいました。 実装もそれなりに複雑なもので、バグ取りに大分手こずりました。それでもなんとか通すことができ、残り1時間弱を残して無事パーカーを獲得することができました。

その後はなぜか正答者数がD500に並んで多かったG700を考えていましたが結局何も浮かばずタイムアップ。結果は65位というまぁ順当なでした。

ちなみに僕の順位はかなりパーカーボーダーすれすれの位置で、結局パーカーを獲得できたのは全体の4分の3程度でした。例年と比べるとかなり厳しい戦いだったようです。

昼休憩

本戦が終わるとリレーまではフリータイムとなり、

  • AI Challengeコンテストを眺める
  • ルービックキューブで遊ぶ
  • カードゲームで遊ぶ
  • りんごの挑戦状を観戦する

などなどしていました。

AI Challengeは僕も挑戦していたのですが全然強いのが作れず途中で断念。本戦進出者のAIの動きを見たり使用したアルゴリズムの話を聞いたりして、「そりゃ勝てんわ」などとなっていました。機械学習とかゲーム戦略ももう少し勉強したいですね。

りんごの挑戦状は競プロとは微塵も関係ない内容で、完全にバラエティ番組の体をなしていました。参加者の皆さんはどこでそういった知識を養ってるんですかね。

チームリレー

そして当日のサブイベント、チームリレーが始まりました。本戦の結果を元にチーム割り振りが行われたとのことで、Eチームとして戦うことになりました。

リレーと言っても形式自体はICPCのようなチームコンテストに近く、1台のPCを共有して10人で10問の問題を解いていくという感じです。ただし、

  • 同じ人が違う問題を実装してはいけない
  • 一度実装を始めたら、その人以外がその問題の実装をすることはできない
  • コーディングスペース内で他メンバーと連絡を取ることはできない

といった制約がありました。それでも、

  • 問題を見てから誰が実装するか決められる
  • 実装を中断して別の問題の人と交代する
  • 提出したコードを見てチーム全員でデバッグする

といったことはできるので、個人戦という印象はほとんどありませんでした。

戦略?

作戦会議の結果、うちのチームの戦略は以下のようになりました。

  • 10番と5番がA、9番と4番がB、...といった具合に2人1組でA~Eを考察して、終わり次第順次実装
  • 早く終わった人達からF~Jの考察に移って臨機応変

僕は7番だったのでD問題の考察&実装をすることになりました。問題としては二分探索と区間をかけ合わせたもので、細かいミスはあったものの無事通すことができました。

しかし本当に問題だったのは後半5問。上手いこと戦略が回らなかったりしたものの、なんだかんだでうちのチームはABCDEGの6完。速さが相まって全体2位を獲ることができました。全完勝負とは一体。

ちなみに上位3チームには夕食で高級和牛が提供されました。旨かったです。

感想

パーカーがゲットできたので心残りはないです。

こどふぇす全体で一番楽しかったのは、やはりチームリレーでした。自分より上の人々がどういった考察をしているのかを間近で見られる機会というのはそうそうないので、とてもいい刺激になりました。

今年初めて参加したこどふぇすでしたが、終わったときに一番強く残った感想が「来年も絶対参加したい」でした。次はもっと色々なことが楽しめるように、今から精進して腕を磨いていきたいですね。


  1. 交通費精算を飛ばしたために、おそらく全参加中で一番早い会場入りになりました。しかし後々交通費関係でちょっとした揉め事を引き起こすことに。

  2. 家で朝食を食べてきたのですが、席には朝食としてサンドイッチが用意されていました。事前に言って欲しかった……。

  3. 「大したことはない」と言っても、ARCなら400点はあるレベルだと思いたい。脱線と飛躍が小さかったということ。