だから僕はプログラミングが出来ない

競プロ・アルゴリズムに関するお話。

TL;DR

こんな問題に出会った。

< Double Cola >

https://www.codewars.com/kata/double-cola/

(概要)

自動販売機に人が並んでいる。その並んだ人の名前をあらわすための配列が渡される。

たとえば["A", "B", "C"]みたく、配列には、列に並ぶ人間たちの名前がString型で定義されている。

並んだ人は、自動販売機でジュースを買ったあと、もう一度並びなおして、そして並び直したさいに「2倍に増殖する」。まるでドラえもんバイバインのように。

つまり、最初に並んでた人がみんな買い終わったときの配列は、["A", "A", "B", "B", "C", "C"]。

FIFOのキューみたく、左から順に配列は処理されていく。

以上の条件で、要素としてStringを複数もつ配列aと、整数nが与えられたとき、n番目にジュースを買う人間は、いったい配列aの中のどのStringになるのか出力せよ、というもの。

僕の考え方(きっとよくない例)

なるほど…。こういうのは、だいたい具体的な例から考えるとわかりやすいんだよな。

たとえば、列に5人並んでるとする。
わかりやすく、名前はa = ["一郎", "二郎", "三郎", "四郎", "五郎"]としよう。

最初に買う順番は単純で、前から1, 2, 3, 4, 5って数えていけばいいな。
たとえばn=1だったら、"一郎"。n=4だったら"四郎"だ。

問題は2周目以降だ。
次は["一郎", "一郎", "二郎", "二郎" ... ]みたく、みんな増殖してる。

n番目だけに着目すると、[6, 7]番目は"一郎"、[8, 9]番目は"二郎", 
[10, 11]番目は.. ,[12, 13].., [14, 15]..みたいな感じか
このとき、たとえばn=10のとき"三郎"、n=15のとき"五郎"になる。

その次は[16, 17, 18, 19] ...(略)... [32, 33, 34, 35]。
さらに倍増してるけど、まだそのまま計算できる範囲。

その次は[36...43] ...(略)... [68...75]。
n=36なら答えが"一郎"ってのはわかる。ただ、もうこのあたりから単純計算だと難しいな。
さて…どう処理していこうか。

ん?よく見れば、倍増する前に全員を処理することを1週と考えたとき、
各周の最後の数字だけに着目すると、数列になってないか?

1週目の最後は5。
2週目の最後は15
3週目の最後は35
4週目の最後は75。

おお、10, 20, 40と増えていく数列だ!

こういう増え方はなんて言うんだっけ?

(3分ほどググって…)

そうそう、等比数列の和ね、うん。久しぶりに見た。

ということは、与えられたnが何周目に位置しているかは、この等比数列の和と組み合わせて考えれば解けそうだぞ。

(ここから30分ほど色々ググって…)

よし、与えられたnが何周目に位置するかを表す数式が書けた。(lapsが何周目になるか表す)

laps = (Math.log2(((n-1) / 5.0) + 1)).floor + 1

たとえば、n=43と入れてみると、lapsは4で、そのnは4週目に位置すると求められる。

これさえわかれば、たとえばn=123017423みたいな巨大な数字が与えられても、
それが何周目に位置するかわかって、そこからは何とか計算できそうだぞ!

ん……? でも、たとえば与えられたnが124週目にあるとわかっても、
そこからそのnが「123週目の終わりと125週目のはじめを基準として、
それを5分割したうちのどの部分に位置するか」を求めないと、
「"一郎"か"二郎"かそれとも…」っていうふうに導き出すことはできないのか。

しかも、よく考えれば、今回は aの配列の要素数は5とも限らない。配列の要素数に応じて、処理を変えるように式を書き換えないとな…。

よし、じゃあもう一度最初から見直して、書き直していくか!

これがこの問題に直面したときの僕の思考でした。

このあと、案の定、ぶじ面倒になって答えを見ました。

そして圧倒的回答(一例)

def whoIsNext(names, r)
  r -= 1
  while r >= names.size
    r -= names.size
    r /= 2
  end
  names[r]
end

圧倒的短さ

しばらく考えてコードの意味を理解したとき、自分がいかにプログラミングのための思考法になってないか気づきました。

これ、単純に言うと、与えられた条件の処理を、逆向きにループしていく処理なんですよね。

「数列を探して〜」とか、「nが何周目に位置するから〜」とか、高校数学のときに考えるような、「xを求めるための式をまず探して、そして左辺がx=になるように分解していく」ようなアプローチは全くしていない。

ただアルゴリズムを探して、そしてそのアルゴリズム通りに動くプログラムを書いているだけ。

い、今まで人生でアルゴリズムを探したことなんてなかったし

そして、僕は自分が(競技)プログラミングが出来ないわけがわかりました。

アルゴリズムの勉強もしてない、アルゴリズムに対する知識量も足りない、そして、そもそもアルゴリズムを探すというアプローチさえ出来ていない。

ああ…。

そりゃできるわけねーわ。

自分が、いかにプログラミングに適応した思考法になっていないか、この問題で痛感しました。

とはいえ、アルゴリズム以外にも勉強することはある

とはいっても、他にも勉強することは山程あるわけで、アルゴリズムだけに時間を投資することは無理なんですけど。

複雑な問題を、アルゴリズムを使って効率的に解くってのはかっこいいし、「データ処理の基本」であると思うので、これからもしっかりやっていかないとな、と、そう思ったわけであります。

そんな気持ちでこのブログを書き始めたんですが、特に落ちがないのでゆるキャンをはりつけて終わっておきます。

alu.jp

よーし、プログラミングがんばるぞーっ。

おわり。