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 に公式の解説も発表されました (※ゴルフの解説ではありません)。
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による。
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] が移動されて以下のようになって (それでも未だ危ないが) ぎりぎり事なきを得る。
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 を呼び出さなければならないのでつらい。
*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 で解釈すると以下のようになる。
_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言語と同じだが、どうやらメモリの配置が違うせいで、そのままだと怪しいメモリアクセスをしているところでクラッシュする。安全になるように修正したら文字数が増えた。
#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 バイトになった
#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。
#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 回通る程度。
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]
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]
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で戦っていた:
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 回だった。
(_=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位相当。
@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 で通ることを確認済み。
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")
同様の理由で水増し提出確認。
#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 に影響されて参戦してしまった。つらかった。もう参加しないという決意を新たにした。
今回はランキングに入れたけれど、強い人達がそんなに集まらなかったからなのではないかという気がする。そもそも公式としてはゴルフではなかったという理由と、ゴルフ以前に速度が最速でなければならないという関門があったという理由があるように思う。