Go to Qiita Advent Calendar 2024 Top
LoginSignup
7
3

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

@letranger

paizaの10万登録ありがとうキャンペーン問題で使用したアルゴリズムと提出コード

Last updated at Posted at 2017-05-25

概要

paizaの10万登録ありがとうスペシャルWキャンペーンが終了しました。
このキャンペーンの問題では言語ごとに5人まで表示されるランキングがあり、自分はそこで、数多の先人のノウハウを参考にして初めてのコードゴルフを抜きつ抜かれつしながら楽しんでいました。

自分の使用したアルゴリズムと提出したコードを簡単に紹介します。

※本文中で言及している2017/05/25現在確認可能なランキングは期間終了前日の2017/05/20時点のものなので、最終日の滑り込み次第では変化する可能性があります。

提出したコードを見直したところRubyの106bのコードではpopを使った入力受け取りを用いていなかったので、コードと本文を訂正しました(2017/05/26)。

ランキング上位を取るために

ランキングの並び順は、優先度の高い順に

  1. 平均実行時間の短さ(恐らく表示桁数分)
  2. 提出コードバイト数の少なさ(改行は2byte換算)
  3. 提出の早さ
    です。上位と同じ平均実行時間を出せばランキングに乗れた言語もありますが、基本的には平均実行時間を維持しながらもbyte数を削る必要がありました。

テストケースの実行時間は、自分の使った2種類のアルゴリズムはともにcase 1 ≒ 2 ＜ 4 ＜ 3 ＜ 5でした。
平均実行時間x秒の達成にはテストケースの3/5でx秒、残りの2/5でx+0.01秒を出せれば充分なので、提出コードが目標タイム達成可能かどうかは3番目に時間の掛かるcase 4でその目標タイムが出るかどうかで判断していました。
実行時間はだいたい0.02,3sの範囲内でぶれるので、目標タイムが出るか怪しいコードでは下ブレが揃うまで何度も提出し直すことで無理くり押し通していました(主にRubyとJavaScript)。paizaさん負荷になってたらゴメンナサイ。

……あと0.01s届かなかった方のコードの中には、同じように提出を繰り返せば届いたものがあったりして。

使用したアルゴリズム

  • どちらのアルゴリズムも予め材料の長さの配列を昇順にソートしておく。
  • 重複した材料をuniqで除去しているが、これは省いてもタイムが変わらないようだったため提出コードでは省いている。
  • result == numberの場合に脱出する分岐も同じ。
  • 最速付近の実行時間を出せるアルゴリズムはこのふたつしか思いつかなかった。

参考コードはRubyで記述している。実際の流れでは、入力例1で商品の個数が16の場合を簡単に追う。表の中の探索中に計算した値は太字で表す。

その一(単純な枝刈り？)

algorithm1.rb
M, N = gets.split.map(&:to_i)
Numbers = M.times.map{ gets.to_i }
Lengths = N.times.map{ gets.to_i }.uniq.sort
Numbers.each{|number|
  result = 9e9
  Lengths.each_with_index{|y, x_from|
    break if y * y >= result || result == number
    Lengths[x_from..-1].each{|x|
      area = x * y
      if area >= number
        result = [result, area].min
        break
      end
    }
  }
  p result - number
}

上のコードではn行目をn列目から探索することによってxとyを交換しただけの値(3 * 5に対する5 * 3など)を探索範囲から除いているが、提出コードではbyte数削減のためイテレータで全て1列目から探索していることが多い。それでも実行時間は増えないことが多かった。

実際の流れ

1行目の左端から右へ向かって、16以上の値を探索する。18が見つかったらresultを18に更新してこの行の探索を打ち切る。

result:18 3 5 6 7
3 9 15 18 21
5 15 25 30 35
6 18 30 36 42
7 21 35 42 49

次は2行目の2列目から右へ向かって探索を行うが、その前に2行目の探索開始位置にあたる25とresultを比較する。25 >= result(18)であり、これは以降の探索範囲にresult未満の値が存在しないことを意味するので探索を終了する。答えはresult(18)-16=2である。

result:18 3 5 6 7
3 9 15 18 21
5 15 25 30 35
6 18 30 36 42
7 21 35 42 49

その二(しゃくとり的？)

algorithm2.rb
# 標準入力を受け取る部分は共通
M, N = gets.split.map(&:to_i)
Numbers = M.times.map{ gets.to_i }
Lengths = N.times.map{ gets.to_i }.uniq.sort
Numbers.each{|number|
  x_idx = y_idx = Lengths.bsearch_index{|x|
    x * x >= number
  }
  result = 9e9
  while 0 <= y_idx && x_idx < Lengths.size
    area = Lengths[x_idx] * Lengths[y_idx]
    if area < number
      x_idx += 1
    elsif area == number
      result = area
      break
    else # area > number
      result = [result, area].min
      y_idx -= 1
    end
  end
  p result - number
}
  • 最初のうちはこっちで頑張っていたが、単純なループで書きやすい上の方法に乗り換えた。
  • 言語にもよるがたいていはこっちのほうがやや速いようだった。
  • 実際の流れでは表の上にはみ出たときに探索を終了しているが、右にはみ出たときも同様に終了する(上or右にしか移動しないので、下or左にはみ出ることはない)。

実際の流れ

x * x >= 16となるxの最小値である5 * 5(25)の位置から探索を開始する。resultにはまず25を代入し、25 > 16なので、次はすぐ上の値を見る。

result:25 3 5 6 7
3 9 15 18 21
5 15 25 30 35
6 18 30 36 42
7 21 35 42 49

15 < 16なので次はすぐ右の値を見る。

result:25 3 5 6 7
3 9 15 18 21
5 15 25 30 35
6 18 30 36 42
7 21 35 42 49

18 > 16なので次はすぐ上の値を見る。また18 < result(25)なのでresultを18に更新する。

result:18 3 5 6 7
3 9 15 18 21
5 15 25 30 35
6 18 30 36 42
7 21 35 42 49

18より上に値はないため探索を終了する。答えはresult(18) - 16 = 2である。

result:18 3 5 6 7
3 9 15 18 21
5 15 25 30 35
6 18 30 36 42
7 21 35 42 49

提出コード

  • 言語の並びは力を入れた順。
  • 変数名はコードによって微妙にバラバラ。紛らわしくってすみません。

Ruby

106b.rb
# 106b 0.09s
l,*u=$<.map &:to_i;q=u[l,$.].sort;u[0,l].map{|v|z=9e9;q.all?{|l|q.all?{|r|v>u=l*r}||u>z||z=u;l*l<z};p z-v}

整形すると、

106b2.rb
l, *u = $<.map &:to_i
q = u[l, $.].sort
u[0, l].map{|v|
  z = 9e9
  q.all?{|l|
    q.all?{|r|
      v > u = l * r
    } || u > z || z = u
    l * l < z
  }
  p z-v
}
  • u[l,$.]の$.には標準入力から読み込んだ行数が入っているため配列の最後までを意味する。u[l..-1]より1b短い。
  • mapの代わりにall?(或いはany?)を使うことによってbreakなしのループ脱出を行う。ただ&&や||や!のパズルで頭がこんがらがる。
  • 一番内側のループ内で代入した値を外のスコープで使うため、変数uを再利用している。
  • 探索終了条件を後ろに持ってくることでbyte数を削減している。

入力を受け取る部分は以下のようにしてもbyte数は変わらない。u.pop($.+~l)のlは商品の個数なので、$.+~l = $.-l-1 = 材料の数になる。

input2.rb
l,*u=$<.map &:to_i;q=u.pop($.+~l).sort;u.map{ # 以降は同じ

アルゴリズムその二

128b.rb
# 128b 0.09s(8-10-10-10-9)
z,*a=$<.map &:to_i;q=a[z,$.].sort;a[0,z].map{|v|l=r=q.index{|x|v<=z=x*x};0while(v>u=q[l]*q[r])?q[r+=1]:(u<z&&z=u;0<=l-=1);p z-v}
128b2.rb
z, *a = $<.map &:to_i
q = a[z, $.].sort
a[0, z].map{|v|
  l = r = q.index{|x|
    v <= z = x * x
  }
  0 while(v > u = q[l] * q[r])\
    ? q[r += 1]\
    : (u < z && z = u; 0 <= l -= 1)
  p z - v
}
  • 探索開始位置の決定に最初はbsearch_indexを使っていたが、材料の数が少ないケースが多いのかindexに変更しても実行時間は増えなかった。
  • indexのブロックの中では、106bのコードの変数uと同じ理由で外の変数zを再利用している。zの初期値は探索開始位置の値になる(探索開始位置の値以上であればなんでもよい)。
  • 結果を文字列に連結し最後に出力するなどの最適化を行うとcase 4で0.08sが出ることがあるのを確認済み。ランキングにおいて平均実行時間はbyte数よりも優先されるので8-8-9-8-9の平均0.08sを引ければ1位だが、case 1,2でもたまにしか出ない0.08s*3が前提になる争いは危険な香りしかしなかったため自重した。

JavaScript

209b.js
// 209b 0.06s(6-6-7-6-7)
p=process;p.stdin.on('data',c=>{V=(0+c).split`
`;L=V.splice(parseInt(V.shift(s=''))).sort((a,b)=>a-b);for(v of V){for(z=1/0,i=0;z>(l=L[j=++i])*l;z=u<z?u:z)for(;v>(u=l*L[j++]););s+=z-v+`
`}p.stdout.write(s)})
209b2.js
p=process;
p.stdin.on('data', c => {
  V = (0 + c).split`
`;
  L = V.splice(parseInt(V.shift(s = ''))).sort((a, b) => a - b);
  for (v of V) {
    for (z = 1 / 0, i = 0; z > (l = L[j = ++i]) * l; z = u < z ? u : z)
      for (; v > (u = l * L[j++]);)
        ;
    s += z - v + `
`
  }
  p.stdout.write(s)
})
  • process.stdin.on()とrequire('fs').readFileSync('/dev/stdin')、console.log()とprocess.stdout.write()など、byte数と速度のトレードオフとなる要素が多かった印象。速度を落とさない程度にbyte数を削るバランス取りが難しく、byte数を削るにつれ平均0.06sが出にくくなっていってやばかった……。ゴルフとは違う何かをやっていた。
  • 入力を`\n`や/\s/でsplitすると材料の配列の最後に邪魔な空文字列が混入する。数値として昇順ソートすることでこれを配列の一番上に浮上させ、探索は添字[1]から行う。
  • 抜きつ抜かれつした末に提出日時の差で1位に。akinomyogaさんとはほぼ同じコードのような気がする。

以下のコードでもcase 4での0.06sを確認できたものの、209bのコードよりもやや遅く、6-6-7-6-7が出る気配がなかったため通すのを断念。parseInt(c)が重かったのかな。

208b.js
p=process;p.stdin.on('data',c=>{s='';[,...V]=(s+c).split`
`;L=V.splice(parseInt(c)).sort((a,b)=>a-b); // 以降は同じ

Perl

121b.pl
# 121b 0.01s(1-1-1-1-1)
for$v(map<>|0,1..<>){$%=9e9;@@or@@=`sort -n`;for$^(@@){$%<$^**2&&last;$v>$_*$^or$%-=$-=$%-$_*$^,last for@@}print$%-$v,$/}

意味不明なので整形すると、

121b2.pl
for $v (map <>|0, 1..<>) {
  $% = 9e9;
  @@ or @@ = `sort -n`;
  for $^ (@@) {
    $% < $^ ** 2 && last;
    $v > $_ * $^ or $% -= $- = $% - $_ * $^, last for @@
  }
  print $% - $v, $/
}
  • 外部コマンド`sort -n`で材料の配列をソートしている。
  • $%-=$-=$%-$_*$^は$% = min($%, $_ * $^)を意味している。
  • 2位だったが、1位のvivibit_netさんには大差をつけられてしまった。86bとか完全にお手上げっす。

Python3

py3_167b.py
# 167b 0.03s(3-3-4-3-4)
N,M,*V=map(int,open(0).read().split());L=sorted(V[N:])
for v in V[:N]:z=9e9;all(z>x*x and~all(v>x*y or globals().update(z=min(z,x*y))for y in L)for x in L);print(z-v)
py3_167b2.py
N, M, *V = map(int, open(0).read().split())
L = sorted(V[N:])
for v in V[:N]:
  z = 9e9
  all(z > x * x and ~all(v > x * y or globals().update(z = min(z, x * y))
                         for y in L)
      for x in L)
  print(z-v)
  • 素人。forとbreak文を使った172b(Python2は184b)のコードを提出していたが、最終日にジェネレータ式で遊んでいたらなんか形になった。
  • z=min(z,x*y)の部分は代入ではなくキーワード引数指定(だよね？)。
  • ~Trueは-2、~Falseは-1なので、~all()は必ず真。
  • globals().update()の返り値はNoneなので必ず偽。

Python2

py2_179b.py
# 179b 0.02s(2-2-3-2-3)
V=map(int,open('/dev/stdin').read().split());L=sorted(V[-V[1]:])
for v in V[2:V[0]+2]:z=9e9;any(all(v>x*y or globals().update(z=min(z,x*y))for y in L)+z<x*x for x in L);print z-v
py2_179b2.py
V = map(int, open('/dev/stdin').read().split())
L = sorted(V[-V[1]:])
for v in V[2:V[0] + 2]:
  z = 9e9
  any(all(v > x * y or globals().update(z = min(z, x * y))
          for y in L) + z < x * x
      for x in L)
  print z-v
  • Python3との12b差はだいたい分割代入とopen(0)のせい。
  • 探索終了条件をand/orではなく+で繋ぐことによってbyte数を縮めている。ただし探索範囲が1行分増える。Python3ではcase 4で0.03sが出なくなるためこの技は使えなかった。

Python3との12b差の内訳

Python3 Python2 byte数差
N,M,*V= V= -5
open(0) open('/dev/stdin') +11
L=sorted(V[N:]) L=sorted(V[-V[1]:]) +4
for v in V[:N]: for v in V[2:V[0]+2]: +6
all(...) any(...) -3
print(z-v) print z-v -1

PHP

222b.php
<!-- 222b 0.04s(3-3-4-4-4) -->
<?php $V=file('/dev/stdin',2);$L=array_splice($V,1+intval($V[0]));sort($L);$s='';for($a=1;$v=$V[$a++];){for($z=9e9,$i=-1;$z>($x=$L[$j=++$i])*$x;)for(;$u=$x*$L[$j++];)if($v<=$u){$z=min($z,$u);break;}$s.=$z-$v.'
';}echo$s?>
222b2.php
<?php
$V = file('/dev/stdin', 2);
$L = array_splice($V, 1 + intval($V[0]));
sort($L);
$s = '';
for ($a = 1; $v = $V[$a++];) {
  for ($z = 9e9, $i = -1; $z > ($x = $L[$j = ++$i]) * $x;)
    for (; $u = $x * $L[$j++];)
      if ($v <= $u) {
        $z = min($z, $u);
        break;
      }
  $s .= $z - $v . '
';
}
echo $s
?>
  • 素人。上位の平均実行時間0.03sに届いていない移植しただけ的な4位。

さいごに

  • Scalaはランクインついでに素人なりにいろいろやってみたものの、まずタイムが1位の0.72sに及ばなかったためゴルフなんてなかった。入出力とアルゴリズムどちらが悪かったんだろうか。
  • コードゴルフは時間を吸われてやばい。けど楽しい。けどやばい。
7
3
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
7
3

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?