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

Last updated at 2024-11-29Posted at 2017-05-28

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

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

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

ciel (@cielavenir) さんの記事: paiza POH hundred_thousand #_poh - Qiita (たぶんゴルフはなさってない。紳士)
letranger (@letranger) さんの記事: paizaの10万登録ありがとうキャンペーン問題で使用したアルゴリズムと提出コード - Qiita
fuyutsubaki (@Fuyutsubaki) さんの記事: 「paizaの10万登録ありがとうキャンペーン問題」での自分の提出コード(perl:146, C++:192) - Qiita
vivibit_net さん (の中の xx2zz さん) の記事: paizaの10万登録ありがとうキャンペーン問題提出コードと解説(Perl:86, PHP:309) | ビビビッ
akinomyoga の記事 (この記事): ゴルフ「paizaの10万登録ありがとうキャンペーン問題」 C:150/C++:174/Ruby:104/JavaScript:209/Perl:114
ikaneko (@ikaneko) さんの記事: paizaの10万登録ありがとうスペシャルの始末記 - Qiita
takl (@takl) さんの記事: paiza10万登録ありがとうゴルフ大会参加報告(Java:375 C#:285) - Qiita
dolpen (@dolpen) さんの記事: paizaの10万登録ありがとうキャンペーン問題で使った考え方とコードゴルフ - Qiita
他の参加者も是非! (見つけたら追加の予定)

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

【10万登録突破Wキャンペーン】結果発表！そしてプログラミング問題解説 - paiza開発日誌

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 より小さい¹と仮定すれば、枝刈りによって $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\}
$$ を求めるということにする。ただし²、
$$
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)$ で求められる³。

複雑性: 時間計算量 $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<M の M は、テストケースが通るような適当に大きな数ならなんでも良かった。

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 に影響されて参戦してしまった。つらかった。もう参加しないという決意を新たにした。

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

問題に答え $r_i$ が存在することから $\varepsilon \lesssim 1$ が保証される。 ↩
なんか $\arg\min$ あたりの数式の使い方が変だけど、厳密にすると長くなるし面倒だから放置する。察して。 ↩
基本的に $k(j)$ は $k$ の小さいものから順に試して最初に非負の $P_kP_k-s_i$ が見つかったらそれを使えば良い。ここで、単調性から $k(j-1)$ の探索は $k=k(j)$ からスタートすれば十分なことが分かる。すると $O(N)$ になる。 ↩

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up