本稿はCodeIQで2015年3月6日～同年3月27日に出題された「ショートコーディング：きのこ危機一髪」という問題の解法に関する記事です。

ショートコーディング：きのこ危機一髪【解説1】

◆注意

本問は「ショートコーディング」・「コードゴルフ」と呼ばれる、ソースコードをできるだけ短く書く遊びの一環として出題されたものですので、一般的なプログラミング解説とは少し異なります。

◆ポイントその１…生き残る条件

先頭（1番目）のきのこが生き残る条件を考えてみましょう。たとえば、きのこ数を8とすると、最初は次のように並んでいます。

1つ飛びで消していくと、

のように、偶数番目のきのこが消え、数はちょうど半分になりました。

最初のステップ（左から1つ飛びで消していく場合）では、最初のきのこは確実に助かり、偶数番目のきのこは必ず犠牲になります。次のステップ（右から1つ飛びで消していく場合）では、「1」と「5」のきのこが犠牲になり、1番目のきのこは生き残ることができません。

今度は最初のきのこ数を10にしてみます。先程と同様に、最初のステップで偶数番目のきのこがすべて消えます。

次のステップでは、「3」と「7」のきのこが消え、「1」は助かりました。

さらに次のステップに進むと、また左からのアプローチになり、この場合は確実に助かります。

しかし次に右からのアプローチで「1」は犠牲になり、最終的に「9」が生き残りました。

なぜ「1」が生き残れなかったのかというと、それは右からのアプローチ時にきのこ数が偶数になってしまったためです。「1」は右側から見ると最後尾に位置し、きのこ数が偶数の場合には踏みつけられる対象となってしまうのです。

以上の例から「1」が残る条件をまとめると、

(1) 左からのアプローチなら必ず残る
(2) 右からのアプローチなら、残りの偶奇によって残るかどうかが決まる

ということになります。左右の区別も実際にはきのこが踏みつけられるステップの偶奇になります。したがって偶奇性を利用すればうまく計算できそうです。

◆ポイントその２…生き残ったグループの番号規則

最初、きのこの番号は1, 2, 3, …と、連続する値になっていますが、途中はどのようになっているのかを考えておきます。きのこ数を、たとえば30くらいにしてみましょう。

最初のステップで、1つ飛びで消していくと、

のようになり、各番号は2飛びの値になりました。さらに減らしていきます。

今度は4飛びになりました。これを繰り返すと、

のように8飛びになります。つまり、1ステップごとに番号と番号の間が2の累乗だけ開いていくことになります。

◆基本アルゴリズム

ここまで説明した2つのポイントを踏まえて、次のようなアルゴリズムを考えます。

while (きのこ数 > 1 ) {
  if ( 右から && きのこ数が偶数 ) 
    左端のきのこが踏まれるので、生き残るきのこは左から2番目になる
  Else
    左端のきのこは生きているのでそのまま続ける

  このステップで生き残ったきのこ数を求める
}

左から2番目のきのこ番号を求めるには、ポイントその2で説明したように、ループ回数に応じて加算する値を2倍ずつ増やしていきます。

◆サンプルプログラム

前述のアルゴリズムを用いて、実際にプログラムを書いてみます。

#include <stdio.h>

int main()
{
  int n; scanf("%d", &n);

  int a=1; // 生き残るきのこの番号
  int k=0; // 左右の区別用ループカウンタ(偶数…左・奇数…右)

  while ( n > 1 ) {
    if ( k%2==1 && n%2==0 ) a+=1<<k;
    n-=n/2; // 残りのきのこ数を求める
    ++k;
  }

  printf("%d\n", a);

  return 0;
}