Mister雑記

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

Mujinコン2018 解説 前編(A-C)

お久しぶりです、試験が終わり夏休み真っ盛りのMisterです。

今回はMUJINさん主催の企業コン。Unratedでしたが、100位以内で貰えるTシャツを狙って参加しました。

解説はA-Eの5問を解説しますが、長くなりそうなので記事はABCの前編とDEの後編に分けます。

目次

A. コンテスト名

概要

文字列 Sの頭5文字がMUJINか否か判定せよ。

制約

  •  1 \leq |S| \leq 10

解説

比べるだけなのだが、C++では主に以下の2つの実装が考えられる。

解答例1: 1文字ずつ比較

#include<iostream>
#include<string>

using namespace std;

int main() {
    string S;
    cin >> S;
    
    string mujin = "MUJIN"; // 比較対象
    
    // 文字数条件: |S| >= 5
    if (S.size() < 5) {
        cout << "No" << endl;
        return 0;
    }
    
    for (int i = 0; i < 5; i++) {
        if (S[i] != mujin[i]) {
            // 違ったら即アウト
            cout << "No" << endl;
            return 0;
        }
    }
    
    cout << "Yes" << endl;
    return 0;
}

1つ目が上のように1文字ずつ比較していって、途中で違う文字が出たら即終了というもの。

この実装における最大の注意点は、12行目に出てくる文字数条件である。これのチェックを怠ると、後に比較するときに範囲外参照を起こしてREとなることがある。この範囲外参照が起こるケースはサンプルにも入っていないので要注意。

解答例2: substr

#include<iostream>
#include<string>

using namespace std;

int main() {
    string S;
    cin >> S;
    
    if (S.substr(0, 5) == "MUJIN") {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}

2つ目はstringのsubstrというメンバ関数を使う方法。substrは

S.substr(1文字目の位置, 文字数)

という具合に引数を渡して使う1

この方法はforループが不要な上、文字数比較をしなくていいのが良い。というのも文字数だけ切り抜こうとするとSをオーバーしてしまう場合、勝手に「末尾まで」と解釈し直してくれる仕様だからだ。正直コンテストが終わるまで知らなかった。

おまけ: Pythonでの解答例

print("Yes" if input()[0:5] == "MUJIN" else "No")

スライス記法で楽に切り取れるので、上のように1行で書ける。

B. セキュリティ

概要

整数 A+-のみからなる文字列 Sが与えられる。

 Sを頭から見ていって、+なら Aが1増えて-なら1減る。

このとき、途中で Aが0になることがあるか判定せよ。

制約

  •  0 \leq A \leq 100
  •  1 \leq |S| \leq 100
  •  A = 0の状態で-が来ることはない。

解説

実際にシミュレートすればいい。

解答例

#include <iostream>
#include <string>

using namespace std;

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

    // コーナーケース
    if (A == 0) {
        cout << "Yes" << endl;
        return 0;
    }
    
    // 範囲for文で順番に見ていく
    for (char c : S) {
        if (c == '+') {
            A++;
        } else {
            A--;
        }
        
        if (A == 0) {
            cout << "Yes" << endl;
            return 0;
        }
    }

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

この問題でも注意点が1つ、それが「最初から A=0であるケース」だ。AtCoderは慈悲深いのでサンプルでそのケースを挙げてくれているが、Codeforcesではこういったコーナーケースが原因でHack祭りがしばしば催される。

あと範囲for文に関しては過去の記事で簡単に取り上げたので、初見の方はそちらを参照していただきたい。

C. 右折

概要

所々壁になっている N \times Mの盤面が与えられる。

このとき、始点から1マス以上直進して中継点で右に90度ターンし、また1マス以上直進して終点へ着く、という経路が存在する始点と終点の組は全部で何通り考えられるか。

制約

  •  2 \leq N, M \leq 2 \times 10^3
  •  s_{ij}はマス (i, j)が壁なら#、何もないなら.

解説

超簡単に言えば、「#を通らないL字は盤面上にいくつあるか?」ということである。

ここで注目すべきは、始点でも終点でもなく中継点である2

f:id:misteer:20180805172214p:plain

上のように、「中継点」と「方向」さえ決めれば突き当たりまでのマス数の積で全経路の総数が求められる。

というのも、赤矢印が通るマスと青矢印の通るマスからそれぞれ1つずつ始点、終点を選べば経路が作れるからだ。赤紫の経路は赤の1マス目と青の2マス目を選んだ場合のものである。

中継点ごとの総経路数を求めてみよう。上下左右に突き当たりまでのマス数をそれぞれ U, D, L, Rとすると、そのマスを中継点とする経路の総数は 
UL + LD + DR + RU = (U + D)(L + R)
で求められる。

後は各マスについて U, D, L, Rを求めればいいのだが、これが地味に難しい。

様々な方法があるが、私は以下のように再帰的に求めることにした。この辺は実装力が問われるところ。

f:id:misteer:20180805171522p:plain

解答例

#include <iostream>
#include <string>
#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++)

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

const ll dx[4] = {0, -1, 0, 1};
const ll dy[4] = {-1, 0, 1, 0};
const ll MAX = 2018;

ll N, M;
V<string> S(MAX);
V<V<V<ll>>> dp(MAX, V<V<ll>>(MAX, V<ll>(4, -1)));
// dp[x][y][i] = (x, y)中心で(dx[i], dy[i])方向の
//               突き当たりまでのマス数
// (x, y)が未探索or壁なら-1

// (x, y)を始点として、方向(dx[i], dy[i])に突き進む
ll rec(ll x, ll y, ll i) {

    // 再探索防止
    if (dp[x][y][i] >= 0) return dp[x][y][i];

    // 1つ進んだマス(nx, ny)を探索
    ll nx = x + dx[i];
    ll ny = y + dy[i];
    
    if (nx < 0 || nx >= N || ny < 0 || ny >= M || S[nx][ny] != '.') {
        // (nx, ny)は突き当たりなのでマス数は0
        dp[x][y][i] = 0;
    } else {
        // 探索続行
        dp[x][y][i] = rec(nx, ny, i) + 1;
    }

    return dp[x][y][i];
}


int main() {
    // 初期化
    cin >> N >> M;
    FOR(i, 0, N - 1) {
        cin >> S[i];
    }

    // 方向(dx[i], dy[i])、中継点(x, y)
    FOR(i, 0, 3) {
        FOR(x, 0, N - 1) {
            FOR(y, 0, M - 1) {
                if (S[x][y] == '.') {
                    // (x, y)を起点にdpテーブルを埋める
                    rec(x, y, i);
                }
            }
        }
    }

    // 探索結果を集計
    ll ans = 0;
    FOR(x, 0, N - 1) {
        FOR(y, 0, M - 1) {
            if (S[x][y] == '.') {
                // (U + D) * (L + R)を加算
                ans += (dp[x][y][0] + dp[x][y][2]) * (dp[x][y][1] + dp[x][y][3]);
            }
        }
    }

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

実装が重く、かつ発想も簡単ではない。ARCなら余裕で500点相当だろう。

他にも「端からカウントを増やしていって壁で0にリセットする」という方法なら再帰を使わずにdpテーブルを埋められる。 もっと大胆な方法として、盤面の方を90度回転させてもいい。

計算量は O(NM)、4方向の定数倍も考慮すると最悪で 10^7程度になるのでC++でも結構怖いレベル。上のコードは1021msで思ったより危なかった。Pythonで通すのは至難の業だろう。


  1. ちなみに第2引数を省略すると文字列の末尾まで抜き取ってくれる。

  2. 私が本番でこの発想にすぐ至れたのは、CSAで類題を解いたことがあるためである。