色々な問題の解答(CodeIQ)
はじめに
CodeIQというところでプログラミング問題に挑戦しましたので、ネタバレです。
最近、鍋谷さんの問題が色々一斉に締め切りを迎えましたので、まとめて紹介です。
問題一覧
ボタンを押して数を作ろう
次のような問題でした。
- 1 から始めて、+1 あるいは ×2 を何回か( 組み合わせて良い ) 行って目的の数 ( 標準入力から入力される ) を作る時の最短手順は何手かを出力する。
これは、「目的の数を2進数で表した時の、先頭の1の桁を除いた、1の桁の数の2倍と、0の桁の数の和」で計算できますから、次のように短いコードで済みます。Ruby(40)とPerl(38)です。
p gets.to_i.to_s(2).gsub(?1,"00").size-2
$y+=$x%2+1,$x>>=1while$x+=<>;print$y-2
くねくね最短経路
次のような問題でした。
- 通れない箇所がある6×6のマス目をスタートからゴールまで、「2手連続で同じ方向に移動しない」という条件で進むときの最短の手順を出力する。ゴールにたどり着けない場合は“X”を出力する。
- マス目の状況は、各行のマスを s,g,_,x ( それぞれスタート、ゴール、通れるマス、通れないマス ) 6文字でエンコードした文字列6組をスラッシュ区切りでつないだ文字列として入力される。
例えば s_____/______/__X___/___X__/______/_____gという入力であれば、次のようなマス目の状況で、緑の線をたどるように動くことで最短の14手が実現できます。
で、次のようなPerlのコードを提出しました。
use strict;
use warnings;
no warnings qw(uninitialized);
use feature qw(say);
sub prepare_map;
sub resolve;
say resolve(prepare_map(<>,6))//'X';
sub prepare_map
{
# input string and map width
my ($in,$w)=@_;
my @m;
my %p;
while ( $in=~/[^X\W]/g )
{
my $i=$-[0]+$w+1;
$m[$i]=1;
$p{$&}=$i;
}
return ($w,@p{qw(s g)},@m);
}
sub resolve
{
# map width, start/goal position, map data
my ($w,$s,$g,@m)=@_;
die unless defined $s && defined $g;
my @distance=(-$w-1,1,$w+1,-1);
# work array to save (position,direction)->(min step)
my @w;
# initial step 0 for all directions at the start
$w[$s]=[(0)x4];
# queue for the next position
my @q=map[$s,0,$_],0..3;
while ( @q )
{
# previous position/step, direction
my ($p,$n,$d)=@{shift @q};
$p+=$distance[$d];
next unless $m[$p];
$n++;
# when reach the goal
return $n if $p==$g;
my $r=$w[$p]//=[];
for my $i ( 0..3 )
{
next if $i==$d || defined $r->[$i];
$r->[$i]=$n;
push @q,[$p,$n,$i];
}
}
return undef;
}
まあ、解き方としては普通にBFSなんですが、「2手同じ方向には進めない」ということで、単純に「マス目毎に最小距離を記録していく」とするのでは対処できません。そのため、マス目毎に、4方向それぞれでの最小距離を考えます。
例えばですが、「3手で(2,2)のマスに辿りつき、次に右に行ける」という状況を「(2,2,右)→3」として記録しておき、そこから更に1手進めて右に行く次は右以外の方向に進めるので、(2,3,上)→4, (2,3,下)→4, (2,3,左)→4 と、右移動以外の3組を記録する、といった具合にです。( 勿論、最短手順を管理するため、既に手数が記録されている場合はスキップします )
なお、実装上の工夫と言うかデータの持ち方としては、
- 地図を1次元化して考える
- 行同士が続きと判断されないよう、間にガード領域(Xと同等)を挟む ( 1行7マス相当 )
- 2次元的な上-右-下-左の移動を、1次元的な-7,+1,+7,-7の移動として処理する
- 地図の端の処理を簡略化するため、地図の上下に仮想的なガード行 ( Xのみからなる行 ) 領域を設ける
ということをしています。
最寄りの素数
次のような問題でした。
- 次のように自然数が ( 無限に ) 配置されたマス目において、入力で与えられる自然数 ( 非素数 ) のマスから最も近いマスにある素数を出力する。複数ある場合はカンマ区切りで出力する。
- なお、マス同士の距離は、マスの中心同士の直線距離とする。例えば、6→7のように隣接のマスは距離1、6→13のようにケイマの位置にあるマスは距離√5となる。
次のRubyのコードを提出しました。
require 'prime'
def sq_decompose(n)
c=1
while n%4==0
c*=2
n/=4
end
return [] if n%4==3
t=[]
e=false
if n.even?
e=true
n/=2
end
s,g=0,Math.sqrt(n).floor
while s<g
sum=s**2+g**2
if sum==n
t<<[s,g]
s+=2;g-=1
elsif sum<n
s+=1
else
g-=1
end
end
if e
t.each do |r|
r[0],r[1]=c*(r[1]-r[0]),c*(r[1]+r[0])
end
elsif c>1
t.each do |r|
r[0],r[1]=c*r[0],c*r[1]
end
end
t
end
def getpos(n)
r=Math.sqrt(n).ceil
n+r>r*r ? [r**2-n+1,r] : [r,n-(r-1)**2]
end
def getnum(x,y)
x<1||y<1 ? 1 : x>y ? (x-1)**2+y : y**2-x+1
end
def solve(n)
x,y=getpos(n)
d2=1
loop do
t=sq_decompose(d2).map{|r|
s,g=*r
(
s==0 ?
[[g,0],[0,g],[-g,0],[0,-g]]
: s==g ?
[[s,s],[-s,s],[-s,-s],[s,-s]]
:
[[g,s],[s,g],[-s,g],[-g,s],[-g,-s],[-s,-g],[s,-g],[g,-s]]
).map{|r|
getnum(x+r[0],y+r[1])
}.select(&:prime?)
}.flatten
return t.sort if t.size>0
d2+=1
end
end
puts solve(gets.to_i)*?,
何と言うか、あまり気の利いた方法を思い浮かばなかったので、地道に地道に。
入力の数のマスがどこにあるか位置を割り出し、そこから少しずつ距離を増やしていって、等距離にあるマスの中で素数が含まれるかどうかを見ていく戦略です。
距離をそのまま考えるとルートが出てきてしまいますから、「距離の2乗」を考え、これを1からインクリメントしていきます。
で、例えば「距離の2乗=5」という状況だと、マスの位置が(左右5マス,上下0マス),(左右2マス,上下1マス)離れたものが ( 更に左右と上下を入れ替えたものも ) 全て当てはまるわけですが、これらの組み合わせを割り出すために sq_decompose を定義しています。…処理時間短縮のためか、2のべきで割った数で計算してるんですが、今見返すとやや中途半端な気もしますね。本気で短縮するなら素因数分解していく所です。
1の並びで小さい方から
次のような問題でした。
- カンマ区切りで入力される2数 X,Y ( 自然数 ) に対して、以下で定義される F(n) の値が X に等しくなる自然数 n の中で、Y番目に小さいものを出力する。
- F(n) は、「n を2進数表記した時の、連続する1の桁の長さの最大値」と定義する。
※例えば 55=110111(2) で、連続する1の桁数が2の部分と3の部分がありますが、最大値は3になるので、F(55)=3
以下のRubyのコードを提出しました。
eval"X,Y="+gets
# k-bonacci用メモ領域
m=[1]*4
# 2通りのk-bonacciの項を返す関数 ( i=0,1 に応じて (X+i)-bonacci )
k=->d,i=1{d<0?0:m[d*2+i]||=2*k[d-=1,i]-k[d-X-i,i]}
# 2進d桁以下で、X桁連続する1を持つ ( X桁より多くは連続しない ) 数の個数
s=->d{k[d]-k[d,0]}
# y番目の数を返す関数
# 探索範囲の2進桁数上限をdで与える
# i=0 はX桁連続する1を持つもの ( X桁より多くは連続しない )
# i=1 は連続する1が高々X桁であるもの
f=->y,i=0,d=(1.5*Math.log2(y)).ceil+X+1{
d>X ?
0.upto(X){|j|
# X==j の場合は無条件に i=1 に切り替える
v=[s,k][i|=j/X][t=d-j-1]
# 上位桁を確定して縮小した問題を再帰的に解く
y>v or break f[y,i,t]+(2**j-1<<t)
y-=v
}
: y-1
}
p f[Y]
2進で連続する1の桁数が高々Xである数の個数は、桁数の上限を項数とするk-bonacci (X+1-bonacci ) で表すことができます。
以下では例として X=3 に対する個数 k(d) を考え、これが 4-bonacci になっていることを示します。
例えば、高々7桁の数 ( なお 0 は 0桁の数と見做します。以下同様 ) は次のように分類できます。ここで、a…a の部分も「連続する1の桁数が高々X」です。
- 0aaaaaa … k(7-1)個
- 10aaaaa … k(7-2)個
- 110aaaa … k(7-3)個
- 1110aaa … k(7-4)個
そのため、k(7)=k(6)+k(5)+k(4)+k(3) です。同じように考えると、一般の d に対して
- k(d)=k(d-1)+k(d-2)+k(d-3)+k(d-4)
という条件が導かれます。これは 4-bonacci数列の漸化式に他なりません。
そうすると、連続する1の桁数の最大値が丁度Xである個数に関しては、2種類のk-bonacci ( X+1-bonacci,X-bonacci ) の差となることが分かります。( 以下 s(d)で表します )
では改めて、数の桁数の上限を決めた場合の「連続する1の桁数の最大値が丁度Xとなる数」を小さい順に分類すると次のようになります。これは先ほどと同じ X=3 で上限7桁の例です。
- 0eeeeee … s(6)個
- 10eeeee … s(5)個
- 110eeee … s(4)個
- 1110aaa … k(3)個
※e…e は「連続する1の桁数の最大値が丁度Xとなる数」a…aは「連続する1の桁数の最大値が高々Xとなる数」を表します。
そのため、順番からこの分類のどれにあたるかを割り出し、上位の桁を決定することができます。未確定の下位の桁は再帰的に問題を縮小して決定していくことができます。
なお、上の例で一番下の分類となった場合、下位の桁は「丁度」ではなく「高々」の方で個数を数えていく必要がありますが、分類としては似たようなものであるため、まとめて扱います。この切り替えは、関数 f の引数 i で行っています。
バスの料金を計算しよう(初級編/ややリアル編)
類似の問題のため、まとめて取り上げます。
次のような問題でした。
- 幼児・子供・大人数名でバスを何本か乗り継ぐ時の料金の合計を計算し出力する。
- 料金の計算上複数のルールがあるときは、最も安くなるように計算する。
- 入力は、「バスの区間の標準料金(カンマ区切り)」と「乗客の種別(カンマ区切り)」をコロンでつないだもの。
※例えば、初級編での210,220,230,210:A,C,I,Aは、210円,220円,230円,210円の4区間を、分類Aが2人、分類Cが1人、分類Iが1人の合計4人で乗ることを表します。 - 乗客の種別は、初級編が A(大人)、C(子供)、I(幼児)の3種類。ややリアル編がそれぞれに n(通常)、p(定期あり)、x(特別パスあり) を加えた9種類。
※例えば“Ap”であれば、「定期ありの大人」といった種別を表します。 - 各種別での料金は次の通りです
- 大人は標準料金 ( ややリアル編では「通常」の場合 )
- 子供は標準料金の半額、ただし10円未満は切り上げ ( ややリアル編では「通常」の場合 )
- 幼児は子供と同額だが、同行する大人1名につき2名まで無料にできる
- 「定期あり」の場合は無料 ( ややリアル編 )
- 「特別パスあり」の場合は「通常」の56%の料金、ただし10円未満は切り上げ ( ややリアル編 )
- ややリアル編に限り、「一日乗車券」が選択可能。これは全区間まとめて標準料金910円とすることができる。
<>=~/(.*):(.*)/; $u+=$_,($_%4&&$d++)for split',',$1; $$_++for split',',$2; $C+=$I if($I-=$A*2)>0; print$u*$A+($u/2+$d*5)*$C;
…まあ、これはそのままですね。各区間の標準料金を全部足して、分類A,C,Iの人数 ( そのまま$A,$C,$Iで扱う ) を元に掛け算して終わりです。…ただ、210円とか、130円とか、「奇数×10円」の区間があると端数処理の分狂うので、区間数を$dでカウントして補正するようにしています。
fee,pas=gets.split(?:).map{|s|s.split ?,}
fee.map! &:to_i
discount=->f,ischild,special{
f=(f*0.05).ceil*10 if ischild
f=(f*0.056).ceil*10 if special
f
}
ftab=(0..3).map{|i|[discount[910,i>1,i%2>0],fee.reduce(0){|s,f|s+discount[f,i>1,i%2>0]}].min}
adultn=pas.count{|s|s=~/A/}
p pas \
.reject{|s|s=~/p/} \
.sort \
.chunk{|s|!!(s=~/I/)} \
.reduce(0){|s,(isinf,r)|
r.drop(isinf ? adultn*2 : 0).reduce(s){|t,e|
t+ftab[(isinf||e=~/C/?2:0)+(e=~/x/?1:0)]
}
}
ややリアル編は色々ややこしくなってます。が、一番に注意すべきは「一日乗車券の方が特になるか」の判定です。これには2点あって、
です。なので最初に、定期ありを除く各種別 ( 幼児は子供と同じなので省いて、結局4種類 ) で料金を計算して比べて最小の料金を決定してしまいます。
あとは、大人同伴で無料になる幼児についてですが、これは料金の高い幼児を優先して無料にした方が良いので、種別をソートしておきます。丁度 In の方が Ix より先に来るので、先頭を切ってしまえば良いです。
あ。「定期あり」は何やっても無料なので、最初から省いてしまいます。( ただし大人の人数には効いてくるので注意 )
世界は歪んでいる。それでも君は歩む。
次のような問題でした。
- 次の図にあるようなマス目を、0のマスから3のマスを向いている状態から、入力で指定された通りに進んだ時の、通るマスの文字を順番通りに出力する。ただし、途中でマス目の外 ( 奈落 ) に出た場合はそこで“!”を出力し以降の文字は出力しない。
- 入力は、“L”“R”0～9の数字からなる文字列で与えられる。先頭から順番に行った行動を表し、L/Rはその場での左/右への方向転換 ( 移動はしない )、数字はそのマス数分の直進を表す。
※例えば、入力が3R3の場合は、0→3→6→9 と3マス直進し、右を向いて 9→a→b→奈落 と3マス直進するため、0369ab!と出力します。
以下のPerlのコードを提出しました。
$_=<>; print 0*s/./($t+=$&<1&&(2&ord$&)-1)%4x$&/ge,s/./ $d+$&&1?$r:$c+=1-($d+$&&2); $a++,$c=$r,$r=2,$d--if$c>6; $a--,$r=$c,$c=6,$d++if$r>2; $x=$a%3*21+$c*3+$r; $h?"":($h=$c<0||$r<0||$r>2)?"!":$x>61?"@":$x<10?$x:chr$x+87-($x>35)*58 /grex
まず、入力文字列を進む数分だけの方向の数値 ( 0～3 ) に変換し、1マスずつ進める処理を考えます。例えば 5R1R1R1R1 なら、000001230 といった具合です。後は、この変換後の数値を実際に到達したマスに置き換えていきます。
横3マス×縦7マスの3領域に分割できるため、横・縦・領域それぞれの位置を $r,$c,$a で管理します。
領域をまたぐ時は $a を変化させ、同時に $r,$c を変換します。
実際に進む方向は、変換した入力文字列に対応する絶対的な方向ではなく、各領域に対しての相対的なもので考える必要があるため、ベースの方向を $d で管理します。領域をまたぐ時には $d も変化させます。
※なお、領域 $a および方向 $d はそれぞれ mod 3, mod 4 で考えます。
位置から、マスの通し番号 $x を計算し、既に奈落に到達しているかどうかのフラグである $h に応じて最終的なマスの文字を生成します。
終わりに
問題が沢山で疲れました…。なので、あくまで解説はざっくり ( 提出時のコメントをちょっと弄った位 ) にしています。
計算が簡単なもの、ケースの分類が大変なもの等色々ありましたが、どうすれば一番ラクできたかは気になりますね。( 特に「最寄りの素数」)
