Manateeではメルマガ会員を募集中！

競技プログラミングの楽しさについて

前回は“競技プログラミングがいかに役に立つか”について書きましたが、今回は競技プログラミングの楽しさについて書きたいと思います！

「楽しい」とは書きましたが、凄く正直に書いてしまえば競技プログラミングは万人向けの娯楽だとは言い難いです。もし競技プログラミングより普通にゲームやWebサービスを作っていた方が楽しい！ というのであれば、おそらくそちらをした方が良いのではないかと思います。

競技プログラミングの楽しさには色々とあります。その中でも僕が一番知ってほしい楽しさは“問題の解き方を思いついた時の楽しさ”です。その爽快感を感じられる人なら、競技プログラミングをかなり楽しめるのではないかと思います。そこで今回は爽快感をよく感じられる問題を例として取り上げたいと思います。

問題

制約

［引用コンテスト］

• AtCoder Grand Contest 004 [C - AND Grid]

 

解説

問題を見てもあまり意味がわからないと思うので、ざっくりと図で説明します。

例えば、以下のような入力が与えられたとします。

5 5
.....
.#.#.
.....
.#.#.
.....

それに対し、貴方が出力するべきものは例えば以下のようなものです。

.....
#####
#....
#####
.....

.###.
.#.#.
.#.#.
.#.#.
.....

これは、どういうものか、というと、図で説明するとこのような感じになります。

入力で赤と青の重なっている部分が与えられるので、それを実現可能な赤・青の例を1つ作ってください、という問題です。

与えられる入力の制約としては、一番端の行・列には#が与えられないこと。出力の制約として、赤・青がひとつながりになっていること、があります。

さてこの問題ですが、どうやったら解けるでしょうか？

難しい入力を想像してみましょう。例えばこんなものもあります。

人間の手で考えながら頑張って構築すれば、こうして上手く赤マス・青マスを作れるかもしれません。ですが、コンピュータにこれを解かせようとすると、一定のルールで解かせないといけません。

さて、この問題を確実に解けるような方法はあるのでしょうか？少し考えてみてから、この下の解答編を見てみてください。

解答

実はこの問題は、次の方法を使うとひどくあっさりと解けてしまいます。まずは以下のような赤と青のマスの塗り方をします。

こうした後に重なった部分の色を変えてしまえば、どんな入力が与えられても解くことができます。

このように、最悪のパターンでどんな入力が与えられるかや、そういった場合でもうまくプログラムを実行させるためにはどのような工夫が必要か、みたいなことを考えると、こうした問題を解くことができます。

コードは以下のようになりますが、初心者の人はまだコードの内容を気にする必要はありません。 AtCoder Beginner Contestなどに出ている人は、まずは基本的な書き方を覚えるところからなので、こうした難しい問題のコードはひとまず見なくても大丈夫です。とはいえ、意外と長くないコードで先ほどの問題が解けてしまうことがわかるのではないかと思います。

#include<iostream>
#include<string>
#include<vector>
using namespace std;

int main() {
    int H, W; // たて、よこ
    cin >> H >> W;
    vector<string> a; // 入力
    for (int i = 0; i < H; i++)
    {
        string s;
        cin >> s;
        a.push_back(s);
    }

    vector<vector<int>> board(H, vector<int>(W));
    for (int i = 0; i < H; i++)
    {
        for (int j = 0; j < W; j++)
        {
            // 1が赤のみ、2が青のみ、3が赤青両方
            if (a[i][j] == '#') board[i][j] = 3;    // #なら無条件で両方
            else if (j == 0) board[i][j] = 1;       // 左端なら赤
            else if (j == W - 1) board[i][j] = 2;   // 右端なら青
            else board[i][j] = (i % 2) + 1;         // それ以外は偶奇で分ける
        }
    }

    for (int k = 1; k <= 2; k++) // 赤青両方について出力する
    {
        for (int i = 0; i < H; i++)
        {
            for (int j = 0; j < W; j++)
            {
                // 赤=1、青=2でand演算し、配置するべきか判定
                if (board[i][j] & k) cout << '#';
                else cout << '.';   
            }
            cout << endl;
        }
        if (k == 1) cout << endl; // 最初だけ改行する
    }
    return 0;
}

おわりに

さて、今回の連載は、どうでしたでしょうか？ 「プログラミングなんて関係ないじゃないか」と思った人もいるかもしれません。

そうです。今回の問題はプログラミングというよりはパズルのようなもので、コードが書けるかどうかというのはあまり関係がありません。初心者の方にはまだまだ難しいかもしれませんが、プログラミングに慣れた方なら、解き方を聞けばあっさりとコーディングできてしまうかと思います。 AtCoder上位の人なら、解法を聞いてからのコーディング時間は、おおよそ“2分～3分程度”ではないかと思います。

競技プログラミングにはさまざまな問題がありますが、こうしたアイデアが一番大切です。コーディング力が問われないような問題もありますし、逆にどれだけ正確に実装できるかを競うようなコーディング力が非常に問われる問題もあります。 こうした思い付きが楽しい、と感じられる人は、ぜひ競技プログラミングをはじめてみることをおすすめします。

次回からは、競技プログラミングで強くなるために必要なことを少しずつ解説していきたいと思います。お楽しみに！

Manateeではメルマガ会員を募集中！