golf.html

<title>コードゴルフ</title>
<h3 class="shadow">コードゴルフとは</h3>
<p>与えられた条件を満たすプログラムをなるべく少ない文字数で書く競技です。ショートコーディングと呼ばれる場合や、ゴルフと略される場合があります。<br />
競プロの問題は、入力の形式・制約・出力の形式・実行時間制限などの条件がきちんと定まっているので、そのままゴルフの問題として流用することができます。<br />
その上、競プロの問題は、解くのに必要な実装量がさほど多くない（ことが多い）ので、ゴルフと相性が良いです。</p>
<h4 class="shadow">yukicoderにおけるコードゴルフ</h4>
<p>yukicoderでは、出題済みの各問題（「スコア問題」および「その他の問題」は除く）について、最短ACコード（これをyukicoderでは「ショートコード」と呼んでいます）の提出者に対してゆるふわポイントが付与されます。<br />
最短ACコードが複数ある場合は、それらの中で最も早いタイミングで提出されたコードのみをショートコードとし、その提出者に対してのみ、ゆるふわポイントが付与されます。</p>
<p>解説放送ではその時点でのショートコードが紹介されます。</p>
<p>問題毎のショートコードの一覧は以下のページで見ることができます（左のメニューの「ランキング」からこれらのページへ移動できます）。</p>
<ul>
<li><a href="https://yukicoder.me/ranking/golfer">問題別ショートコード一覧</a></li>
<li><a href="https://yukicoder.me/ranking/pure_golfer">問題別純ショートコード一覧</a></li>
</ul>
<p>その時点でのショートコードよりも短いコードを提出しACすれば、そのコードが新たなショートコードとなり、ゆるふわポイントを奪取することができます。<br />
ショートコードの保持者が変わったことについて知りたいならば、以下のbotをフォローすると便利です。</p>
<ul>
<li><a href="https://twitter.com/yukigolfer">yukicoder最短コード更新お知らせ(@yukigolfer)</a></li>
<li><a href="https://twitter.com/yukigolfer_pure">yukicoder「純」最短お知らせ(@yukigolfer_pure)</a></li>
</ul>
<h3 class="shadow">コードを書く前に</h3>
<p>実際に短いコードを書く前に知っておくべきことがいくつかあります。<br />
<h4 class="shadow">強い言語を使う</h4>
言語別ゴルフの場合は使いたい言語を使えばよいのですが、yukicoderのショートコードのような多言語混合ゴルフでは「強い言語」を使う必要があります。<br />
「強い言語」とは、主に以下の言語です。競プロerに人気のC++は、ゴルフでは弱いです。</p>
<ul>
<li>Perl（大抵のことは短く書ける。実行速度が遅いので問題によってはTLEになることもある。）</li>
<li>Ruby（大抵のことは短く書ける。実行速度はPerlよりは速いが問題によってはTLEになることもある。）</li>
<li>C（実行速度が速い言語の中では短く書ける言語である。）</li>
<li><a href="http://rsujskf.s602.xrea.com/?cLay">cLay</a>（C++っぽい言語をC++に変換する言語で、Cより短く書ける。yukicoder以外のオンラインジャッジでは使えない。）</li>
<li>Bash（dcやsedを呼び出すと短く書ける。それら以外にも競プロの問題でゴルフする際に相性の良いものはある。）</li>
<li>Perl6（<strong>Perlとは別の言語</strong>である。実行速度が非常に遅いが、とても短く書ける方法が色々ある。）</li>
</ul>
<h4 class="shadow">ジャッジ環境においてACとみなされる条件を把握しておく</h4>
<p>ジャッジ結果がACになるのであれば何でもあり（ACにならないならどんなに良さそうでもダメ）なので、ジャッジがどうなっているのかを知るのは重要です。<br />
ジャッジ環境の言語のバージョンには注意しましょう。<br />
yukicoderでは以下の点に注意するとよいでしょう。</p>
<ul>
<li>ユーザーの出力の行頭と行末のスペースを取り除いた結果が想定出力と一致すればACとなる。</li>
<li>「最後に改行してください」とあるが、改行しなくてもよい。</li>
<li><del>本来の出力の後に余計なスペースおよび改行があってもよい。</del>この仕様は修正されました。</li>
<li>出力が正しくてもREになってはいけない。</li>
<li>誤差を許容する問題では、指数表記で出力しても値として正しければよい。</li>
<li>スペシャルジャッジでは、問題文で指定されている出力形式よりも実際にACとなる出力形式が緩いことが多い（改行区切り・スペース区切りのどちらでもよい、など）。ジャッジコードを読んで実際のAC判定がどうなっているのかを確認するとよい。</li>
<li>WAになるような入力ケースがたまたまテストケースに含まれていなかったためにACとなった場合（いわゆる嘘解法）は後から落とされる可能性がある。</li>
</ul>
<h3 class="shadow">縮め方</h3>
<p>以下では、実際にコードを縮める上でよくある書き方や変形方法などについて述べます。</p>
<div class="tex2jax_ignore">
<h4 class="shadow">変数/宣言</h4>
<p>特別な理由がない限り、変数名は1文字にします。</p>
<h5 class="shadow">Perl</h5>
<p><code>$</code>に続いて変数名を書くとスカラー変数になります。</p>
<pre>$a              # aという名前の変数です。
${a}            # こうも書けます。
${'a'}          # ${式}でもよいです。
${print'!';'a'} # 余計なこともできます。
$b='a';${$b}    # $bという名前の変数です。$bの値が'a'なので$aです。
$b='a';$$b      # この場合は{}を省略できます。
</pre>
<p>変数を宣言せずに使えます。宣言しなかった場合、グローバル変数になります。スコープを制限したいときには宣言が必要です。</p>
<p>宣言したかどうかにかかわらず、変数の初期値は<code>undef</code>です。これは、数値として評価すれば0、文字列として評価すれば空文字列、真偽値として評価すれば偽です。</p>
<p><code>@</code>に続いて変数名を書くと配列変数になります。配列も宣言せずに使えます。初期値は空リストです。</p>
<pre>@a              # aという名前の配列です。
@{a}            # こうも書けます。
@{'a'}          # @{式}でもよいです。
@{print'!';'a'} # 余計なこともできます。
$b='a';@{$b}    # $bという名前の配列です。$bの値が'a'なので@aです。
$b='a';@$b      # この場合は{}を省略できます。
</pre>
<p>スカラー変数<code>$a</code>と配列変数<code>@a</code>は異なるものなので、1つのコード内で両方を使うことができます。</p>
<p>配列の1つの要素にアクセスするには<code>$a[0]</code>のように書きます。これは配列変数<code>@a</code>の0番目の要素であって、スカラー変数の<code>$a</code>とは無関係です。<code>[]</code>内はスカラーコンテキストで、整数値でないものは整数値に変換されます。</p>
<p>配列の複数の要素にアクセスするには<code>@a[0,1,2]</code>のように書きます。<code>[]</code>内はリストコンテキストで、整数値でないものは整数値に変換されます。</p>
<p><code>""</code>で囲われた文字列では変数展開されます。配列の先頭要素を数値として使う際に、これを利用して縮めることができます。</p>
<pre>@a=(3,1,4,1,5);print$a[0]+5
@a=(3,1,4,1,5);print"@a"+5
</pre>
<p><code>"@a"</code>は変数展開されて<code>"3 1 4 1 5"</code>という文字列になります。この文字列は数値として評価すると3になります。</p>
<h6 class="shadow">特殊変数</h6>
<p>特殊変数と呼ばれるものが多数あり、それらを使いこなすのはゴルフでは重要です。ゴルフでよく使う特殊変数は下表の通りです。</p>
<p>ここに載っていない情報を詳細に知りたければ<a href="https://perldoc.jp/docs/perl/5.16.1/perlvar.pod">perldoc.jp</a>などを参照してください。</p>
<table class="table">
<thread>
    <tr><th>特殊変数</th><th>型</th><th>初期値</th><th>説明</th><th></tr>
</thread>
<tbody>
    <tr><td><code>$_</code></td><td>任意</td><td><code>undef</code></td><td>無名変数です。さまざまな場面で暗黙に使われます。</td></tr>
    <tr><td><code>$.</code></td><td>任意→int64</td><td><code>undef</code></td><td>標準入力から読み込んだ行数です。読み込む前は型が決まっていません。<br />入力が1行しかない数え上げの問題では初期値の1として使えます。</td></tr>
    <tr><td><code>$%</code></td><td>int64</td><td><code>0</code></td><td>この変数に代入すると整数に変換されます。</td></tr>
    <tr><td><code>$=</code></td><td>int64</td><td><code>60</code></td><td>この変数に代入すると整数に変換されます。</td></tr>
    <tr><td><code>$-</code></td><td>uint63</td><td><code>0</code></td><td>この変数に代入すると非負整数に変換されます。<br />負数を代入すると0になるので、0とのmaxをとるのに使えます。</td></tr>
    <tr><td><code>$^T</code></td><td>int64またはint32</td><td><code>16億ぐらい</code></td><td><code>$^T</code>と書かずに<code>$&#20;</code>と書けます（<code>&#20;</code>の文字コードは20です）。<br />初期値はプログラム実行開始時刻（1970年1月1日からの経過時間）です。<br />この変数に代入すると整数に変換されます。初期値が大きいので最小値を求めるのに使えます。</td></tr>
    <tr><td><code>$^F</code></td><td>int32</td><td><code>2</code></td><td><code>$^F</code>と書かずに<code>$&#6;</code>と書けます（<code>&#6;</code>の文字コードは6です）。<br />この変数に代入すると整数に変換されます。初期値が2なのでたまに便利です。</td></tr>
    <tr><td><code>$|</code></td><td>uint1</td><td><code>0</code></td><td>この変数に代入すると、一旦整数に変換された後、それが0でなければ1に変換されます。<br/><code>--$|</code>と書くと、0なら1（-1は0でないので1に変換される）、1なら0に変わるので、0と1を交互に使いたいときに使えます。<br/>最初だけ違う処理をしたいときには<code>$|++</code>が使えます（2は0でないので1に変換される）。</td></tr>
    <tr><td><code>$/</code></td><td>文字列</td><td><code>"\n"</code></td><td>入力の行の終端を定義します。通常は「行」といえば<code>"\n"</code>が現れるまでの部分を指しますが、この変数の値を変えることで、例えば<code>" "</code>までを1行とすることもできます。<br/ >初期値が改行なので改行を出力するときにもよく使います。</td></tr>
    <tr><td><code>$"</code></td><td>文字列</td><td><code>" "</code></td><td>配列を<code>""</code>で囲んで文字列にするときに要素間を何でjoinするかを定義します。<br />初期値が空白なので、入力をsplitするときに<code>&lt;&gt;=~$"</code>の形で非常によく使います。</td></tr>
    <tr><td><code>$,</code></td><td>文字列</td><td><code>undef</code></td><td><code>print</code>で出力するときに要素間を何でjoinするかを定義します。<br />この変数の値を書き換えるとすれば大抵は<code>$,=$"</code>か<code>$,=$/</code>だと思います。</td></tr>
    <tr><td><code>$\</code></td><td>文字列</td><td><code>undef</code></td><td><code>print</code>で出力するときに末尾に何を追加するかを定義します。<br />改行を出力しなくてもよい問題で、「答え」をこの変数に入れておく使い方をします。</td></tr>
    <tr><td><code>$`</code></td><td>read-only文字列</td><td><code>undef</code></td><td>正規表現にマッチした部分よりも前の文字列です。</td></tr>
    <tr><td><code>$&</code></td><td>read-only文字列</td><td><code>undef</code></td><td>正規表現にマッチした部分の文字列です。</td></tr>
    <tr><td><code>$'</code></td><td>read-only文字列</td><td><code>undef</code></td><td>正規表現にマッチした部分よりも後の文字列です。<br />空白区切りで2つの入力が与えられたときに、<code>&lt;&gt;=~$"</code>した後、右側の値を取り出すために使います。</td></tr>
    <tr><td><code>$1</code>,<code>$2</code>,<code>$3</code>,...</td><td>read-only文字列</td><td><code>undef</code></td><td>正規表現の<i>n</i>番目の<code>()</code>にマッチした部分の文字列が<code>$<i>n</i></code>です。</td></tr>
    <tr><td><code>$#<i>hoge</i></code></td><td>int32</td><td><code>-1</code></td><td>正確には特殊変数ではないですが、変数のように扱うことができます。<br /><code>@<i>hoge</i></code>の最終インデックス（要素数-1）です。負数を代入すると-1になります。<br />配列自動拡張機能を利用して最大値を求めるのに使えます。<br /><code>pop@a</code>の代わりに<code>--$#a</code>と書いた方が短くなる場合があります。</td></tr>
</tbody>
</table>
<h5 class="shadow">C</h5>
<pre>// (1)
main(){int a=0;...
a;main(){...

// (2)
int f(int a,int b){...
f(a,b){...

// (3)
char a[99],*b;
char*b,a[99];
</pre>
<p>(1)グローバル変数は<code>0</code>で初期化されます。int型のグローバル変数は宣言する際に型を省略できます。</p>
<p>(2)int型を返す関数の返り値の型は省略できます。引数が全てint型であるような関数の引数の型は省略できます。</p>
<p>(3)ポインタ変数とポインタでない変数を宣言する場合はポインタ変数を先に書いた方が短いです。</p>
<h4 class="shadow">分岐</h4>
<p>通常のプログラミングでは分岐といえばif文ないしif-else文を使うのが常識ですが、ゴルフでは<code>?:</code>,<code>&amp;&amp;</code>,<code>||</code>を使うのが常識です（言語によっては他の分岐方法もあります）。</p>
<p><code>A?B:C</code>は、Aが真のときBが、Aが偽のときCが実行されるので、if-else文の代わりになります。</p>
<p><code>A&amp;&amp;B</code>は、Aが真のときに限り、Bが実行されるので、if文の代わりになります。<br /><code>A&amp;&amp;B</code>の真偽値を知りたいのではなく、Aの真偽値によってBが実行されるかどうかが決まる、ということです。<br />これは短絡評価と呼ばれる性質を利用したものです。</p>
<p><code>A||B</code>は、Aが偽のときに限り、Bが実行されるので、これもif文の代わりになります。</p>
<p>分岐する際には比較演算をすることが多いですが、そのときに、真偽を反転させるようにすると縮む場合があります。<br />例えば、<code>if(a&lt;=b)C</code>は<code>a&lt;=b&amp;&amp;C</code>と書けて、真偽を反転することで、<code>a&gt;b||C</code>と書けます（同様に、<code>a&lt;=b?C:D</code>も<code>a&gt;b?D:C</code>と書けます）。</p>
<pre><code>a&lt;=b  →  a&gt;b
a&gt;=b  →  a&lt;b
a==b  →  a-b  （Ruby以外の多くの言語では数値の真偽値は0なら偽、0でないなら真）
</code></pre>
<p>整数変数と定数の比較でも同様に長い演算子の代わりに短い演算子を使うことで縮む場合があります。</p>
<pre><code>a&lt;=5  →  a&lt;6
a&gt;=5  →  a&gt;4
</code></pre>
<p>比較演算は分岐の条件として使われることが多いですが、比較によって得られた真偽値を整数値として使うこともあります（Ruby以外）。<br />例えば<code>x+=a&lt;=b</code>は<code>a&gt;b||++x</code>よりも短いです。</p>
<h4 class="shadow">ループ</h4>
<h5 class="shadow">C</h5>
<p>Cのループ構文には<code>while</code>と<code>for</code>がありますが、<code>for</code>の方が短い（または同じ）です。次の3つのコードは基本的に同じです（<code>A</code>,<code>B</code>,<code>C</code>,<code>D</code>は何らかの式とします）。</p>
<pre>A;while(B){C;D;}
A;while(B)C,D;
for(A;B;D)C;
</pre>
<p><code>while</code>の繰り返す部分が単文のとき、ブロック<code>{}</code>は省略できます。これは<code>for</code>や<code>if</code>でも同様です。<code>;</code>を<code>,</code>に変えることで、通常は複数の文に分けて書くような部分を単文にすることができます。</p>
<p><code>for</code>の<code>A</code>,<code>C</code>,<code>D</code>には何を書いてもよいので、<code>while</code>で書けるものは必ず<code>for</code>でも書けます。<code>D</code>にインクリメントやデクリメント以外の式を書くこともできます。<code>B</code>の部分で<code>,</code>を使うこともあります。</p>
<h4 class="shadow">型変換</h4>
<h5 class="shadow">Perl</h5>
<p>Perlでは演算子によって項の解釈が定まることがほとんどなので、明示的に型変換する必要がある場面は他の言語に比べれば少ないものの、必要な場合もあります。また、Perlにはスカラーコンテキストとリストコンテキストという概念があり、これの変換についてもここで扱います。</p>
<p>次のコードを見てください。</p>
<pre># (1)
print&lt;&gt+0^&lt;&gt;+0
print&lt;&gt+0^&lt;&gt;

# (2)
&lt;&gt;;print 0+grep$_&gt;3,&lt;&gt;
&lt;&gt;;print~~grep$_&gt;3,&lt;&gt;

# (3)
@a=map&lt;&gt;.'',1..&lt;&gt;
@a=map~~&lt;&gt;,1..&lt;&gt;

# (4)
print int&lt;&gt;/2
print&lt;&gt;/2|0
print&lt;&gt;&gt;&gt;1

# (5)
$x=&lt;&gt;+0
$x+=&lt;&gt;
$%=&lt;&gt;
</pre>
<p>(1)は、入力の1行目の値と2行目の値をxorした結果を表示するコードです。Perlの<code>^</code>には「非負整数同士での演算」「文字列同士での演算」の2種類があり、少なくとも一方が文字列（または<code>undef</code>）でない場合は非負整数同士での演算になるので、0を足すことで数値に変換できます。少なくとも一方が文字列でなくなればよいので、1行目を型変換した場合、2行目に対しては明示的に型変換する必要はありません。</p>
<p>(2)は、入力の2行目以降に与えられた値のうち、3より大きいものの個数を表示するコードです。<code>print</code>の引数はリストコンテキストで評価されるので、<code>print grep</code>としてしまうと、条件に当てはまる要素のリストを表示してしまいます。要素数を知るにはスカラーコンテキストに変換すればよいので、0を足すのでもよいですが、ビット反転<code>~</code>を2回使ったほうが短いです。</p>
<p>(3)は、入力の1行目に要素数Nが与えられて、そこからN行にわたって与えられる文字列を<code>@a</code>に代入するコードです。<code>map</code>の第1引数はリストコンテキストで評価されるので、<code>map&lt;&gt;,1..&lt;&gt;</code>としてしまうと、<code>&lt;&gt;</code>が残りの入力の文字列のリストになってしまいます。スカラーコンテキストに変換すればよいので、空文字列を連結するのでもよいですが、文字列のビット反転<code>~</code>を2回使ったほうが短いです。</p>
<p>(4)は、入力の1行目の値を2で割った結果（切り捨て）を表示するコードです。Perlの割り算は整数同士の演算であっても結果が実数になる場合があります。実数を整数に変換するには<code>int</code>を使います。非負実数を非負整数に変換する場合は0との論理和<code>|</code>をとるほうが短いです。2の整数乗で割って切り捨てをする場合は右シフト<code>&gt;&gt;</code>を使ったほうが短い場合があります。</p>
<p>(5)は、入力の1行目の値を代入するコードです。未定義の変数に対して、文字列を数値に変換して代入したい場合は、<code>+=</code>を使うと短く書けます。Perlには特殊変数というものがあります。一部の特殊変数は型が決まっていて、代入すると強制的に型変換されます。</p>
</div>