概要
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秒以内
入力例
15
6 2 5 8 1 6 3 3 2 7 2 9 1 5 8
出力例
5
入力例の4文字目からの "1 6 3 3 2" が最短で長さ 5.
解答1
(1のある位置, 2のある位置, 3 のある位置) の組み合わせを一つずつ作り, それらの位置の (右端 - 左端 + 1) の一番小さい値を出力する.
入力例に対するおおまかな操作は次の通り.
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)$. コードは次の通り.
#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$ の中で最短の長さを出力する.
入力例に対するおおまかな操作は次の通り.
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節に説明されている, しゃくとり法を適用する.
入力例に対するおおまかな操作は次の通り.
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)$. コードは次の通り.
#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] に対して上を行い, 最短の部分列の長さを出力する.
入力例に対するおおまかな動作は次の通り.
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)$. コードは次の通り.
#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 さんに教えてもらった方法.
入力例に対するおおまかな動作は次の通り.
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)$. コードは次の通り.
#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.