ProjectEuler Problem 191

Problem 191 - Project Euler 問題のページ
Problem 191 - PukiWiki 日本語訳

三進数を作り出してチェックする、ってのはちょっと遅いような気がしたので、ううむ、と考えてみると、

• L (late, 遅刻) は、文字列中に最大1回しか出てこない

ということに気がついた。

ということで、

• O (on time, 出席) をゼロで表し、 A (absent, 欠席) をイチで表す二進数を考えて
• 三つ連続するイチが含まれていない文字列を見つけ次第、そいつをカウントする。
• あとから、O (on time, 出席) のゼロを一個だけ L (late, 遅刻) に書き換える。

という方針でやってみたら、うまくいった。

OAOA (二進表記: 0101) の場合、まずそれを「賞を貰える文字列」のひとつとしてカウントした上で、LAOA と OALA の二つもカウントする。つまり、二進表記のゼロの数を数えてやる。

O (on time, 出席) ではなく、A (absent, 欠席) も L (late, 遅刻) に書き換える方法だと、二重にカウントしちゃってよろしくない。

O (on time, 出席) ではなく、A (absent, 欠席) を L (late, 遅刻) に書き換える方法だと、三つ連続した A を見つけて除外するという作業の前にそれをやらなくてはならないので、うまくない。AAA は除外だけど、ALA は除外されるべきじゃないので、L への書き換えで「三連続欠席」を分断しちゃうし。

30bit の数をカウントしていくときに、早くまわす方法は、0011100000 0000000000 0000000000 というような三つ連続したイチを見つけた時点で、その三連続１の最後の位にイチを足してやること。そこに1が三つ並んでるってことは、それより下位がどういう並びであっても興味ないからね。

  0011100000 0000000000 0000000000
+ 0000100000 0000000000 0000000000

  0100000000 0000000000 0000000000