蟻本2-2 / Fence Repair コード解説
競プロを始めました。
実力を上げるために、いま蟻本を読んでいる。
そこで、2-2 Fence Repairの解答コードを読んで何やってるのかわからなかった。
いろいろいじってそういうことか、という理解を得たので、そのことについてまとめようと思う。
ソース
C#で書き直してソースが以下。
static class Program
{
static bool isDebug = true;
static int[] L = new int[]{3, 5, 4, 1, 2};
static int N = L.Length;
static int ans = 0;
static void Main()
{
while(N>1){
int mii1=0, mii2=1;
if(L[mii1] > L[mii2]) swap(ref mii1, ref mii2); /*/ <= (1) /*/
for(int i=2;i<N;i++){
if(L[i] < L[mii1]){
mii2 = mii1;
mii1 = i;
}else if(L[i] < L[mii2]){
mii2 = i;
}
}
int t = L[mii1] + L[mii2];
ans += t;
if(mii1 == N - 1) swap(ref mii1, ref mii2); /*/ <= /*/
L[mii1] = t; /*/ <= (2) /*/
L[mii2] = L[N-1]; /*/ <= /*/
N--;
}
Console.WriteLine(ans);
}
static void swap(ref int l1, ref int l2){
int tmp = l1;
l1 = l2;
l2 = tmp;
}
}
疑問点
- (1)のswapって何の意味があんの？ 先頭に1番小さいのと2番目に小さいのを持ってきたいのか？ でもそのあと、1番目に小さいものと2番目に小さいものの探索ループが始まるけど
- (2)って何の意味があるの？
このコードがそもそもやりたいこと
- 配列中の1番目に小さいものと2番目に小さいものを合計(A)する
- (A)を配列に戻し、全部探索し終わるまで、もう一度1.を行う
(1)のswapって何やってるの？
直後の探索ループが正しく動作するように配列を初期化している
...
int mii1=0, mii2=1;
if(L[mii1] > L[mii2]) swap(ref mii1, ref mii2); /*/ <= (1) /*/
for(int i=2;i<N;i++){
if(L[i] < L[mii1]){ /*/ (1-1) /*/
mii2 = mii1;
mii1 = i;
}else if(L[i] < L[mii2]){ /*/ (1-2) /*/
mii2 = i;
}
}
...
やってることを自然言語で説明してみる。
まず、mii1には、配列中で一番小さい値を示すインデックス(以下「第一最小値指示子」)が入っていると 仮定 する。(A)
mii2には、配列中で二番目に小さい値を示すインデックス(以下「第二最小値指示子」)が入っていると 仮定 する。(A)
ここからループを回し、mii1, mii2 以外のすべてのインデックスについて、値を探索する。
(1-1)では、第一最小値がほんとうに第一最小値か確認している。
この条件式が真になるのは、第一最小値よりも小さい値が見つかってしまった時。
その時、第一最小値指示子を第二最小値指示子へ格下げして、新たに見つかった小さい値のインデックスを第一最小値指示子に任命する。
(1-2)では、(1-1)はクリアして第一最小値は第一最小値であることが分かったので、第二最小値が本当に第二最小値か確認している。
この条件式が真になるのは、第一最小値よりも大きいけど、第二最小値よりも小さい値が見つかってしまったとき。(B)
この時、第二最小値指示子を破棄して、新たに見つかった小さい値のインデックスを第二最小値指示子に任命する。
上記を繰り返して、本当の第一最小値指示子と、本当の第二最小値指示子を求める。
(1)のswapは、(A)での値が 仮 とはいえ、ちゃんと第一最小値 < 第二最小値を成り立たせるために行っている。
これをしないと、ループ内での処理(B)が正しく動作しなくなる。
(2)
図を描いたらわかった。
... /*/ (2-A) /*/
if(mii1 == N - 1) swap(ref mii1, ref mii2); /*/ (2-B) /*/
L[mii1] = t; /*/ (2-C) /*/
L[mii2] = L[N-1]; /*/ (2-D) /*/
N--; /*/ (2-E) /*/
図の左側が mii1 == N - 1 の場合、図の右側が mii1 != N - 1 の場合
結論
配列を効率よく利用するためのコードでした
