エンジニアの kenkoooo です。Nintendo Switch の在庫が未だに見つかりません。

RCO x indeed 社内プロコン

RCOアドテク部には「プロコン部」というサークルがあり、各自でプログラミングコンテストに参加して、 終了後に解法を共有したり、コンテスト中に不正解となったコードをみんなでデバッグしたりしています。今回は indeed Tokyo のメンバーと一緒に社内プログラミングコンテストを開催しました。

RCO には 10 名ほどの競技プログラマーが在籍していますが、リクルート傘下の indeed にも多数の競技プログラマーが在籍しています。昨年に引き続き、今年も RCO と indeed の競技プログラマーを中心にリクルートグループの社員やインターン生の競技プログラマーが集まり、indeed 恵比寿オフィスでコンテストを行いました。

問題セット

今回は RCO の uwi さんが、自分が解いていない問題セットの中から 2017 Hackatari Codeathon というコンテストを選んでくれました。（uwi さんはとてつもない量の問題を解いているので、uwi さんが解いていない問題は誰も解いていない可能性が高いためです）

結果

members	A	B	C	D	E	F	G	H	I	total
lyyllyyl, Bobgy, sky58, kawatea	-	o	o	o	o	-	o	o	o	7
climpet, shiratty8, iehn, bya	-	o	o	o	o	-	o	o	-	6
takapt, tomerun, gahou	o	-	-	o	o	-	o	o	-	5
math, KenjiH, threepipes_s, roiti46	-	o	o	o	o	-	o	o	-	6
amylase, flowlight, kenkoooo, tubo28	-	o	-	o	o	-	o	o	-	5
Mi_Sawa, nisshy, dpforest, uwi	o	o	-	o	o	-	o	o	-	6
kcm1700, y3eadgbe, eha, cormoran	o	o	o	o	o	-	o	o	-	7

簡単 4 問 + 難しめ 3 問 + 無理 2 問 というようなセットでした。kawatea さんのチームが I 問題を通していて会場が沸きました。

C問題レビュー

今回は C 問題を担当して方針は立ったものの通すことができず、とても悲しい気持ちになったので、この場を借りて C 問題を振り返りたいと思います。

概要

問題ページ

各マスに 3 種類のうちのいずれかの模様が描かれた、縦 R マス、横 C マスのグリッドを、左上から右下まで最短経路で移動した時に通る、3 種類の模様の最小値を最大化する問題です。

これは動的計画法によって解くことができて、「今いる列」、「今いる行」、「今まで通った模様1の数」、「今まで通った模様2の数」という4つの状態を持てば良いです（「今いる列」と「今いる行」から「今まで通った模様の合計値」が計算できるため、「今まで通った模様3の数」は持たなくても復元可能です）。

ですが、それだけでは正答になりません！！！！！！！！！

R <= 100 および C <= 100という制約から、「今まで通った模様1の数」と「今まで通った模様2の数」の取りうる値の最大値は、それぞれ 199 となるため、状態の数は全部で 100 * 100 * 200 * 200 = 4 * 10^8 より 4 億通りになります。これは計算すると数秒で終わるはずですが、この問題の実行制限時間が 1 秒であることを考えると不安になります。実際、以下に示すような Java による動的計画法の実装では 1 秒では計算が終わらず、正答とはなりません。悲しい。

import java.io.PrintWriter;
import java.util.Scanner;

/*
 * このコードは実行に1秒以上かかるため、正答とはなりません
 */
public class C {

  private void solve(Scanner in, PrintWriter out) {
    int R = in.nextInt();
    int C = in.nextInt();
    char[][] maze = new char[R][];
    for (int i = 0; i < R; i++) {
      maze[i] = in.next().toCharArray();
    }

    int MAX = R + C - 1;
    boolean[][][][] dp = new boolean[R][C][MAX + 1][MAX + 1];
    if (maze[0][0] == '|') {
      dp[0][0][1][0] = true;
    } else if (maze[0][0] == '-') {
      dp[0][0][0][1] = true;
    } else {
      dp[0][0][0][0] = true;
    }

    for (int r = 0; r < R; r++) {
      for (int c = 0; c < C; c++) {
        for (int i = 0; i < MAX; i++) {
          for (int j = 0; j < MAX; j++) {
            int sum = r + c + 1;
            int k = sum - i - j;
            if (k < 0) {
              continue;
            }

            if (maze[r][c] == '|') {
              if (c > 0) {
                dp[r][c][i + 1][j] = dp[r][c - 1][i][j] || dp[r][c][i + 1][j];
              }
              if (r > 0) {
                dp[r][c][i + 1][j] = dp[r - 1][c][i][j] || dp[r][c][i + 1][j];
              }
            } else if (maze[r][c] == '-') {
              if (c > 0) {
                dp[r][c][i][j + 1] = dp[r][c - 1][i][j] || dp[r][c][i][j + 1];
              }
              if (r > 0) {
                dp[r][c][i][j + 1] = dp[r - 1][c][i][j] || dp[r][c][i][j + 1];
              }
            } else {
              if (c > 0) {
                dp[r][c][i][j] = dp[r][c - 1][i][j] || dp[r][c][i][j];
              }
              if (r > 0) {
                dp[r][c][i][j] = dp[r - 1][c][i][j] || dp[r][c][i][j];
              }
            }
          }
        }
      }
    }

    int ans = 0;
    int sum = R + C - 1;
    for (int i = 0; i < MAX; i++) {
      for (int j = 0; j < MAX; j++) {
        int k = sum - i - j;
        if (k < 0) {
          continue;
        }
        if (dp[R - 1][C - 1][i][j]) {
          int min = Math.min(i, j);
          min = Math.min(min, k);
          ans = Math.max(min, ans);
        }
      }
    }

    out.println(ans);
  }

  public static void main(String[] args) {
    PrintWriter out = new PrintWriter(System.out);
    Scanner in = new Scanner(System.in);
    new C().solve(in, out);
    in.close();
    out.close();
  }
}

通常、このように計算量が厳しい時は、簡単に復元可能な、陽にもつ必要のない状態を探し出して省略することで、計算量のオーダーを落とします。しかしながら、今回は次のような工夫をします。

• Java ではなく C++ で実装する。
• boolean の配列に対する操作が bit ベクトル同士の操作に置き換えることが可能であることに注目し、更新操作を bitset に置き換える。

これはアルゴリズム的な工夫というよりも、筋肉に頼った解決策のように感じますが、これらを適用した下記のコードは実行制限時間内に完了し、正答となります。

#include <bits/stdc++.h>
using namespace std;

bitset<200> dp[100][100][200];
int main() {
  int R, C;
  cin >> R >> C;
  vector<string> maze(R);
  for (int i = 0; i < R; i++) {
    cin >> maze[i];
  }

  int MAX = R + C - 1;

  if (maze[0][0] == '|') {
    dp[0][0][1].set(0);
  } else if (maze[0][0] == '-') {
    dp[0][0][0].set(1);
  } else {
    dp[0][0][0].set(0);
  }

  for (int r = 0; r < R; r++) {
    for (int c = 0; c < C; c++) {
      for (int i = 0; i < MAX; i++) {
        if (maze[r][c] == '|') {
          if (c > 0) {
            dp[r][c][i + 1] |= dp[r][c - 1][i];
          }
          if (r > 0) {
            dp[r][c][i + 1] |= dp[r - 1][c][i];
          }
        } else if (maze[r][c] == '-') {
          if (c > 0) {
            dp[r][c][i] |= (dp[r][c - 1][i] << 1);
          }
          if (r > 0) {
            dp[r][c][i] |= (dp[r - 1][c][i] << 1);
          }
        } else {
          if (c > 0) {
            dp[r][c][i] |= dp[r][c - 1][i];
          }
          if (r > 0) {
            dp[r][c][i] |= dp[r - 1][c][i];
          }
        }
      }
    }
  }

  int ans = 0;
  int sum = R + C - 1;
  for (int i = 0; i < MAX; i++) {
    for (int j = 0; j < MAX; j++) {
      int k = sum - i - j;
      if (k < 0) {
        continue;
      }
      if (dp[R - 1][C - 1][i][j]) {
        int min = std::min(i, j);
        min = std::min(min, k);
        ans = std::max(min, ans);
      }
    }
  }

  cout << ans << endl;
}

これは、ビット並列化による定数倍高速化ですが、これだけで数十倍速くなるので、なかなか侮れません。

寿司

問題が解けなかったとしても寿司は美味しい。

広告

RCOアドテク部では、定数倍高速化が趣味のエンジニアも募集しています。

採用ページ