概要

CodeIQ で出題されていたコーディング面接からの問題に対して, 4通りの解答 (C++) を考えたのに加えて, コメントで教えてもらった方法をコードにした記録です.

問題

ぎゅうぎゅうシーケンス (codeIQ, 2017年3月7日で解答は締め切られ, 今は問題を閲覧できない)

出題者の Ozy さんによると, 書籍『世界で闘うプログラミング力を鍛える本コーディング面接189問とその解法』で解説されている問題の簡略版とのことです.

入力: 正の整数からなる数列 $a_1, \ldots , a_n (n \leq 5000)$. この数列は 1, 2, 3 をそれぞれ1つ以上含むとする.

入力の書式: 1行目に数列の長さ n, 2行目に数列の値 $a_1, \ldots , a_n$.

出力: 1, 2, 3 の数字がすべて含まれる数列の部分列 $a_i,\ldots , a_j (1\leq i<j\leq n)$ の中で一番短い列の長さ ($j-i+1$).

出力の書式: 1行目に一番短い列の長さ.

実行時間: 2秒以内

入力例

input.txt

15
6 2 5 8 1 6 3 3 2 7 2 9 1 5 8

出力例

output.txt

入力例の4文字目からの "1 6 3 3 2" が最短で長さ 5.

解答1

(1のある位置, 2のある位置, 3 のある位置) の組み合わせを一つずつ作り, それらの位置の (右端 - 左端 + 1) の一番小さい値を出力する.

入力例に対するおおまかな操作は次の通り.

gyu1.txt

15
6 2 5 8 1 6 3 3 2 7 2 9 1 5 8
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 <- インデックス

1 のある位置: 4, 12
2 のある位置: 1, 8, 10
3 のある位置: 6, 7
(x, y, z): x = [1 の位置], y = [2 の位置], z = [3 の位置]. 
(4, 1, 6) 長さ 6
(4, 1, 7) 長さ 7
(4, 8, 6) 長さ 5
(4, 8, 7) 長さ 5
(4, 10, 6) 長さ 7
(4, 10, 7) 長さ 7
(12, 1, 6) 長さ 12
(12, 1, 7) 長さ 12
(12, 8, 6) 長さ 7
(12, 8, 7) 長さ 6
(12, 10, 6) 長さ 7
(12, 10, 7) 長さ 8

最短は長さ 5

計算時間は $O(n^3)$. コードは次の通り.

gyu1.cpp

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

int main(){
  int n, res = 5001;
  cin >> n;
  vector<int> w;
  vector<vector<int> > v;
  for (int i = 0; i < 4; i++) { v.push_back(w); }
  for (int i = 0; i < n; i++) {
    int m;
    cin >> m;
    if ((m == 1) || (m == 2) || (m == 3)) { v[m].push_back(i); }
  }

  for (int i1 = 0; i1 < v[1].size(); i1++) {
    for (int i2 = 0; i2 < v[2].size(); i2++) {
      for (int i3 = 0; i3 < v[3].size(); i3++) {
        int left = min(v[1][i1], min(v[2][i2], v[3][i3]));
        int right = max(v[1][i1], max(v[2][i2], v[3][i3]));
        res = min(res, right-left+1);
        if (res == 3) { printf("3\n"); return 0;}
      }
    }
  }
  cout << res << endl;

  return 0;
}

解答2

$i = 1$ とする. $i$ でない (2 のある位置, 3 のある位置) の組み合わせを 1つずつ作り, 2 と 3 の間の部分列に $i$ が含まれているもののうち, 最も短い部分列の長さを記録する.

$i = 2, 3$ についても, 同様に最も短い部分列の長さを記録する. そして, $i = 1, 2, 3$ の中で最短の長さを出力する.

入力例に対するおおまかな操作は次の通り.

gyu2.txt

15
6 2 5 8 1 6 3 3 2 7 2 9 1 5 8
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 <- インデックス

1 のある位置: 4, 12
2 のある位置: 1, 8, 10
3 のある位置: 6, 7
[2 の位置, 3 の位置] (2-1-3, 3-1-2 の順)
(1, 6) 間に 1 あり. 長さ 6.
(1, 7) 間に 1 あり. 長さ 7.
(8, 6) 間に 1 なし. 
(8, 7) 間に 1 なし. 
(10, 6) 間に 1 なし. 
(10, 7) 間に 1 なし. 
[1 の位置, 3 の位置] (1-2-3, 3-2-1 の順)
(4, 6) の間に 2 なし. 
(4, 7) の間に 2 なし. 
(12, 6) の間に 2 あり.  長さ 7.
(12, 7) の間に 2 あり. 長さ 6
[1 の位置, 2 の位置] (1-3-2, 2-3-1 の順)
(4, 1) 間に 3 なし. 
(4, 8) 間に 3 あり. 長さ 5.
(4, 10) 間に 3あり. 長さ 7.
(12, 1) 間に 3 あり. 長さ 12.
(12, 8) 間に 3 なし. 
(12, 10) 間に 3 なし. 
最短は 5.

$i=1$ のとき, 2, 3 の間に 1 があるかどうか（1 の位置を表すソートされた数列に対して, 2, 3 の位置はどこに入るか）を二分探索で求めることで, 計算時間は $O(n^2\log n)$. コードは省略.

解答3

参考文献のプログラミングコンテストチャレンジブック 3.3節に説明されている, しゃくとり法を適用する.

入力例に対するおおまかな操作は次の通り.

gyu3.txt

15
6 2 5 8 1 6 3 3 2 7 2 9 1 5 8
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 <- インデックス

(l, r): l 左端の位置, r 右端の位置
(0, 0) -> 1, 2, 3 のすべてが揃うまで, 右端を動かす
(0, 7) -> 1, 2, 3 のどれか (2) が欠けるまで, 左端を動かす
(2, 7) -> 長さ 7-2+1 = 6
--------> 1, 2, 3 のすべてが揃うまで, 右端を動かす
(2, 9) -> 1, 2, 3 のどれか (1) が欠けるまで, 左端を動かす
(5, 9) -> 長さ 9-5+1 = 5
--------> 1, 2, 3 のすべてが揃うまで, 右端を動かす
(5, 13) -> 1, 2, 3 のどれか (3) が欠けるまで, 左端を動かす
(7, 13) -> 長さ 13-7+1 = 7
---------> 1, 2, 3 のすべてが揃うまで, 右端を動かして数列の最後に到達. 
最短 5

計算時間は $O(n)$. コードは次の通り.

gyu3.cpp

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

int main(){
  int n, res = 5001;
  cin >> n;
  vector<int> v;
  for (int i = 0; i < n; i++) {
    int m;
    cin >> m;
    v.push_back(m);
  }
  int left = 0, right = 0;
  int count[4] = {0, 0, 0, 0}; 

  while (right < n) {
    bool flag = true;

    while ((count[1] == 0) || (count[2] == 0) || (count[3] == 0)) { 
      if ((v[right] >= 1) && (v[right] <= 3)) { count[v[right]] += 1; }
      right++;
      if (right > n) { flag = false; right =n; break; }
    }
    while ((count[1] >= 1) && (count[2] >= 1) && (count[3] >= 1)) {
      if ((v[left] >=1) && (v[left] <= 3)) { count[v[left]] -= 1; }
      left++;
    }
    
    if (flag) { res = min(res, right-left+1); }
  }

  cout << res << endl;

  return 0;
}

解答4

数列にある 1, 2, 3 の場所 (pos) と値 (num) を順番に配列 $v$ へ代入する.
入力からの代入をすべて終えたら, v[i] を i=0 から順番に見ていき, v[i] の値 v[i].num $\in \{1, 2, 3\}$ 以外の値 (v[i].num=1 ならば 2, 3) が v[i].pos より以前の場所に現れていることを確認する. そして, それらの場所 prev[j], prev[k] のうち, より以前に現れている場所 left=min(prev[j], prev[k]) を使って, 部分列の長さ v[i].pos - left + 1 を求める.
すべての v[i] に対して上を行い, 最短の部分列の長さを出力する.

入力例に対するおおまかな動作は次の通り.

gyu4.txt

15
6 2 5 8 1 6 3 3 2 7 2 9 1 5 8
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 <- インデックス

prev[1] = -1, prev[2] = -1, prev[3] = -1.
i=1 -> prev[2] = 1
i=4 -> prev[1] = 4
i=6 -> prev[3] = 6. 長さ 6-1+1 = 6.
i=7 -> prev[3] = 7. 長さ 7-1+1 = 7
i=8 -> prev[2] = 8. 長さ 8-4+1 = 5
i=10 -> prev[2] = 10. 長さ 10-4+1 = 7
i=12 -> prev[1] = 12. 長さ 12-7+1 = 6
最短 5

計算時間は $O(n)$. コードは次の通り.

gyu4.cpp

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

struct numpos {
  int num, pos;
};

int main(){
  int n, res = 5001;
  cin >> n;

  vector<numpos> v;
  for (int i = 0; i < n; i++) {
    int m;
    cin >> m;
    if ((m == 1) || (m == 2) || (m == 3)) {
      numpos np; np.num = m; np.pos = i;
      v.push_back(np);
    }
  }

  int s = v.size();
  int prev[4] = {-1, -1, -1, -1}; 
  for (int i = 0; i < s; i++) {
    bool flag = true;
    int left = 5001;
    for (int j = 1; j <= 3; j++) {
      if ((prev[j] == -1) && (v[i].num != j)) { flag = false; }
      if ((prev[j] != -1) && (v[i].num != j)) { left = min(left, prev[j]); }
    }
    if ((flag) && (res > (v[i].pos - left + 1))) { res = v[i].pos - left + 1; }
    prev[v[i].num] = v[i].pos;
  }

  cout << res << endl;

  return 0;
}

解答A （追記）

コメントで kota9 さんに教えてもらった方法.

入力例に対するおおまかな動作は次の通り.

gyu-kota9.txt

15
6 2 5 8 1 6 3 3 2 7 2 9 1 5 8
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 <- インデックス

[前処理]
(i, num) = (12, 1)
next[12][1] = 10000, next[12][2] = 10000, next[12][3] = 10000, numpos[1] = 12
(i, num) = (10, 2)
next[10][1] = 12, next[10][2] = 10000, next[10][3] = 10000, numpos[2] = 10
(i, num) = (8,  2)
next[8][1] = 12, next[8][2] = 10, next[8][3] = 10000, numpos[2] = 8
(i, num) = (7, 3)
next[7][1] = 12, next[7][2] = 8, next[7][3] = 10000, numpos[3] = 7
(i, num) = (6, 3)
next[6][1] = 12, next[6][2] = 8, next[6][3] = 7, numpos[3] = 6
(i, num) = (4, 1)
next[4][1] = 12, next[4][2] = 8, next[4][3] = 6, numpos[1] = 4
(i, num) = (1, 2)
next[1][1] = 4, next[1][2] = 8, next[1][3] = 6, numpos[2] = 1
[本処理]
(i, num) = (1, 2)
right = min(next[next[1][1]][3], next[next[1][3]][1])
      = min(next[4][3], next[6][1]) = 6. 長さ 6-1+1 = 6.
(i, num) = (4, 1)
right = min(next[next[4][2]][3], next[next[4][3]][2])
      = min(next[8][3], next[6][2]) = 8 長さ 8-4+1 = 5.
(i, num) = (6, 3)
right = min(next[next[6][1]][2], next[next[6][2]][1])
      = min(next[12][2], next[8][1]) = 12. 長さ 12-6+1 = 7.
(i, num) = (7, 3)
right = min(next[next[7][1]][2], next[next[7][2]][1])
      = min(next[12][2], next[8][1]) = 12. 長さ 12-7+1 = 6.
(i, num) = (8, 2)
right = min(next[next[8][1]][3], next[next[8][3]][1])
      = min(next[12][3], next[10000][1]) = 10000
最短　5

計算時間は $O(n)$. コードは次の通り.

gyu-kota9.cpp

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

struct numpos {
  int num, pos;
};

int main(){
  int n, res = 10000;
  int next[10001][4];
  for (int i = 1; i <= 3; i++) { next[10000][i] = 10000; }
  cin >> n;
  vector<numpos> v;
  for (int i = 0; i < n; i++) {
    int m;
    cin >> m;
    numpos a; a.num = m; a.pos = i;
    v.push_back(a);
  }

  int numpos[4] = {10000, 10000, 10000, 10000};
  for (int i = n-1; i >= 0; i--) {
    int num = v[i].num;
    if ((num == 1) || (num == 2) || (num == 3)) {
      for (int j = 1; j <= 3; j++) { next[i][j] = numpos[j]; }
      numpos[v[i].num] = v[i].pos;
    }
  }

  int nextnum[4][2] = {{-1, -1}, {2, 3}, {1, 3}, {1, 2}};
  for (int i = 0; i < n; i++) {
    int num = v[i].num;
    if ((num == 1) || (num == 2) || (num == 3)) {
      int next2[2];
      for (int j = 0; j < 2; j++) { next2[j] = nextnum[num][j]; }
      int right = min(next[(next[i][next2[0]])][next2[1]],
		      next[(next[i][next2[1]])][next2[0]]);
      res = min(res, right - i + 1);
    }
  }

  cout << res << endl;

  return 0;
}

解答へのたどり着き方

問題を見たとき, 参考文献に書いてあったしゃくとり法を思い出して, 解答3 のコードをまず書きました.

その後, 出題者の解答までの想定時間が 20分だったにもかかわらず, 解答 3 のコードを書き終えたのは, 眠って一晩明けてからでした. そこで, 想定時間内でもコードを書ける（であろう）単純な方法として, 解答1 のコードを書きました.

しかし問題では $n\leq 5000$ に設定されているため, 解答1 では $n^3$ が大きいときには $10^{11}$ ほどになります. これでは2秒の制限時間で終わらないかもしれません. そこで, 計算時間を抑えるための方法として, 解答2 の考えにたどり着きました.

最後に, このまとめを書いているときに, 解答4 の方法でも答えが出せそうだったので, 解答4 のコードを書きました.

ということで残念ながら, いずれの方法も想定時間内で解答できませんでした.

参考文献

プログラミングコンテストチャレンジブック. 秋葉拓哉, 岩田陽一, 北川宜稔. 毎日コミュニケーションズ. 2010.