Hatena::ブログ(Diary)

わさっき RSSフィード

2017年11月14日

[] aを100個,キー操作回数最小で

いきなりですが問題です.

Windowsメモ帳で,「a」を100個以上並べた文字列を作る,キー操作回数最小の操作を答えなさい.

いくつか条件を書かないといけません.中身が空のメモ帳を開いた状態から始めます.長押し(離すまでずっと「a」が出る)は使用しないこととします.Ctrl+Cなど,ショートカットキーはそれで1回とします.「Ctrl+C,Ctrl+V」は(Ctrlを押しながらCとVの順に押すとしても)2回と数えます.

コンピュータを使っている者として,素朴な発想は,“倍々”です.まず「a」と打って表示させ,次に「Ctrl+A(全指定)」「Ctrl+C(コピー)」「Ctrl+V(貼り付け)」「Ctrl+V(貼り付け)」で,表示が「aa」になります.もう一度Ctrl+A,Ctrl+C,Ctrl+V,Ctrl+Vで,「aaaa」です.繰り返せば,やがて,aが128個並んだ状態になります.wikipedia:曽呂利新左衛門の「今日は米1粒、…」と同じ考え方です.

キー操作回数は,最初の「a」で1回,倍にする1つ分で4回,そして128個にするには,倍にする操作を7回(2の7乗は128),行いますので,全部で1+4×7=29回となります.

しかしこの回数が最小値ではありません.減らすことができます.はじめに「aa」と打ってから,倍々をすれば,倍にする操作は1回減って6回ですので,全部で2+4×6=26回です.

はじめに「aaa」であれば,3+4×6=27回,「aaaa」まで打ち込むのだと,4+4×5=24回,「aaaaaaa」から倍々すれば,7+4×4=23回です.

そろそろ,プログラミングで解を求めましょう.倍の操作をする前に,aの並びを打ち込む回数をnとしたとき,n×2のm乗がs以上となるような最小のmを(nに依存して)求めます.そして,倍にする1回分の操作をcとすると,nが与えられたときのキー操作最小回数は,n+c×mとなります.あとはn=1, 2, 3, ...として,最小値を求めればよいというわけです.s=100,c=4とし,nは1から20までで計算してみると,次のとおりです

$ ruby -e 's=100;c=4;1.upto(20){|n|0.upto(s){|m|if n*2**m>=s then puts "n=#{n}, m=#{m} => #{n+c*m}"; break; end}}'
n=1, m=7 => 29
n=2, m=6 => 26
n=3, m=6 => 27
n=4, m=5 => 24
n=5, m=5 => 25
n=6, m=5 => 26
n=7, m=4 => 23
n=8, m=4 => 24
n=9, m=4 => 25
n=10, m=4 => 26
n=11, m=4 => 27
n=12, m=4 => 28
n=13, m=3 => 25
n=14, m=3 => 26
n=15, m=3 => 27
n=16, m=3 => 28
n=17, m=3 => 29
n=18, m=3 => 30
n=19, m=3 => 31
n=20, m=3 => 32

ということで,「aaaaaaa」まで打ち込んでから倍プッシュするのが,キー操作回数最小と分かりました.

aの並びを100から他の値に変えてみると,数がちょうど2のべき乗というときと,そこに1加えたときとで,最小の操作が異なってきます.たとえばs=8192,すなわち2の13乗では,n=4, m=11およびn=8, m=10の48回が最小値です.そこに1を加えてs=8193とすると,n=5, m=11とn=9, m=10の49回が最小値となります.

テキストエディタキーボードマクロ機能を使うと,また別の傾向を示します.手元のEmacsでは,F3のキーでマクロ記録開始,F4のキーで記録の終了と再生を行います.そうすると,a,F3,C-a,C-k,C-y,C-y,F4と,1+6回の操作をしておけば,倍にする操作はF4の1回で済みます.上のrubyコマンドを少し修正して,c=1で固定し,sをさまざまに変更して実行すると,n=1とn=2のときが同数かつ最小となりました.

トラックバック - http://d.hatena.ne.jp/takehikom/20171114/1510608028