7
2

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.

ゴルフ「paizaの10万登録ありがとうキャンペーン問題」 C:150/C++:174/Ruby:104/JavaScript:209/Perl:114

Last updated at Posted at 2017-05-28

paiza を勝手にコードゴルフ場にして遊んだ人たち (自分も含めて)

paiza の 10万登録ありがとうスペシャルWキャンペーン|paiza[パイザ] (4/20 - 5/21) で出題された問題で勝手にゴルフ大会が開かれて(局所的に)盛り上がっていました。キャンペーン期間が終わった今、各自提出したコードを晒して解説しているようです。僕も、折角頑張ってゴルフしたので、便乗して投稿します!

以下、投稿の時系列に記事一覧

追記: 6/6 に公式の解説も発表されました (※ゴルフの解説ではありません)。

2017/5/20 時点のランキングとリンク (敬称略)

言語 1位 2位 3位 4位 5位 大会後短縮
Java takl
0.07s/375B
uwi
0.07s/509B
dolpen
0.07s/664B
nagise
0.07s/761B
_
0.07s/1145B
PHP vivibit_net
0.03s/306B
mizzsig
0.03s/377B
okaduki
0.03s/543B
letranger
0.04s/222B
dyuma
0.04s/885B
Ruby akinomyoga
0.09s/104B
letranger
0.09s/106B
n4o847
0.09s/108B
hogeover30
0.09s/132B
Isuzu_T
0.09s/333B
akino×letran
0.09s/99B
Python2 letranger
0.02s/184B
ebicochineal
0.02s/198B
rpy3cpp
0.02s/283B
uwi
0.02s/301B
vivibit_net_evil
0.03s/137B
Perl vivibit_net
0.01s/86B
letranger
0.01s/121B
fuyutsubaki
0.01s/146B
Isuzu_T
0.01s/328B
orehajikoranai
0.01s/776B
vivibit×letran
0.01s/83B
C akinomyoga
0.01s/150B
hogeover30
0.01s/153B
ikaneko
0.01s/163B
fuyutsubaki
0.01s/174B
myanta
0.01s/186B
akino×fuyu
0.01s/149B
C++ hogeover30
0.01s/174B
akinomyoga
0.01s/174B
fuyutsubaki
0.01s/192B
kuwa
0.01s/203B
runom
0.01s/206B
akino×fuyu
0.01s/172B
C# takl
0.01s/285B
dorifru
0.01s/384B
ebicochineal
0.01s/425B
tokeiya
0.01s/460B
enum_hack
0.01s/463B
JavaScript letranger
0.06s/209B
akinomyoga
0.06s/209B
n4o847
0.06s/225B
yama
0.07s/1654B
vivibit_net_evil
0.08s/171B
akino×letran
0.06s/208B
Scala amaya
0.72s/585B
letranger
0.75s/895B
TastyPaizaPizza
0.88s/1422B
kzyKT
0.89s/687B
ciel
0.9s/523B
Python3 letranger
0.03s/172B
ebicochineal
0.03s/200B
uwi
0.03s/239B
rpy3cpp
0.03s/305B
chakku
0.04s/367B

#1 問題要約
整数の列 $s_i$ ($i=1,\dots,M$) と $p_i$ ($i=1,\dots,N$) が与えられる。各 $s_i$ ($i=1,\dots,M$) について、$$
r_i = \min(\{p_jp_k-s_i\}_{j,k=1}^N\cap\mathbb{N}_0)
$$ を出力する。

入力の形式
M N
s_1
…
s_M
p_1
…
p_N
出力の形式
r_1
…
r_M

#2 アルゴリズム
ここでは実際に提出に使ったアルゴリズムのアイディアを簡単に説明する。たぶん、コードを読むほうが早いので詳しくは説明しない。A-C の 3つのアルゴリズムを紹介するが、最終的にはどの言語にもアルゴリズムAを使った (他にもアルゴリズムは試したけれど遅かった)。また、実際のコードでは「paiza の用意したテストケースが通れば細かいことは気にしない」という方針で色々省略した。

説明のために積の集合 $Q := \{ p_i \cdot p_j; |; i,j=1,\dots,N\}$ を定義しておく。

##2.1 アルゴリズムA
アイディア: @Fuyutsubaki さんと同じアルゴリズム。まず $C[q] :\Leftrightarrow (q \in Q)$ なる配列を準備して、各 $s_i$ に対して $\min\{k\in\mathbb{N}_0; |; C[s_i+k]\}$ を線形探索する。$C$ の生成は適当に枝刈りする。メモリの無駄が大きいが単純なので短くしやすい。

複雑性: 時間計算量は、愚直にやると $O(N^2+M\kappa)$ (ただし $\kappa$ は答えの平均) になる。$p_i$ が一様分布をしていてかつ $\varepsilon := (\max s_i+K)/(\max p_i)^2$ が 1 より小さい1と仮定すれば、枝刈りによって $O(N + N^2\varepsilon(1-\log\varepsilon)+M\kappa)$ に落とせる。空間計算量は、愚直にやると $O((\max p_i)^2)$ だが、枝刈りで $O(\max s_i+\kappa)$ に抑えられる。

##2.2 アルゴリズムB
アイディア: 配列 $C$ に $Q$ をソートしたものを入れる。各 $s_i$ について $\min\{q\in C; |; q \ge s_i\}$ を二分探索して $s_i$ を減ずる。$C$ の生成は適当に枝刈りする。

複雑性: 枝刈りをすれば、空間計算量は $|C| = O(N^2\varepsilon(1-\log\varepsilon))$ で、時間計算量は $O(N+|C|+M\log|C|)$ になる。

##2.3 アルゴリズムC
アイディア: $\{p_i\}$ をソートして配列 $P$ に入れておく。問題を変形して、各 $s_i$ について、$$
\min \{P_jP_{k(j)}-s_i; |; j=1,\dots,N,; k(j)\ne N+1\}
$$ を求めるということにする。ただし2
$$
k(j) := \begin{cases}
\mathop{\rm arg min}_k(\{P_jP_k-s_i\}_k\cap\mathbb{N}_0), &
\text{if $\{P_jP_k-s_i\}_k\cap\mathbb{N}_0\ne \emptyset$}, \\
N + 1, &
\text{otherwise.}
\end{cases}
$$
ここで性質 $1 \le k(N) \le k(N-1) \le \dots \le k(1)$ (単調性) を使えば列 $k(1),\dots,k(N)$ は $O(N)$ で求められる3

複雑性: 時間計算量 $O(N(\log N + M))$、空間計算量 $O(N)$

#3 コード
目次も兼ねて、自分が提出に用いた各コードの一覧表。

言語 バイト数 アルゴリズム 提出状況
3.1 C 150B A 1位
3.2 C 173B C 途中で3.1に切り替えた
3.3 C++ 174B A 2位(提出順で負けた)
3.4 C++ 191B C 途中で3.3に切り替えた
3.5 Ruby 104B A 1位
3.6 Ruby 115B B 途中で3.5に切り替えた
3.7 JavaScript 209B A 2位(提出順で負けた)
3.8 Perl 114B A 水増し提出確認
3.9 C 139B Perl 水増し提出確認
3.10 C++ 157B Perl 水増し提出確認

順位は 2017/5/20 時点の結果。本命はC言語の 3.1 で、これが一番汚い。3.2 は気に入っている。また Perl および C/C++ の system("perl -E") を用いたものはランキングに入りたくなかったので、文字数水増しで提出した。

以降、各コードの紹介。見やすいように空白・改行を入れたが、実際の提出では勿論それらは詰めた。

##3.1 C 150B 1位 (2017/5/20時点)
アルゴリズムAによる。

C 空白類を除いて150B
D[1<<14],*C=D-2,j,k;
main(q){
  for(;
    k<=D[-1];
    j=!(
      !k?k=!~scanf("%d",++C):
      q?j<*D?q<1e4&&!++C[q]:~--*D:
      C[D[k]+j]&&printf("%d\n",j,k++)
    )*++j
  )q=C[-*D]*C[~j];
}

fuyutsubaki さんの記事を見て気付いたけれど 1<<14 (16384) は '}}'(32125) にできるので 149B になるな…。

ヒント: これだけだと多分解読に時間がかかるので、ヒントを書いておく。まず、上記のコードはそのままだとメモリのあらぬ所を触って死ぬが、コンパイラの最適化によって q=C[-*D]*C[~j] が移動されて以下のようになって (それでも未だ危ないが) ぎりぎり事なきを得る。

C 151B
D[1<<14],*C=D-2,j,k;
main(q){
  for(;
    k<=D[-1];
    j=!(
      !k?k=!~scanf("%d",++C): /* (1) */
      (q=C[-*D]*C[~j])?j<*D?q<1e4&&!++C[q]:~--*D: /* (2) */
      C[D[k]+j]&&printf("%d\n",j,k++) /* (3) */
    )*++j
  );
}

プログラムを通して j は常にインクリメントし、折に触れて 0 に初期化する。コードの動作は 3 つのステージに分けられる: (1) 読み取り (2) Cの構築 (3) 探索&出力。各ステージにいる間はそれぞれ上記コードの (1) … (3) の分岐に入る。

(1) k==0 の内は D[-1] から順に読み取った整数を格納していく。D[-1] は配列外だけれど動くから気にしない。読み取る数字がなくなったら k=1 を設定する。この時の配列 D の配置は以下のようになっている。

            配列D                                           ↓ポインタC
            +-----+------+---+------+-----------+---+-------+------+------+-…
参照方法: D[-1] | *D  | D[1] | … | D[M] | C[~(N-1)] | … | C[~0] | C[0] | C[1] | … 
中身の値: M     | N   | s_1  | … | s_M  | p_1       | … | p_N   | 0    | 0    | …
            +-----+------+---+------+-----------+---+-------+------+------+-…

(2) *D>1 の内は q!=0 になるので分岐 (2) に入る。二重ループ for (*D = N,…,1) for (j = 0,…,*D-1) で積 $q = p_j\cdot p_k$ を生成して C[q]++ として表Cを構築する。

(3) 探索&読み取りはそのまま。for (k = 1,…,D[-1]) で各 $s_k$ について計算する。

埋め込まれている定数は、テストケースに通る&CPUのキャッシュに載るように適当に小さく選んだ。

##3.2 C 173B 別アルゴリズム
初めはアルゴリズムCで戦っていた。qsort を呼び出さなければならないのでつらい。

C 173B
*P,j,q,D[4002],*Q=D-2,*S=D;
main(m){
  for(;
    P?
      j?
        q=*Q*P[j-1]-*S,
        m=q+0u<m?q:m,
        *Q*q<0?++Q:--j||printf("%d\n",m)
      :++S<(m=j=*D,Q=P)
    :~scanf("%d",++Q)||~qsort(P=Q-*S,*S,4,"\u05cb\a+\6À");
  );
}

但し、qsort に渡している文字列は、実際にはエスケープは使わずに Unicode で直接入力してバイト数を節約した。これは ciel さんの qsortの比較関数 - Qiita にあるものをお借りして、UTF-8 のバイト列になるように改造したものである。paiza では提出の文字コード及び C++ の実行文字集合は UTF-8 のようなので、上記の文字列は d7 8b 07 2b 06 c3 80 というバイト列 (7バイト) で埋め込まれる。

提出では上記のように "\u05cb\a+\6À" を用いたが "\u05cb\a+\6Ð" の方が良さそうである (安全そうな気がする)。これは UTF-8 で d7 8b 07 2b 06 c3 90 というバイト列 (7バイト) になり、x86-64 で解釈すると以下のようになる。

"\u05cb\a+\6Ð" 逆アセンブル (Intel syntax)
_d7:        xlatb ; ※UTF-8 になるように加えた無害そうな命令
_8b_07:     mov eax,[rdi]
_2b_06:     sub eax,[rsi]
_c3:        ret
_90:        nop ; ret するのでどうせここには来ない

訂正 (2017/5/29 16:58): バイト列が d7 8b 07 2b 06 c3 80 22 であると書いていましたが最後の 22 は余分でした。
訂正 (2017/5/29 16:58): \u5cb\u05cb by @cielavenir さん[コメント6]
修正 (2017/5/29 16:58): "\u05cb\a+\6Ð" を使う場合の説明に変えました。

##3.3 C++ 174B 2位 (2017/5/20時点)
アルゴリズムA。文字数は1位の hogeover30 さんと同じ。提出順で2位。

基本的にC言語と同じだが、どうやらメモリの配置が違うせいで、そのままだと怪しいメモリアクセスをしているところでクラッシュする。安全になるように修正したら文字数が増えた。

C++ 174B
#import<map>
int D[14000],*C=D-2,j,k,q;
int main(){
  for(;
    k<=D[-1];
    j=!(
      !k?k=!~scanf("%d",++C):
      (q=C[-*D]*C[~j])?j<*D?q<1e4&&!++C[q]:~--*D:
      C[j+D[k]]&&printf("%d\n",j,k++)
    )*++j
  );
}

これも fuyutsubaki さんの記事 のように '}}' を使えば 173 バイトに縮む。

追記 (2017/5/30 6:17): 眺めていたら 172 バイトになった

C++ 172B
#import<map>
int*C,D['7 '],j,k,q;int main(){for(;k<=D[-1];j=!(!k?k=!~scanf("%d",C=D+j-1):
(q=C[-*D]*C[~j])?j<*D?q<1e4&&!++C[q]:~--*D:C[j+D[k]]&&printf("%d\n",j,k++))*++j);}

##3.4 C++ 191B 別アルゴリズム
アルゴリズムC。

C++ 191B
#import<regex>
int*P,j,q,D[4002],m,*Q=D-2,*S=D;
int main(){
  for(;~scanf("%d",++Q););
  for(std::sort(P=Q-*S,Q);
    j?
      q=*Q*P[j-1]-*S,
      m=q+0u<m?q:m,
      *Q*q<0?*Q++:--j||printf("%d\n",m)
    :++S<(m=j=*D,Q=P);
  );
}

##3.5 Ruby 104B 1位 (2017/5/20時点)
アルゴリズムA。実行時の速度のばらつきで 2 回に 1 回通る程度。

Ruby 104B
M,*z=$<.map &:to_i;
*C=S=z.shift(M);
z.sort!.map{|a|z.all?{|b|C[b*=a]=0;b<M}};
S.map{|s|p C[s..-1].index 0}

b<MM は、テストケースが通るような適当に大きな数ならなんでも良かった。

2位 (106B) の @letranger さんと殆ど同じコードになっているのではないかと思っていたが全然違った。letranger さんのアルゴリズムを見たら、初期のアルゴリズム選定のときに遅くて駄目だと思って捨ててしまったのが使われていた。

追記 (2017/5/28 17:37): @letranger さん[コメント1]の手により 101 バイトになりました! [提出11回目 0.09s Accepted]

Ruby 101B by letranger
M,*z=$<.map &:to_i;S=z.shift M;z.sort!.map{|a|z.all?{|b|$*[b*=a]=0;b<M}};S.map{|s|p$*[s..-1].index 0}
  • 配列Cを自分で作る代わりに$*を使える。

追記 (2017/5/30 6:17): @letranger さん[コメント8]より 99 バイト [提出8回目 0.09s Accepted]

Ruby 99B by letranger
M,*z=$<.map &:to_i;S=z.shift M;z.sort!.map{|a|z.all?{|b|b*a<$*[b*a]=M}};S.map{|s|p$*[s,$.].index M}
  • z.all?の停止条件とCへの代入がくっつけられる。
  • $.を使う。

##3.6 Ruby 115B 別アルゴリズム
因みに Ruby は最初はアルゴリズムBで戦っていた:

Ruby 115B
M,*z=$<.map &:to_i;
S=z.shift M;C=[];
z.sort!.map{|a|z.all?{|b|C<<b*=a;b<M}};
C.sort!;
S.map{|s|p C.bsearch{|q|q>=s}-s}

##3.7 JavaScript 209B 2位 (2017/5/20時点)
アルゴリズムA。1位の @letranger さんと文字数は同じ。提出順序で2位。

速度が出ない…。速度制限のせいで余りゴルフしているような気分ではなかった。ささいな違いで通らなくなる。特に最後の2文字短縮は、@letranger さんに追いつくために、時間帯を変えるなどして意地で 37 回提出して通した…。ごめんなさい…。因みに 211 バイトのコードは 9 回だった。

JavaScript 209B
(_=process).stdin.on('data',x=>
  (
    P=(
      C=new(A=Int32Array)(2e3),
      D=new A(`${x}`.split(/\s/))
    ).slice(p=2+D[0]).sort()
  ).map(a=>
    P.find(b=>(C[b*=a]=p)<b)
  )|_.stdout.write(
    D.slice(2,p)
     .map(s=>C.indexOf(p,s)-s)
     .join`\n`
  )
)

引用: letranger さんの解説記事
"akinomyogaさんとはほぼ同じコードのような気がする。"

全然違った。自分的には恐らく違うのだろうという気はしていた。自分のコードの恣意性が大きい気がしていたので。言葉にしづらいけれどなんか、速度制限が高温の熱浴になってエントロピーが高くなっているような感覚。

追記 (2017/5/28 17:37): @letranger さん[コメント1]により `${x}`(0+x) に置き換えて 208 バイトに縮められました!

##3.8 Perl 114B
アルゴリズムA。ランキングに入らないように (Perl 勢を刺激しないため) 文字数水増しで提出して 0.01s になることを確認した。2017/5/20時点のランキングで2位相当。

Perl 114B
@s=`head @{[-<>]}`;
map{for$b(@p){$c[$q=$_*$b]=$q<2e5||last}}@p=`sort -n`;
map{$i=0;$i++until$c[$_+$i];print$i.$/}@s

2e5 は適当にテストケースに通るように選んだ数字。Perl初心者なので Perl 勢の @letranger さんや vivibit_net さんのコードは参考になる。というか、map の後の {} は省略できるのか。。vivibit_net さんの 86B は奇っ怪なコードに違いないと自分を慰めていたのに、真っ当なコードだったことが衝撃。

##3.9 C 138B139B system("perl")
禁じ手。これを許すと C/C++ ランキングが Perl ランキングと別に存在している意味がなくなってしまうので、文字数水増し提出でランキングに反映されないようにして提出した。0.01s で通ることを確認済み。

C→Perl 139B
main(){
  system(
    "perl -E'"
    "  @s=`head @{[-<>]}`;"
    "  map{for$b(@p){$c[$q=$_*$b]=1,$q>1e4&&last}}@p=`sort -n`;"
    "  map{$i=0;$i++until$c[$_+$i];say$i}@s"
    "'"
  );
}

元々 Perl 勢が system で C/C++ に攻め込んで来た時のために用意した最終兵器だった (そのときは Perl で隠れ1位だった) はずが、Perl に 86 バイトのコードが現れた (諦めるしか無い…) ために無力化されてしまった。

訂正 (2017/5/28 18:35): どれが最後に通ることを確認したコードだったか忘れたので、それっぽいの (138B) を選んで載せていたら通らないコードでした。すみません! 正しいもの (139B) に入れ替えました

##3.10 C++ 156B 157B system("perl")
同様の理由で水増し提出確認。

C++→Perl 157B
#import<map>
int main(){
  system(
    "perl -E'"
    "  @s=`head @{[-<>]}`;"
    "  map{for$b(@p){$c[$q=$_*$b]=1,$q>1e4&&last}}@p=`sort -n`;"
    "  map{$i=0;$i++until$c[$_+$i];say$i}@s"
    "'"
  );
}

訂正 (2017/5/28 18:35): 正しいもの (157B) に入れ替え。

感想

コードゴルフの競技は昔2,3回程度参加して、時間が溶けるだけで上位陣には及ばないことに気付いたので参加しないことにしていた。ところが、TL に影響されて参戦してしまった。つらかった。もう参加しないという決意を新たにした。

今回はランキングに入れたけれど、強い人達がそんなに集まらなかったからなのではないかという気がする。そもそも公式としてはゴルフではなかったという理由と、ゴルフ以前に速度が最速でなければならないという関門があったという理由があるように思う。

  1. 問題に答え $r_i$ が存在することから $\varepsilon \lesssim 1$ が保証される。

  2. なんか $\arg\min$ あたりの数式の使い方が変だけど、厳密にすると長くなるし面倒だから放置する。察して。

  3. 基本的に $k(j)$ は $k$ の小さいものから順に試して最初に非負の $P_kP_k-s_i$ が見つかったらそれを使えば良い。ここで、単調性から $k(j-1)$ の探索は $k=k(j)$ からスタートすれば十分なことが分かる。すると $O(N)$ になる。

7
2
9

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
7
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?