AtCoder
コードゴルフ
競技プログラミング
ショートコーディング


はじめに

複数の言語が同じ長さで最短である場合は、どちらのコードも紹介します。

最短コードが更新された問題があれば教えてください。

この記事が投稿された後に非自明に更新された問題については、その問題の後ろのほうに以前までの最短コードについてのコメントを残しておきます。(消すのは忍びないので)

各問題のフォーマットは以下の通りです。


ABC%03d 問題名


入力形式


解法


最短コードの言語(Byte数)

最短コード


コメント


AtCoderでコードゴルフをするにあたって


  • 出力形式について


    境界はあいまいですが、コンテストごとに「出力の末尾に改行が必要か否か」が異なります。おおむね、ABC035以前は改行が必要で、それより後は改行をつけなくてもたいていACできます。

    さらに、改行区切りを空白区切りにしたり、また空白区切りを改行区切りにして出力してもACできる場合があります。


  • 改行文字について


    submitページから直接提出すると、改行文字は2Byteとカウントされます。

    競技プログラミング補助ツールなどを使用してファイルから直接サーバーに提出することで、改行文字を1Byteにすることができます。

    競技プログラミングのための補助ツールを作った

    AtCoderへの提出をCRLFでなくLFでやるようにするuserscript(作者の方いわく、できるだけ補助ツールの方を使ってほしいそうです。)


  • テストケースハックについて


    ある時点以降に開催されたAtCoderのコンテストのテストケースはすべて公開されています。

    これを利用した、いわゆる「嘘解法」(=制約範囲内の入力の全てには正答しない解法)を使ってコードが縮む場合もあります。

    AtCoder のテストケース



言語別索引

各言語の最短コード中に頻繁に出てくる知識やテクニックもまとめて書いておきます。


Bash

ABC013 10Byte

ABC018 36Byte

ABC019 25Byte

ABC022 38Byte

ABC050 9Byte

ABC111 8Byte


Perl

<>は入力を読み込みます。数値や文字列として評価したときは1行、リストとして評価したときはすべて読み込みます。

printは引数を出力する関数です。

print (1+2)+4などでprintの直後に括弧があると、優先的にそれを引数としてprint関数を呼び出してしまうので、それを防ぐためにprintと括弧の間に+をはさむ(print+(1+2)+4)というテクニックがあります。perldoc print関数

コード中にPerlで予約されていない単語が登場すると、クオートされた文字列として解釈されます。この機能は「裸の単語」(bareword)と呼ばれています。

ABC021 18Byte

ABC045 18Byte

ABC074 13Byte

ABC076 13Byte

ABC083 47Byte

ABC087 16Byte

ABC088 21Byte

ABC089 11Byte

ABC104 29Byte

ABC112 28Byte


Ruby

getsは入力から1行読み込む関数です。

putsは引数を改行区切りで出力し、最後にも改行する関数です。

pはデバッグ用に用意された出力関数で、わずか1Byteという驚異的な短さを持ちます。(ただ、デバッグ用であるため文字列を出力するとクオートされるなど競プロには向かない面もあります。)

ABC015 20Byte

ABC023 12Byte

ABC027 16Byte

ABC075 16Byte

ABC078 24Byte

ABC095 19Byte

ABC101 14Byte

ABC110 25Byte


Sed

入力を1行ごとにパターンスペースに読み込んで実行されます。

cはパターンスペースの代わりに後に続く文字列を出力するコマンドです。

コマンドは前に条件を書くことで、それを満たすときのみ実行するようにできます。

//は正規表現によるマッチングを行います。

Yes/Noで答える問題を、

/pattern/cYes

cNo

として解くテクニックがあります。

これは、入力が/pattern/にマッチする場合Yesを、そうでない場合はNoを出力するというコードです。

[a-zA-Z0-9_]-は範囲を表します)という文字集合は「ワード文字」と呼ばれ、\wと表せるほか、単語の境界などに影響を与えます。

ABC006 15Byte

ABC010 7Byte

ABC020 17Byte

ABC028 40Byte

ABC029 6Byte

ABC033 26Byte

ABC038 12Byte

ABC042 13Byte

ABC047 15Byte

ABC048 11Byte

ABC049 26Byte

ABC051 6Byte

ABC053 17Byte

ABC054 38Byte

ABC056 10Byte

ABC059 19Byte

ABC060 25Byte

ABC062 11Byte

ABC068 8Byte

ABC070 18Byte

ABC071 12Byte

ABC073 11Byte

ABC079 19Byte

ABC085 6Byte

ABC086 16Byte

ABC093 19Byte

ABC097 15Byte

ABC099 14Byte

ABC100 16Byte

ABC109 11Byte

ABC111 8Byte

ABC114 15Byte


Awk

入力が1行ごとに読み込まれ、空白等で分割されて$1,$2,...に代入されて実行されます。$0は行全体を表します。

$0は数値として評価する場合$1と全く等しいです。

trueに評価される式があるごとに後に続くブロック、なければ{ print $0 }が実行されます。

先頭に付く式がないブロック単体は常に実行されます。

出力したいものを$0に代入し、その代入が行われた式全体をtrueと評価させることで、明示的に出力するのを省略するテクニックがあります。

"",0(0.0)のみがfalseです。

変数や文字列を並べて書くと文字列として連結されるので、0trueと評価するために未定義の変数(aなど)を使って0a(=0""="0")とするテクニックがあります。

ABC002 14Byte

ABC003 11Byte

ABC004 7Byte

ABC005 14Byte

ABC007 4Byte

ABC008 10Byte

ABC009 13Byte

ABC011 10Byte

ABC012 9Byte

ABC016 19Byte

ABC017 20Byte

ABC024 46Byte

ABC026 8Byte

ABC030 48Byte

ABC031 20Byte

ABC034 25Byte

ABC035 23Byte

ABC036 17Byte

ABC037 23Byte

ABC039 23Byte

ABC040 22Byte

ABC041 19Byte

ABC043 10Byte

ABC044 39Byte

ABC052 23Byte

ABC055 24Byte

ABC057 14Byte

ABC058 24Byte

ABC061 26Byte

ABC063 21Byte

ABC064 22Byte

ABC065 48Byte

ABC067 33Byte

ABC069 12Byte

ABC072 14Byte

ABC080 19Byte

ABC081 7Byte

ABC082 19Byte

ABC084 8Byte

ABC091 22Byte

ABC094 28Byte

ABC095 19Byte

ABC096 9Byte

ABC098 30Byte

ABC102 10Byte

ABC105 12Byte

ABC106 12Byte

ABC107 10Byte

ABC113 8Byte

ABC116 8Byte

ABC117 6Byte

ABC118 19Byte


Brainfuck

ABC090 9Byte


Octave

dispは出力を行う関数です。これは実数型を出力するとき、先頭に空白文字をつけます。初期の改行文字を省いてはいけないジャッジでは、その余計な空白によってWAと判定されてしまいます。

ABC103 23Byte


Perl6

getは入力を1行読み込む関数です。

sayは引数を出力して改行する関数です。

ABC001 12Byte

ABC009 13Byte

ABC014 12Byte

ABC019 25Byte

ABC025 32Byte

ABC032 37Byte

ABC041 19Byte

ABC046 18Byte

ABC066 29Byte

ABC074 13Byte

ABC077 27Byte

ABC092 26Byte

ABC108 12Byte

ABC115 29Byte


問題


ABC001 積雪深差


$ H_1 $

$ H_2 $


$H_1 - H_2$を出力します。


Perl6(12Byte)

say get- get


末尾に改行が必要なので、以前はPerl 13Byteが最短でしたが、AtCoderで言語のアップデートが行われた際に古い問題でもPerl6が使えるようになり、更新されました。

-は1項目と2項目を数値型にキャストして減算をします。

Perl6ではハイフンがメソッドや変数の名前として有効なので、get-getとすると存在しない関数を呼び出そうとしてREになります。

また、get -getget(-get)とパースされてしまうので、get- getは12Byte以下で唯一正しくパースされる書き方です。

実は、ABC001~005はメモリ制限が厳しいので、一部の言語はできる限りシンプルに実装してもMLEを起こします。

Perl6もそういう言語のひとつで、テストケース全てでMLEを起こさないというのはかなり運が良いことです。(僕は上のものと全く同じコードを2回submitしてどちらも1ケースだけMLEしました。)


ABC002 正直者


$ X \quad Y $


${\rm max} (X,Y)$を出力します。


Awk(14Byte)

$0=$1>$2?$1:$2


三項演算子で$X$と$Y$の大きな方を選び、$0に代入します。

$0 \le X,Y $かつ$X \ne Y$より$0は必ず正の数(=true)となるので、出力が行われます。

このコードも言語アップデートの際にAWKが使えるようになって更新されたものです。以前はbashからAWKを呼び出すコードが最短でした。


ABC003 AtCoder社の給料


$N$


$(N+1) \times 5000$を出力します。


Awk(11Byte)

$0=5e3*++$0


5e3は$5.0 \times 10^3$を表します。前置インクリメントで$0(この場合$1と等しいです)に1加算し、5000と掛け算したものを$0に代入します。

この値は必ず正であるため、出力が行われます。


ABC004 流行


$N$


$2 \times N$を出力します。


Awk(7Byte)

1,$0*=2


2倍するだけならば$0*=2でよいのですが、これだと$N=0$であるとき出力が行われません。

8Byteのコードでは$0=$1*2aなどとして数値を文字列化し、それを免れているのですが、最短コードは,を使っています。

AWKでは,範囲パターンを表し、左の式がtrueとなってから右の式がtrueになるまで常にtrueとなります。よって、左の式を常にtrueとしておけば必ず出力されます。


ABC005 おいしいたこ焼きの作り方


$x \quad y$


$\lfloor y/x \rfloor$を出力します。


Awk(14Byte)

$0=int($2/$1)a


AWKでは数値は浮動小数点数なので、intにキャストすることで切り捨てしています。

int($2/$1)が0となる場合に備えて、未定義の変数aを連結しています。


ABC006 世界のFizzBuzz


$N$


$N \in \{3,6,9\}$のときYES、そうでなければNOを出力します。


Sed(15Byte)

/[369]/cYES

cNO

正規表現において、[]というのは「どれか1文字」を表しますから、「文字列中に3,6,9のどれか1文字が含まれている」であればcYESが実行されます。そうでなければcNOが実行されます。


ABC007 植木算


$N$


$N-1$を出力します。


Awk(4Byte)

$0--


$0を直接デクリメントします。前置デクリメントを使うと、$N=1$のとき$0が0となって出力が行われなくなるので、後置デクリメントを使っています。


ABC008 アルバム


$S \quad T$


$T-S+1$を出力します。


Awk(10Byte)

$0=$2-$1+1


そのままです。$S \le T$より$T-S+1 \gt 0$であるから$0は必ずtrueとなります。


ABC009 引越し作業


$N$


$\lceil N/2 \rceil$を出力します。

この問題はPerl6とAWKで同じ13Byteの提出があります。


Perl6(13Byte)

say -+^get+>1


$\lceil A/B \rceil = \lfloor (A+B-1)/B \rfloor$なので、特に今回は$\lfloor (N+1)/2 \rfloor$を計算します。

整数を2の補数表現で保持する言語では、bit反転~と符号反転-を利用して-~a == a+1とするテクニックがあります。Perl6でも同じことができます。

また、正の数を2で割った商というのは、その数を1bit右にシフトしたものと等しいです。

演算子が他の言語とは違っているので読みにくいですが、Perl6では(数値の)bit反転が+^、右bitシフトが+>ですから、上のコードをC言語に直すと-~(入力)>>1となり、求める値が得られました。


Awk(13Byte)

$0-=int($0/2)


$\lceil N/2 \rceil=N-\lfloor N/2 \rfloor$です。この値は必ずtrueです。


ABC010 ハンドルネーム


$S$


$S$の末尾に"pp"を連結して出力します。


Sed(7Byte)

s/$/pp/


s/pattern/replacement/は正規表現patternにマッチする部分文字列をreplacementで置き換えます。

これを使って、「文字列の終端」を"pp"に置き換えます。

$は正規表現において文字列の終端という「場所」を表す文字です。元の文字列中の文字は一切変更されません。


ABC011 来月は何月?


$N$


$$

\begin{cases}

N+1 & (1 \le N \le 11) \\

1 & (N = 12)

\end{cases}

$$

を出力します。


Awk(10Byte)

$0=$0%12+1


法を12として$N$に1加算、とはちょっと違って、$\{1,2,...,12\}$にマッピングする必要があります。先に12で割った余りを求めておけば、うまく対応付けられます。


ABC012 スワップ


$A \quad B$


$B,A$の順に空白区切りで出力します。


Awk(9Byte)

$0=$2FS$1


文字列連結を使って$0=$2" "$1とするのですが、実は組み込み変数FS(Field Separator)のデフォルト値は" "なので、それを使うことで1Byte短縮されます。


ABC013 A


$X$


文字$X \in \{{\rm A},{\rm B},{\rm C},{\rm D},{\rm E} \}$が$A$を1番目として何番目かを出力します。


Bash(10Byte)

tr A-E 1-5


コマンドtrは、ある文字を別の文字に置き換えるコマンドです。置き換える対象の文字は複数指定でき、それに対応する置き換えた後の文字を同じ数指定します。

範囲指定を使えるので、上のコードはtr ABCDE 12345と等しく、これはA1に、B2に、......と置き換えます。


ABC014 けんしょう先生のお菓子配り


$a$

$b$


$a+x \equiv 0 \pmod{b} $を満たす$x(0 \le x \lt b)$を出力します。


Perl6(12Byte)

say -get%get


$x = -a \bmod b$です。C言語C99において負の数を割った余りは0以下になりますが、これは余りの定義に反することで有名な罠です。(C89では正になる場合もあるそうです。hsjoihsさんにご指摘いただきました。)

Perl6では正の余りが計算されます。


ABC015 高橋くんの研修


$A$

$B$


文字列$A,B$のうち長いほうを出力します。


Ruby(20Byte)

puts$<.max_by &:size


$<はRubyの組み込み変数です。variable $<

これは(Rubyスクリプトの実行時に引数を与えない競プロにおいては)標準入力を表し、メソッドeachを実行することで入力を改行区切りですべて読みます。

max_byはeachを呼び出し、引数で与えられた(ここでは括弧が省かれています)文字列長を返すメソッドsizeをそれぞれの文字列で実行して、その結果が最も大きなものを返します。

つまり上のコードは「入力を改行区切りですべて読み、その中で文字列長が最も長いものを出力する」という意味です。


ABC016 12月6日


$M \quad D$


$ M \equiv 0 \pmod{D}$であればYES、そうでなければNOを出力します。


Awk(19Byte)

$0=$1%$2?"NO":"YES"


$M \bmod D$が0でなければNO、0ならばYESです。


ABC017 プロコン


$s_1 \quad e_1$

$s_2 \quad e_2$

$s_3 \quad e_3$


$$

\sum_{i=1}^{3}{\frac{s_i \cdot e_i}{10} }

$$

を出力します。


Awk(20Byte)

{$0=s+=$1*$2*.1}NR>2


.10.1の省略形です。

最初のブロックは1行ごとに毎回実行されます。内部ではsにこれまでの総和を持ちつつ、$0にそれを代入しています。

このままでは出力が行われませんが、組み込み変数NR(現在の行番号を表す)が2より大、つまり3行目の処理中のみNR>2trueになって、その時点の$0つまりこれまでの$1*$2*.1の総和が出力されます。


ABC018 豆まき


$A$

$B$

$C$


それぞれの数字が3つの中で大きい順に何番目かを、それぞれの行に出力します。


Bash(36Byte)

eval nl\|sort\ -k2n{r\|,}|awk \$0+=0


これを読む前に、これの元になった以前の最短コードを読みます。


Bash(37Byte)元最短コード

nl|sort -k2nr|nl|sort -k2|awk '$0=$1'



  • コマンドnlは行の先頭に行番号をつけます。

  • コマンドsortは行を並び替えます。



    • -k2は2番目の値をkeyに指定します。


    • -nはkeyを数値として比較します。


    • -rは逆順にソートします。



パイプでつなげられたコマンドを区切り、入力例1を使って動きを追ってみます。(各フィールドの区切りは,で書きました)

input
nl
sort -k2nr
nl
sort -k2
awk '$0=$1'

12
1, 12
2, 18
1, 2, 18
2, 1, 12
2

18
2, 18
1, 12
2, 1, 12
1, 2, 18
1

11
3, 11
3, 11
3, 3, 11
3, 3, 11
3



  1. nlで先頭に行番号がつく



  2. sort -k2nrでフィールド2を数値のkeyとして逆順ソート


  3. nlで先頭に行番号がつく


  4. sort -k2でフィールド2(元の行番号)をkeyとしてソート

    実はこのとき、オプションで数値としてソートしろとは指定していませんが、行番号が1,2,3しかないので文字列として比較しても正しく並び替えられます。


  5. awk '$0=$1'でフィールド1(大きな順に並び替えたときの行番号)を取り出す

元の順番をnlで保存してから大小比較で並び替え、その順番をまたnlで保存して、元の順番に戻しています。

さて、これを縮めたものが現在の最短コード、bash 36Byteです。実際に縮んだ更新点は最後のAWKコードの部分ですが、ほかの書き方もかなり異なっています。

そもそも、nl|sort -k2nr|nl|sort -k2というのはかなり似通った文字列が2回続いたように見えませんか?実際にはnl|sort -k2nr|nl|sort -k2nなので、nl|sort -k2nという文字列を、間にr|と挟んで2回繰り返したようなものです。

これは、シェルの「ブレース展開」という機能を用いて実現できます。

ブレース展開とは、文字列を生成する機能で、例えばA{B,R,G}CABC ARC AGCに展開されます。真ん中の文字が変わっていますが、両端の2文字は変わっていないことがわかります。

これを用いてnl|sort -k2nr|nl|sort -k2nを圧縮すると、"nl|sort -k2n"{"r|",}になります。わかりやすさのために、nl|sort -k2nAr|Bとすると、これはA{B,}という意味で、展開すると(空文字列も考慮して)AB Aとなります。間にr|と挟むのを、1回目の繰り返しの末尾につなげることで達成しています。

後はシェルで特別な機能を持つ|をエスケープしてダブルクオートを外し、これによって得られた文字列をシェルコマンドとして実行すればよいです。文字列を引数に取ってシェルコマンドを実行するのはevalです。


Bash(36Byte)

eval nl\|sort\ -k2n{r\|,}|awk \$0+=0


これのeval nl\|sort\ -k2n{r\|,}が上で説明したようにnl|sort -k2nr|nl|sort -k2nを実行しています。そうして得られた出力をAWKで加工するのですが、フィールド変数$1$0に代入するのとは違う方法をとります。

$0を変更すると行の内容は削除されるので、+=0とすることによって$0の数値としての値($1に等しい)を$0に代入しつつ、そのほかの部分を削除しています。これで望む値、つまりフィールド1の値のみが出力されます。

こうすると何が嬉しいかというと、$0=$1に比べて$の出現回数が1回減ります。$といったシェルで特別な機能を持つ記号が1個しかない場合は、スクリプトをシングルクオートで囲むよりもバックスラッシュでエスケープしてしまったほうが短くなります。ここが1Byteの変更点です。


ABC019 高橋くんと年齢


$a \quad b \quad c$


3つの数の中央値を出力します。

この問題はPerl6とbashで同じ25Byteの提出があります。


Perl6(25Byte)

get.words.sort(+*)[1].say


wordsは文字列を単語に区切ってリストにする関数です。

sort(+*)はリストの要素それぞれに前置+(数値型に強制する)を適用し、ソートします。

リストの要素は3つのはずですから、0-indexedで1番目の値が求める中央値です。


Bash(25Byte)

tr \  \\n|sort -n|sed 2!d


tr \ \\ntr ' ' '\n'をバックスラッシュでエスケープすることで縮めたもので、空白文字を改行文字に置換します。

sort -nは行を数値として比較してソートします。

sed 2!dですが、2!dというのがsedに渡されたコマンドで、これは「2行目でないとき行を削除して次の処理に進む」という意味です。

dはパターンスペース(行)を削除するコマンドです。

!は直前の条件、今回であれば「2=2行目である」を否定します。


ABC020 クイズ


$Q$


$Q=1$のときABC、$Q=2$のときchokudaiを出力します。


Sed(17Byte)

/1/cABC

cchokudai

/1/で文字列中に1が含まれる、つまり$Q=1$かどうかを調べて出力を分けています。


ABC021 足し算


$N$


1行目に$N$を、2行目からN+1行目に$1$を出力します。


Perl(18Byte)

print$x=<>,'1

'
x$x

$x=<>で入力を1行読み込み、"1\n"(ここでは実際の改行文字(1Byte)を文字列に含むことで\n(2Byte)を省略している)を文字列繰り返しの演算子xを用いて$x回繰り返し、$xとその文字列を出力しています。

<>は改行付きで読み込むので、$x"数値\n"という文字列であり、"1\n1\n..."との間にも改行が出力されています。


ABC022 Best Body


$N \quad S \quad T$

$W$

$A_2$

$A_3$

$:$

$A_N$


$W,W+A_2,W+A_2+A_3,...,W+\sum_{i=2}^{N}A_i$のうち$S$以上$T$以下の数値の個数を出力します。


Bash(38Byte)

read s s t;awk $s'>(w+=$1)~w>'$t|wc -l


readは1行読み込み、空白で区切って引数に与えられた変数名の変数に代入します。ここでは、入力の1番目$N$と2番目の$S$が変数sに($N$は上書きで消される)、3番目の$T$が変数tに代入されます。

残りの入力をawkで処理します。

肝心の処理ですが、AWKにはスクリプトとして$s'>(w+=$1)~w>'$tが渡されます。

$s$tは先ほど読み込んだ$S$、$T$に展開されるのですが、シングルクオート内の$1は展開されません。

また、$s$t'>(w+=$1)~w>'の間に空白がないことから、シェルはこれを引数のひとかたまりであると認識して、結果AWKは$S$>(w+=$1)~w>$T$を実行します。(このSTは1行目の数値を表します。)

AWKではwに入力を加算していきます。AWKで大小比較はtrue or falseに応じて1 or 0を返します。二つの大小比較の結果を文字列のマッチング~で比較することを考えます。

もしマッチングが成功したら、$(S \gt w \gt T)\lor(S \le w \le T)$です。制約より$S \le T$なので、$S \le w \le T$であるとわかります。

マッチングに失敗したら、$S \gt w \lor w \gt T$です。

以上のうち、$S \le w \le T$を満たす行のみ出力したいので、マッチングが成功する行を出力します。マッチングに成功したら式の値はtrueとなって出力が行われるため、特別なことをする必要はありません。

wcは標準入力から読み込んだデータの行数や単語数、Byte数をカウントするコマンドで、オプション-lによって行数のみを出力します。ここで、wcに渡る行ではすべて$S \le w \le T$を満たすことがawkで確認されているので、行数がそのまま求める答えとなります。


ABC023 加算王


$X$


$X$の各桁の数字の和を出力します。


Ruby(12Byte)

p`dd`.sum%53


`(バッククオート)は外部コマンドを実行し、結果を文字列として受け取る機能を持ちます。

ddは標準入力をファイル等にコピーするコマンドですが、上のコードでは標準入力を一度にすべて読むために使われており、他のメソッドとの間に空白が必要ない点でgetsより優れています。

文字列のメソッドsumはチェックサムを求めるもので、今回は単に全ての文字のアスキーコードの総和を求めるために使われています。

その値を53で割った余りをpで出力します。

ここで、53という数値がどこから出てきたのかを考えます。

$X$は2桁の整数であることが約束されているので、入力される文字列は数字2文字と改行1文字であるとわかります。

ここで、例えば$X=a \times 10+b \quad (0 \le a,b \le 9)$であるとすると、数字の文字コードは48+値であることから、

`dd`.sum == (48+a) + (48+b) + 10 == a+b+106

であることが言えます。求めるのはa+bで、この値は制約より1以上18以下ですから、53で割った余りをとることで見事a+bが得られるというわけです。


ABC024 動物園


$A \quad B \quad C \quad K$

$S \quad T$


$$

\begin{cases}

A \times S + B \times T & (S+T \lt K) \\

A \times S + B \times T - C \times (S+T) & (S+T \ge K)

\end{cases}

$$

を出力します。


Awk(46Byte)

BEGIN{RS=a}$0=$5*$1+$6*$2-($5+=$6)*$3*($5>=$4)


BEGINブロックは特別で、入力を読む前に一度だけ実行されます。

RS(record separator)は入力を行に区切るときに使われる文字で、初期値は改行です。

これに未定義変数(空文字列)を代入すると、「改行が二文字続くまで」を1行として読み込みます。今回は入力すべてが読み込まれることになります。

大小比較の結果は1 or 0になるので、$(S+T)\times C \times (S+T \ge K)$を計算すれば場合分けを吸収できるのですが、ここで$S+T$を一つの変数にまとめておくことで、2度目の$S+T$の出現時にコードを縮めることができます。(($5+=$6)としておくことでコードの最後の($5+$6>=$4)($5>=$4)に縮んだ)

このコードは制約上$0が0になることがありますが、テストケースではたまたまそういう入力がないため、何も対策をしなくてもACできます。


ABC025 25個の文字列


$S$

$N$


0-indexedの文字列$S$の$\lfloor (N-1)/5 \rfloor$番目と$(N-1) \bmod 5$番目を続けて出力します。


Perl6(32Byte)

say |get.comb[($!=get-1)/5,$!%5]


combは文字列を文字のリストに分解します。これを$(N-1)/5$と$(N-1) \bmod 5$で添え字付けることで、求める場所の文字のリストが得られます。(添え字は整数であることが期待されるので、自動的に切り捨てが行われます。)

$N-1$は変数$!に保存しています。

リストをそのまま出力すると余計な括弧や空白がつくので、|を前置することで平坦化しています。これは、sayに渡る引数が「文字のリスト」から「複数の文字」になった(say ('a','b')say 'a','b'になった)ということで、sayはこれを(空白などで区切らず)順番に出力し、最後に改行します。


ABC026 掛け算の最大値


$A$


$A^2 / 4$を出力します。


Awk(8Byte)

$0*=$0/4


$A \times \frac{A}{4}$です。この値は1以上でtrueです。


ABC027 長方形


$l_1 \quad l_2 \quad l_3$


$l_{1,2,3}$に奇数個存在する数を出力します。


Ruby(16Byte)

p eval`tr " " ^`


実は$l_1 \oplus l_2 \oplus l_3$($\oplus$はbitwise XOR)が答えとなります。これは、同じ数字が2回現れると、その2数のXORが0となるからです。

`を使用して外部コマンドtrを実行しています。trでは空白文字をRubyにおけるXOR演算子^に置換します。

そうして得られた$l_1 \oplus l_2 \oplus l_3$という文字列をevalで実行し、得られた数値、つまり求める答えをpで出力します。


ABC028 テスト評価


$N$


$$

\begin{cases}

{\rm Bad} & (N \le 59) \\

{\rm Good} & (60 \le N \le 89) \\

{\rm Great} & (90 \le N \le 99) \\

{\rm Perfect} & (N=100)

\end{cases}

$$

を出力します。


Sed(40Byte)

/10/cPerfect

/9./cGreat
/[68]/cGood
cBad

これはテストケースハックによって穴だらけのコードになっているので、完全な状態のコードを以下に示します。

/100/cPerfect

/9./cGreat
/[678]./cGood
cBad

まず、入力に100という文字列が含まれるのは$N=100$のときですからPerfectと出力します。そうでなかったとき、$N$は1桁または2桁の数字です。

正規表現で「任意の1文字」は.で表されるので、2桁であって10の位が9の場合を/9./で調べ、Greatを出力します。

次に、2桁であって10の位が「6,7,8のいずれか」である場合を/[678]./で調べ([]は「どれか1文字」です)、Goodを出力します。

最後に、以上3つのどれにも当てはまらなかった場合Badを出力します。

テストケースには10という入力がなかったため、/100//10/としても動きます。

また、テストケースには10の位が7である入力がなかったため/[678].//[68]./としても動き、さらに「Goodでない かつ 1の位が6または8である」という入力がなかったため/[68]/としても動きます。

これで最初に示したコードになります。


ABC029 複数形


$W$


$W$の末尾に"s"を連結して出力します。


Sed(6Byte)

s/$/s/


ABC010とほとんど変わりないことをします。記事内リンクを貼っておくのでそちらを参照してください。


ABC030 勝率計算


$A \quad B \quad C \quad D$


$$

\begin{cases}

{\rm TAKAHASHI} & (B/A \gt D/C) \\

{\rm AOKI} & (B/A \lt D/C) \\

{\rm DRAW} & (B/A = D/C)

\end{cases}

$$

を出力します。


Awk(48Byte)

$0=(a=$2/$1-$4/$3)>0?"TAKAHASHI":a?"AOKI":"DRAW"


$B/A$と$D/C$の差を変数aに保存します。この値が0より大であれば$B/A \gt D/C$です。

そうでなかった場合、aが0でなければ$B/A \lt D/C$、0であれば$B/A = D/C$です。

この問題の以前の最短コードはPerlとAWKで同じ52Byteの提出があります。


Perl(52Byte)元最短コード

$/=$";print+(DRAW,AOKI,TAKAHASHI)[<>/<><=><>/<>],"

"


$/は入力を区切る文字で、デフォルトでは改行文字です。(これにより、<>は「1行」として改行文字までを読み込むのです。)

$"はリストを文字列化するときの区切り文字で、デフォルトでは空白文字です。

$/=$"を実行すると$/の値が空白文字になり、<>は空白区切りで読み込むようになります。

print+によって関数呼び出しとなるのを防いでいます。

リストの中身を見る前にインデックスを見ます。

<>は先に述べた通り空白区切りの入力なので、<>/<><=><>/<>は$A/B \lt=\gt C/D$を表します。

<=>は数値比較の演算子で、

$$

(x \lt=\gt y) = \begin{cases}

-1 & ( x \lt y ) \\

0 & (x = y ) \\

1 & ( x \gt y )

\end{cases}

$$

というように3種類の値を返します。

リストのインデックスに負の値を指定すると、リストの最後の要素から数えます。特に-1はリストの最後の要素を表します。

リストの中身について、DRAWAOKITAKAHASHIはどれもPerlで予約されていない単語です。裸の単語機能を使い、クオートする手間を省いています。

以上のことをまとめると、(DRAW,AOKI,TAKAHASHI)[<>/<><=><>/<>]によって以下のような値がprintに渡されます。

$$

\begin{cases}

-1 & ( A/B \lt C/D ) \\

0 & (A/B = C/D ) \\

1 & ( A/B \gt C/D )

\end{cases} \Rightarrow \begin{cases}

{\rm TAKAHASHI} & ( A/B \lt C/D ) \\

{\rm DRAW} & (A/B = C/D ) \\

{\rm AOKI} & ( A/B \gt C/D )

\end{cases} \Biggl (\Leftrightarrow \begin{cases}

{\rm TAKAHASHI} & (B/A \gt D/C) \\

{\rm AOKI} & (B/A \lt D/C) \\

{\rm DRAW} & (B/A = D/C)

\end{cases} \Biggr)

$$

これで求める答えが出力されることがわかりました。

最後に改行を出力する必要があります。Perlゴルフでは改行を出力するため頻繁に$/を使用するのですが、今回この変数の値を変更してしまったため、改行をそのまま文字列として書いています。


Awk(52Byte)元最短コード

$0=$2/$1>$4/$3?"TAKAHASHI":$2/$1~$4/$3?"DRAW":"AOKI"


大小比較をします。数値の等値比較をするために~という演算子を使っていますが、これは本来文字列に対してマッチングをするための演算子です。AWKでは数値と文字列を区別しないので、$2/$1~$4/$3$2/$1$4/$3を両方文字列として見て、$2/$1の部分文字列に$4/$3が存在するか(これは今回の場合、ほとんど「$2/$1$4/$3は等しい文字列か」という意味になります)を調べて、trueであればDRAWです。


ABC031 ゲーム


$ A \quad D $


$A \times D + {\rm max}(A,D)$を出力します。


Awk(21Byte)

$0=$1*$2+$exp($1<$2)


$はフィールドを参照する演算子なので、($1<$2?$2:$1)$($1<$2?2:1)と書けます。さらにexp関数を使うと、$1<$2のときexp(1) == 2.718...$1>=$2のときexp(0) == 1となり、これでフィールド参照をすると整数に切り捨てられて1 or 2になります。これで$1$2の大小に応じてフィールド1、2の参照を切り替えられます。


ABC032 高橋君と青木君の好きな数


$a$

$b$

$n$


${\rm lcm}(a,b)\times \lceil n/{\rm lcm}(a,b) \rceil$を出力します。


Perl6(37Byte)

say (($_=(get)lcm get)+get-1)div$_*$_


Perl6のlcm演算子を使います。(get)lcm getというのは、1つ目のgetを引数なしで呼び出していると解釈させるためにそうなっています。

$\lceil a/b \rceil = \lfloor (a+b-1)/b \rfloor$を用いて天井関数を計算しています。divは整数範囲の除算演算子で、切り捨てを行います。


ABC033 暗証番号


$N$


4桁の数$N$が、同じ数字が4つ続いた数であるときSAME、割り切れないときDIFFERENTを出力します。


Sed(26Byte)

/\(..\)\1/cSAME

cDIFFERENT

テストケースハックをすると、「同じ2桁の数字が2回続く」という条件だけでACできます。

..で任意の2文字を表し、それを\(\)でキャプチャして\1という名前を付けます。これが直後にもう一回あるため、/\(..\)\1/という正規表現が完成します。入力がこれにマッチすればSAME、しなければDIFFERENTです。


Sed(28Byte)元最短コード

/^\(.\)\1*$/cSAME

cDIFFERENT

^は文字列の先頭、$は文字列の末尾というそれぞれ「場所」にマッチする正規表現です。

^.と書くことで文字列の先頭から1文字(.は任意の1文字を表します)が得られ、この.\(\)で囲んでキャプチャすると\1という名前で参照できます。

/^\(.\)\1*$/という正規表現は、^\(.\)の直後から文字列の末尾までに\1が0個以上(*)存在し、逆に他の文字が存在しないような文字列にマッチします。これはつまり入力文字列の全文字が同じであるということなので、これにマッチすればSAME、しなければDIFFERENTです。


Awk(29Byte)元最短コード

$0=$0%1111?"DIFFERENT":"SAME"


4桁の数で同じ数字が4つ続くときというのは$1111$で割り切れるときです。このとき$0%1111は0、つまりfalseとなります。


ABC034 テスト


$x \quad y$


$x \lt y$のときBetter、そうでなければWorseを出力します。


Awk(25Byte)

$0=$1<$2?"Better":"Worse"


はい。


ABC035 テレビ


$W \quad H$


$W:H=4:3$のとき4:3、$W:H=16:9$のとき16:9を出力します。


Awk(23Byte)

$0=$2/$1~6?"16:9":"4:3"


$W:H=4:3$ならば$H/W=0.75$、$W:H=16:9$ならば$H/W=0.5625$なので、$H/W$という文字列に6という文字が含まれている、つまり6が正規表現でマッチすれば16:9であり、マッチしなければ4:3です。


ABC036 お茶


$A \quad B$


$\lceil B/A \rceil$を出力します。


Awk(17Byte)

$0=int(--$2/$1+1)


$\lceil B/A \rceil=\lfloor (B+A-1)/A \rfloor=\lfloor (B-1)/A+1 \rfloor$を使っています。前置デクリメントで括弧を使うことなく$(B-1)/A$を得ています。int関数で浮動小数点数を整数に切り捨てたものが答えです。

計算結果は必ずtrueになります。


ABC037 饅頭


$A \quad B \quad C$


${\rm max}(\lfloor C/A \rfloor,\lfloor C/B \rfloor)$を出力します。


Awk(23Byte)

$0=int($3/$exp($1>$2))a


下の元最短コードをABC031と同じテクニックで縮めたものです。


Awk(24Byte)元最短コード

$0=int($3/=$1<$2?$1:$2)a


$\lfloor C/{\rm min}(A,B) \rfloor$を出力します。/=を使うことで分母に括弧がつくのを回避しています。答えが0になる可能性があるので、int関数に未定義変数aを連結して文字列化しています。


ABC038 お茶


$S$


$S$の最後の文字がTのときYES、そうでないときNOを出力します。


Sed(12Byte)

/T$/cYES

cNO

$は文字列の末尾の位置を表す正規表現なので、/T$/は「文字列の最後の文字がTである」ときにマッチングし、YESを出力します。そうでなければNOが出力されます。


ABC039 高橋直体


$A \quad B \quad C$


$2 \times(A\times B+B\times C+C\times A)$を出力します。


Awk(23Byte)

$0=($1*$2+$3*($1+$2))*2


AWKでフィールド変数にアクセスするには2Byteも必要なので、

$3*$1+$3*$2よりも

$3*($1+$2)のほうが1Byte短くなります。

計算結果は必ずtrueになります。


ABC040 赤赤赤赤青


$n \quad x$


$ {\rm min}(x-1,n-x)$を出力します。


Awk(22Byte)

(a=$2-1)<$0-=$2{$0=a}1


aに$x-1$を代入し、$0から$2を引いて$n-x$としたものと比較します。もしa$0より小さい場合、答えはaの値ですが、このとき(a=$2-1)<$0-=$2trueとなるため、ブロックの内容$0=aが実行されます。a$0以上であればブロックは実行されません。結局、どちらの場合であっても$0の値がそのまま答えとなります。

最後に1trueと評価されて$0が出力されます。


Awk(23Byte)元最短コード

$0=$1<$2*2?$1-$2a:$2-1a


$ n-x \le x-1 \Leftrightarrow n+1 \le x \times 2 \Leftrightarrow n \lt x \times 2$なので、$n \lt x \times 2$のとき$n-x$を、そうでないとき$x-1$を出力します。

どちらも計算結果が0(=false)になる可能性があるので文字列化しておくのですが、文字列結合は優先順位が低いため、$1-$2a$2-1aのように計算に即座に続けて書いても最後に演算されます。


ABC041 添字


$s$

$i$


1-indexedで$s$の$i$文字目を出力します。

この問題はPerl6とAWKで同じ19Byteの提出があります。


Perl6(19Byte)

get.comb[get-1].say


combは文字列を文字のリストに分解します。

1行目を文字のリストに分解して、2行目の値-1番目(0-indexedにする)を出力します。


Awk(19Byte)

$0=substr(s,s=$1,1)


substr(string,start,length)は文字列stringstart文字目(1-indexed)からlength文字を切り出して返す関数です。

AWKは入力1行ごとにスクリプトを実行しますから、上のコードは2回実行されます。順に考えてみます。

ループ1回目


1. 変数sは未定義です。

2. 変数sに代入しつつ$1が渡ります。

3. 1です。

このとき、第1引数は未定義なのでどこを切り出そうとsubstrは空文字列を返します。これはfalseなので出力は行われません。

ループ2回目


1. 変数sは1行目の$1、すなわち$s$です。

2. 現在の$1、すなわち$i$です。

3. 1です。

よって、$s$の$i$文字目から1文字が切り出されて$0に代入されます。これは求める答えであり、trueなのでそのまま出力されます。


ABC042 和風いろはちゃんイージー / Iroha and Haiku (ABC Edition)


$A \quad B \quad C$


入力された3つの数字を並び替えて5 7 5が作れればYES、作れなければNOを出力します。


Sed(13Byte)

/7 7/cNO

cYES

テストケースハックです。テストケースは以下の5つのみです。

7 5 55 7 55 5 7YES

5 7 77 7 5NO

7が2つ連続している部分文字列がある場合、つまり/7 7/というパターンにマッチすればNO、そうでなければYESを出力すればよいです。

正しい解法で最も短いコードを読むことにします。(これは言語別索引には入っていません。)


Awk(26Byte)

$0=$1*$2*$3-175?"NO":"YES"


3つの数字が5 7 5の並び替えであるとき、かつそのときに限り、3つの数字の積は$175$になります。

$A \times B \times C-175$が$0$以外、つまりtrueであれば"NO"を、$0$つまりfalseであれば"YES"を出力します。


ABC043 キャンディーとN人の子供イージー / Children and Candies (ABC Edit)


$N$


$\frac{N(N+1)}{2}$を出力します。


Awk(10Byte)

$0/=2/$0++


除算ではわかりにくいので乗算に直すと、$0*=$0++/2です。......と思っていたのですが、提出してみるとREしました。手元のgawkではしっかり動きますが、AtCoderのAWKはmawkなので、その違いかもしれません。ideoneのmawkでもREが再現しました。

式の意味自体は変わっていないので$0*=$0++/2を読むことにします。

前置インクリメントでは($0+1)*($0+1)/2という意味になってしまいますが、後置インクリメントを使うことで($0+1)*$0/2となることができます。$0/2が評価され、値が確定してから、左辺の$0の値がインクリメントされる、ということです。


ABC044 高橋君とホテルイージー / Tak and Hotels (ABC Edit)


$N$

$K$

$X$

$Y$


$$

\begin{cases}

X \times N & (N \le K) \\

X \times K + Y \times (N-K) & (N \gt K)

\end{cases}

$$

を出力します。


Awk(39Byte)

BEGIN{RS=a}$0=$exp($1>$2)*($3-$4)+$1*$4


ABC024 動物園と同じく、BEGINブロック内でRSを変更して入力を全行読んでいます。記事内リンクを貼ったので詳しくはそちらを参照してください。

$exp($1>$2)のところにABC031と同じテクニックを用いています。場合分けをして読んでいきます。

$N \gt K$のとき、$exp($1>$2) == $2です。よって式は$2*($3-$4)+$1*$4 == $2*$3+($1-$2)*$4、つまり$K \times X + (N-K) \times Y$となります。

$N \le K$のとき、$exp($1>$2) == $1です。よって式は$1*($3-$4)+$1*$4 == $1*$3、つまり$N \times X$となります。

これは解法に示した場合分けと全く等しくなるので正しい答えが出力できます。計算結果は必ずtrueです。


Awk(40Byte)元最短コード

BEGIN{RS=a}$0=($1-$2)*$($1<$2?3:4)+$2*$3


こちらもRSを変更しています。同じく場合分けしてコードを読みます。

まず$N \lt K$のとき、$($1<$2?3:4) == $3です。よって式は($1-$2)*$3+$2*$3 == $1*$3、つまり$N \times X$となります。

次に$N \ge K$のとき、$($1<$2?3:4) == $4です。よって式は($1-$2)*$4+$2*$3、つまり$(N-K)\times Y + K \times X$となります。

$N=K$のときはどちらの値も等しくなるため、これらは上に示した場合分けによる答えと同じです。

計算結果を$0に代入します。この値は常にtrueです。


ABC045 台形 / Trapezoids


$a$

$b$

$h$


$\frac{(a+b)}{2}h$を出力します。


Perl(18Byte)

print+(<>+<>)*<>/2


<>は1行読み込みです。print+によって関数呼び出しとなるのを防いでいます。


ABC046 AtCoDeerくんとペンキ / AtCoDeer and Paint Cans


$a \quad b \quad c$


$a,b,c$で重複を除いた後の個数を出力します。


Perl6(18Byte)

say +get.words.Set


1行読み込んでwordsによって単語に分割し、そのリストをもとに集合クラスSetを作ります。

Setでは重複する要素は除かれるので、残った要素数を出力すればよいです。+を前置して集合を数値型に強制すると要素数となるので、これを出力します。


ABC047 キャンディーと2人の子供 / Fighting over Candies


$a \quad b \quad c$


$a=b+c \lor b=c+a \lor c=a+b$ならばYes、そうでなければNoを出力します。


Sed(15Byte)

/ [25]/cYes

cNo

テストケースハックです。


Awk(29Byte)元最短コード

$0=$0~($1+$2+$3)/2?"Yes":"No"


条件が成り立つとすると、分けることになるキャンディーの個数は$(A+B+C)/2$個になります。この値が入力文字列中に存在すればYes、しなければNoです。

~は正規表現によるマッチングの演算子で、左辺の文字列に右辺の文字列が正規表現としてマッチングするか否かを返します。左辺は入力文字列全体を表す$0、右辺は分けることになるキャンディーの個数($1+$2+$3)/2です。マッチングに成功すれば条件が成り立つとわかるのでYesを出力します。

実はこの解法は絶妙に嘘解法になっています。例えば"100 51 50"という入力を考えてみます。(この入力に対してはNoと出力されるべきです。)

このとき、($1+$2+$3)/2=="100.5"となりますが、正規表現において.は任意の1文字を表します。したがって、"100.5""100 51 50"の先頭から5文字"100 5"にマッチし、Yesと出力されてしまうのです。ただ、このようなテストケースが存在しなかったためACできました。


Awk(38Byte)元最短コード

$0=$1-$2-$3&&$1^2-($2-$3)^2?"No":"Yes"


条件をまとめることを考えます。真偽を反転した条件のうち$b\ne c+a \land c \ne a+b$をまとめて、$a \ne b+c$と合わせれば判定ができます。

$b\ne c+a \land c \ne a+b \Leftrightarrow a\ne b-c \land a \ne c-b \Leftrightarrow a \ne |b-c| \quad (\because a \gt 0)$ですから、$1$2-$3の絶対値の差が0でないことと同値です。AWKには絶対値を求める関数はありませんが、今回は数が等しいかどうかが問題であるため、2乗することでも判定ができます。


Awk(42Byte)元最短コード

$0=$1-$2-$3&&$2-$1-$3&&$3-$1-$2?"No":"Yes"


$a=b+c \lor b=c+a \lor c=a+b$の論理否定は$a \ne b+c \land b \ne c+a \land c \ne a+b$です。

さらに$a \ne b \Leftrightarrow a-b \ne 0$であることから、AWKなどの0がfalseを、非0がtrueを表す言語ではa-bと書くだけでa!=bの条件を表すことができます。


ABC048 AtCoder *** Contest


AtCoder$\quad s \quad $Contest


$x$を$s$の先頭の文字として$AxC$を出力します。


Sed(11Byte)

s/\B.\| //g


文字列から特定の文字を抜き出すのではなく、不必要な文字を取り除くことを考えます。

不必要な文字は「ワード文字の右側にある文字」と「空白文字」です。

s/pattern/replacement/gはパターンスペースの文字列を左から見ていき、/pattern/にマッチする箇所をすべてreplacementに置き換えます。ここで、一度置き換えられた文字列が再度探索されることはありません。

/pattern/を読んでいきます。

\|というのはエスケープされた|で、「左または右の正規表現のいずれか」を表します。

左の正規表現について、\Bというのは「単語の境界でない場所」を表します。これは、\bが「単語の境界である場所」にマッチするのに対して、その否定を取ったものといえます。



  • "Hello!"の中で\bがマッチする位置

 H e l l o !

↑ ↑



  • "Hello!"の中で\Bがマッチする位置

 H e l l o !

↑ ↑ ↑ ↑ ↑

.は任意の1文字を表すので、/\B./という正規表現は「「ワード文字とワード文字に挟まれた場所」とその右の文字」にマッチします。(上の例で!の後ろにもマッチしているように、実は\Bはワード文字でない文字と文字の間にもマッチしますが、今回は関係ありません。)

右の正規表現はそのまま「空白文字1字」にマッチします。

以上より、/\B.\| /は先に示した「不必要な文字」すべてに順番にマッチし、空文字列で置き換えられていくので、最終的に望む出力が得られます。


ABC049 居合を終え、青い絵を覆う / UOIAUAI


$c$


$c \in \{{\rm a},{\rm e},{\rm i},{\rm o},{\rm u}\}$であればvowel、そうでなければconsonantと出力します。


Sed(26Byte)

/[aiueo]/cvowel

cconsonant

/[aiueo]/aiueoのいずれか1文字を表します。入力にaiueoのいずれか1文字が含まれていればvowel、含まれていなければconsonantを出力します。


ABC050 Addition and Subtraction Easy


$A \quad op \quad B$


入力を数式として評価した結果を出力します。


Bash(9Byte)

expr `dd`


`dd`で入力をすべて読み、文字列化してコマンドexprの引数としています。

exprは引数の式を評価するコマンドで、評価結果を標準出力に書き出しますから、これで答えが得られます。


ABC051 Haiku


$s$


$s$中のカンマをすべてスペースに置換して出力します。


Sed(6Byte)

y/,/ /


yはシェルコマンドtrと同じく、文字ごとの置換を行います。

y/,/ /と書くと、文字列中のすべての,に置換されます。


ABC052 Two Rectangles


$A \quad B \quad C \quad D$


${\rm max}(A \times B,C \times D)$を出力します。


Awk(23Byte)

(a=$3*$4)>$0*=$2{$0=a}1


aに$C \times D$を代入しておいて、$0*=$2として得た$A \times B$と大小比較をします。もしaのほうが大きければ、$0aの値を代入します。そうでなければ、$0の値はそのまま$A \times B$です。

これで$0が答えを表すようにできました。1を評価することによって出力されます。


Awk(25Byte)元最短コード

$0=$(3^(($1*=$2)<$3*=$4))


$1*=$2$3*=$4を実行することで、$1$3のうち大きいほうを出力すればよくなります。

3^(($1*=$2)<$3*=$4)という式は、$1<$3ならば3^1==3$1>=$3ならば3^0==1のように、$1$3のうち大きなほうのフィールド番号を表します。

これを$という「フィールド参照の演算子」に適用することで、求める値を得られます。

この値は必ずtrueです。


ABC053 ABC/ARC


$x$


$x \lt 1200$ならばABC、そうでなければARCを出力します。


Sed(17Byte)

/[23]00/cARC

cABC

テストケースハックです。

正しい解法で最も短いコードを読むことにします。(これは言語別索引には入っていません。)


Perl(20Byte)

print<><1200?ABC:ARC


1行読み込んで比較し、出力を行っています。

ABCARCには裸の単語機能が使われています。


ABC054 One Card Poker


$A \quad B$


カード$N$の強さが$(N+11)\bmod 13$で定義されるので、$A$が$B$に勝つならAlice、負けるならBob、引き分けるならDrawを出力します。


Sed(38Byte)

/6\|9\| 2\|1 13/cAlice

/1 1/cDraw
cBob

テストケースハックです。

正しい解法で最も短いコードを読むことにします。(これは言語別索引には入っていません。)


Perl(50Byte)

print$/=$",(Draw,Alice,Bob)[(<>-2)%13<=>(<>-2)%13]


Perlでは負の数の余りも正の数で求められるので、$(N+11)\bmod{13}=(N-2)\bmod{13}$です。C言語やAWKでは負の数の余りは負の数になるので、-2+11になって1Byte増えてしまいました。

全体としてABC030とほとんど同じような形ですが、こちらは新しめの問題なので、そこで少し短縮されています。

まず、出力の末尾に改行が必要なくなりました。(3Byte短縮)

次に、出力の先頭に余計な空白がついていてもACできるようになったので、

$/=$";print+(...

print$/=$",(...と書けるようになりました。(1Byte短縮)


ABC055 Restaurant


$N$


$800 \times N - 200 \times \lfloor N/15 \rfloor$を出力します。


Awk(24Byte)

$0=$1*800-int($1/15)*200


intで除算の切り捨てを行っています。計算結果は必ずtrueになります。


ABC056 HonestOrDishonest


$a \quad b$


$a=b$ならばH、$a \ne b$ならばDを出力します。


Sed(10Byte)

s/H//;t;cH


入力中の文字をそのまま利用することを考えます。(ここで、空白の有無はジャッジに関係しません。)

入力がD Dである場合Hを出力しなければなりませんが、入力中にHの文字は存在しません。それは別に考えるとして、他の3パターン(H DD HH H)ではどうなるでしょうか。

H DD Hに対してはDを出力します。これは、入力中からHの文字を削除すれば良いです。

H Hに対してはHを出力します。これも入力中からHを1文字削除すれば良いです。

よって、この3パターンについてはHを1文字削除すればよいと分かったので、まずs/H//でその処理を行います。(このときD Dでは/H/とのマッチングに失敗するので削除が行われません。)

tというのはループを実現するコマンドで、以前に置換が成功していた場合、スクリプト中で指定されたラベルの存在する場所にジャンプします。今回はラベルが指定されていないので、スクリプトの最後にジャンプします。

tコマンドを実行することで、「Hの削除に成功していた」つまりH DD HH Hのどれかである場合、後の処理を行わず即座に出力して終了します。

残るD Dというパターンのみでcコマンドが実行されます。これは冒頭でも説明したように、パターンスペースの内容のかわりに後ろに続く文字列、今回はHを出力するコマンドです。

以上により、4パターンすべてで望む出力が得られました。


Sed(14Byte)元最短コード

/H/{/D/cD

};cH

{}は中のコマンドをまとめて一つのコマンドのようにします。if文のブロックのようなものです。

まず/H/が確かめられます。入力された文字列中にHが存在しない場合、D Dが入力されたと特定できるのでHを出力します。

文字列中にHが存在した場合は/D/が確かめられ、両方のマッチングが成功した、つまりHDが両方存在する場合Dを出力します。

マッチングに失敗した、つまりHDのどちらかしか存在しなかったらHを出力します。


ABC057 Remaining Time


$A \quad B$


$A+B \pmod{24}$を出力します。


Awk(14Byte)

$0=($1+$2)%24a


足して余りを求めるだけです。計算結果が0になる可能性があるため、文字列化しています。


ABC058 ι⊥l


$a \quad b \quad c$


$b-a = c-b$ならばYES、そうでなければNOを出力します。


Awk(24Byte)

$0=$2*2-$3-$1?"NO":"YES"


$b-a=c-b \Leftrightarrow b \times 2-c-a = 0$です。


ABC059 Three-letter acronym


$s_1 \quad s_2 \quad s_3$


$s_{\{1,2,3\}}$の先頭の文字を大文字にしてつなげ、出力します。


Sed(19Byte)

s/\(.\)\w* */\u\1/g


ABC048と似たような問題ですが、こちらは大文字にする必要があります。

「1個のワード文字(1と名付ける) + 0個以上のワード文字 + 0個以上のスペース」を「1の大文字」に置換する操作を文字列のすべてに行います。


  1. 1個のワード文字/\(.\)/:実は「1個の文字(スペースを含む)」でも動作します。それが.で、\(\)(特別な意味を持たせるためエスケープしています)で囲うことで、それ以降\1として参照できます。

  2. 0個以上のワード文字/\w*/\wはワード文字を表します。*で「0個以上の」です。

  3. 0個以上のスペース/ */:スペースはそのままと書きます。

そうしてマッチングした部分を、\1の大文字に置換します。\uは「後に続く文字の先頭1文字を大文字にする」で、\u\1と書くと「\1の先頭1文字(先頭も何も1文字しかないですが)を大文字にする」となります。(ちなみに、\Uは「後に続く文字すべてを大文字にする」です。)

s/pattern/replacement/gと書くと/pattern/にマッチした部分文字列すべてreplacementに置換しますから、求める答えが得られました。


ABC060 Shiritori


$A \quad B \quad C$


「$A$の最後の文字と$B$の最初の文字が同じ」かつ「$B$の最後の文字と$C$の最初の文字が同じ」であればYES、そうでなければNOを出力します。


Sed(25Byte)

s/\(.\) \1/\1/;//cYES

cNO

まずs/\(.\) \1/\1/についてです。これは「空白を挟んで同じ文字が二個続く場所」のうち文字列中に最初に現れる箇所を、その文字1文字に置換します。("abc cde efg""abcde efg"にする)

.は任意の1文字、それを\(\)で囲んで\1という名前を付けます。そこから空白を挟んでもう1回\1がある場所、というのを表す正規表現が/\(.\) \1/で、その最初の出現を\1の1文字に置換するコマンドがs/\(.\) \1/\1/です。

次に//cYESについてですが、これはsedの機能で、空のパターンは直前に実行されたパターンがあればそれに置き換わります。今回の場合、直前に/\(.\) \1/とマッチングが試されているので、/\(.\) \1/cYESとなります。

先の説明により、このパターンは「空白を挟んで同じ文字が二個続く場所」にマッチングします。s/\(.\) \1/\1/と合わせて2回マッチングすれば、条件を満たすことが確認できるのでYESを出力します。そうでなければNOです。

最初にわざわざ置換して文字を残しているのは、"abc c cde"といった$b$が1文字の入力に対応するためです。


ABC061 Between Two Integers


$A \quad B \quad C$


$A \le C \le B$ならばYes、そうでなければNoを出力します。


Awk(26Byte)

$0=$3<$1||$2<$3?"No":"Yes"


<=より<のほうが1Byte短いので、真偽を反転させています。


ABC062 Grouping


$x \quad y$


$\{1,3,5,7,8,10,12\},\{4,6,9,11\},\{2\}$というグループ分けにおいて、$x$と$y$が同じグループに属するならYes、そうでないならNoを出力します。


Sed(11Byte)

/2/cNo

cYes

テストケースが弱すぎるので、入力中に2という文字が含まれていればNo、含まれていなければYesを出力するだけでACできます。

正しい解法でコードゴルフするにはどのような方針が有効でしょうか?提出されていた中でAWKとPerlとC言語の、それぞれ最短コードがどうやってグループ分けをしているか読んでみます。


Perl(49Byte)

print$/=$",4460832/4**<>%4-4460832/4**<>%4?No:Yes


$$\left\lfloor \frac{4460832}{4^N} \right\rfloor \bmod{4}...(1)$$


Awk(50Byte)

$0=int((x=197658)/3^$1%3)-int(x/3^$2%3)?"No":"Yes"


$$\left\lfloor \frac{197658}{3^N} \bmod{3} \right\rfloor...(2)$$


C言語(71Byte)

a=199070;main(x,y){scanf("%d%d",&x,&y);puts(a/x/x-a/y/y&3?"No":"Yes");}


$$\left\lfloor \frac{\left\lfloor \frac{199070}{N} \right\rfloor}{N}\right\rfloor \bmod{4}...(3)$$

\N
1
2
3
4
5
6
7
8
9
10
11
12

(1)
0
2
0
1
0
1
0
0
1
0
1
0

(2)
0
2
0
1
0
1
0
0
1
0
1
0

(3)
2
3
2
1
2
1
2
2
1
2
1
2

正しいグループ分けができていることがわかります。


ABC063 Restricted


$A \quad B$


$A+B \ge 10$ならerror、そうでないなら$A+B$を出力します。


Awk(21Byte)

9<$0+=$2{$0="error"}1


まず$0$2を加えます。この値が9より大であった場合は、ブロックが実行されて$0"error"が上書きされます。最後に1、つまりtrueが評価されるので$0が出力されます。


ABC064 RGB Cards


$r \quad g \quad b$


$r \times 100 + g \times 10 + b \equiv 0 \pmod{4}$ならばYES、そうでないならNOを出力します。


Awk(22Byte)

$0=($2$3)%4?"NO":"YES"


$r$の値が何であろうと$100 \equiv 0 \pmod{4}$なので関係ないです。そして、AWKでは文字列連結が簡単に行えるので、$2$3とすれば数値的には$2*10+$3になります。ただ、文字列連結より余りを求める演算のほうが優先順位が高いので、括弧でくくる必要があります。


ABC065 Expired?


$X \quad A \quad B$


$$

\begin{cases}

{\rm delicious} & (-A+B \le 0) \\ {\rm safe} & (0 \lt -A+B \le X) \\ {\rm dangerous} & ( X \lt -A+B)

\end{cases}

$$

を出力します。


Awk(48Byte)

$0=$3>$2?$3>$2+$1?"dangerous":"safe":"delicious"


最初の条件は$B>A$で、これを満たさなければdeliciousです。

次の条件は$B>A+X \Leftrightarrow X<-A+B$で、これを満たせばdangerous、満たさなければsafeです。


ABC066 ringring


$a \quad b \quad c$


$a,b,c$のうち小さいほうから2つの和を出力します。


Perl6(29Byte)

$_=+<<get.words;say .sum-.max


答えは$a+b+c-{\rm max}(a,b,c)$と等しいです。

入力をwordsで単語に区切ります。+<<というのは、リストのすべての要素に前置+を適用するということで、つまりはリストの要素をすべて数値型に強制する役割を持ちます。こうして得られた$a,b,c$のリストを$_に代入します。

sumはリストの総和を求める関数で、sum $_$_.sumとして使うのですが、実は.sumとだけ書くとPerl6が$_に対して呼び出しているのだなと勝手に解釈してくれるのです。maxでも同じことができて、結局リストの総和から最大値を引いた値が得られました。

リストの要素をすべて数値型に強制しているのは、maxは文字列のリストについて辞書順比較で最大値を求めるからです。


ABC067 Sharing Cookies


$A \quad B$


$A,B,A+B$の中に3で割り切れる値が存在すればPossible、しなければImpossibleを出力します。


Awk(33Byte)

$0=($1*$2%3-1?"P":"Imp")"ossible"


法を3として、$A$と$B$の組み合わせすべてについて$A \times B$の値を書き出してみます。

A\B
0
1
2

0
0
0
0

1
0
1
2

2
0
2
1

この表の中で、Impossibleと出力すべき組み合わせである$(A,B)=(1,1),(2,2)$を抜き出すと、$A \times B$の値は2つとも1です。

逆に、Possibleと出力すべき組み合わせにおいては、$A \times B$の値は0 or 2であることがわかります。

よって、$A \times B -1 \not\equiv 0$であればPossible、そうでなければImpossibleを出力すればよいです。


Awk(39Byte)元最短コード

$0=($1*$2*($1+$2)%3?"Imp":"P")"ossible"


$A \times B \times(A+B)$が3で割り切れたら"P"、割り切れなければ"Imp"を用意して、末尾に"ossible"を連結します。

possible/impossibleで出力する問題であれば、共通部分を"possible"まで取り出せます。


ABC068 ABCxxx


$N$


ABCと$N$を続けて出力します。


Sed(8Byte)

s/^/ABC/


^は文字列の先頭という「場所」にマッチする正規表現です。s/^/ABC/で先頭をABCに置き換えて出力します。


ABC069 K-City


$n \quad m$


$(n-1)\times(m-1)$を出力します。


Awk(12Byte)

$0=--$1*--$2


前置デクリメントを使うことで括弧を省略しています。$2 \le n,m$より計算結果はtrueになります。


ABC070 Palindromic Number


$N$


$N$が文字列として回文であればYes、そうでなければNoを出力します。


Sed(18Byte)

/\(.\).\1/cYes

cNo

入力は必ず3文字です。

/\(.\).\1/を分解すると、

\(.\):任意の1文字に\1という名前を付ける

.:任意の1文字

\1:最初の\(.\)と同じ文字

となるため、1文字目と3文字目が同じならばマッチングが成功してYesを出力します。成功しなければ回文ではないのでNoです。


ABC071 Meal Delivery


$x \quad a \quad b$


$|x-a|<|x-b|$ならばA、そうでなければBを出力します。


Sed(12Byte)

/7\|60/cB

cA

テストケースハックです。


Awk(27Byte)元最短コード

$0=$2<$3~$1*2<$2+$3?"A":"B"


絶対値を求める代わりに、2乗して比較します。

$|x-a|<|x-b| \Leftrightarrow (x-a)^2<(x-b)^2 \Leftrightarrow x^2-2ax+a^20 \Leftrightarrow (2x-a-b)(a-b)>0$より、$(2x>a+b \land a>b)\lor(2x<a+b \land a<b)$です。

さて、これは制約$|x-a|\ne|x-b|$より、$a<b$と$2x<a+b$の真偽値が等しいということです。AWKでは大小比較は真偽によって1 or 0の値になるので、2つの不等式が返す値が数値的または文字列的に等しければよいです。このうち、文字列的に等しいというのは、マッチングによって判定できます。

つまり、$2<$3がとる0 or 1である文字列に、$1*2<$2+$3がとる0 or 1である文字列がマッチングすれば、上の式変形により$|x-a|<|x-b|$であると判定できるので、Aを出力します。マッチングしなければBを出力します。


ABC072 Sandglass2


$X \quad t$


$X \ge t$ならば$X-t$、そうでなければ$0$を出力します。


Awk(17Byte)

1,$0*=0<$0-=$2


まず$0から$2を引きます。この値が0より大であるか否かを1 or 0として$0に掛けます。

$0-$2が0より大であれば1が掛けられる、すなわち$0はそのままですが、0以下のときは$0*=0が実行されて$0の値は0になります。

出力を行うために、ABC004と同じく範囲パターンを用いています。


ABC073 September 9


$N$


$N$に9が含まれていればYes、含まれていなければNoを出力します。


Sed(11Byte)

/9/cYes

cNo

$N$が2桁であることが保証されているとか、そんなことは関係ありません。やるだけです。


ABC074 Bichrome Cells


$N$

$A$


$N^2-A$を出力します。

この問題はPerlとPerl6で同じ13Byteの提出があります。


Perl(13Byte)

print<>**2-<>


1行目を2乗したものから2行目を引いて出力します。


Perl6(13Byte)

say get²-get


getはPerlの<>より1Byte長いですが、かわりに2乗の操作が1Byte縮みました。それが²です。

Perl6にはUnicode演算子が存在します。Unicode 1文字で2Byteから4Byteかかり、²は2Byteでした。


ABC075 One out of Three


$A \quad B \quad C$


$A,B,C$のうち1つだけ異なる数を出力します。


Ruby(16Byte)

p eval`tr ' ' ^`


コードはABC027と全く一緒です。

こちらは数値の範囲が$[-100,100]$である点、ABC027は同じ数が3つ出現する可能性がある点で問題は少し違いますが、結局3つの数のbitwise XORをとれば答えになります。


ABC076 Rating Goal


$R$

$G$


$2 \times G-R$を出力します。


Perl(13Byte)

print-<>+<>*2


-(1行目)に2行目を2倍して足します。入力順の関係からこのような書き方になっています。


ABC077 Rotation


$C_{1,1}C_{1,2}C_{1,3}$

$C_{2,1}C_{2,2}C_{2,3}$


1行目を反転したものが2行目と等しければYES、等しくなければNOを出力します。


Perl6(27Byte)

<NO YES>[get~~get.flip].say


flipは文字列を反転する関数です。1行目と反転した2行目を~~で比較しています。

~~はスマートマッチと呼ばれる演算子で、右辺の型によって挙動を変えます。今回は右辺が文字列なので、文字列の等値比較になります。

get~~get.flipTrueorFalseになるのですが、これをインデックスにすると数値の1or0になります。

<NO YES>は文字列のリスト("NO","YES")に等しいです。

Perlでは裸の単語と言って予約されていない単語は文字列として解釈されましたが、Perl6ではその機能は取り除かれました。ただ、<>で囲うことで単語のリストを作ることができ、それにインデックスでアクセスすることで答えを出力しています。


ABC078 HEX


$X \quad Y$


$X,Y \in \{{\rm A},{\rm B},{\rm C},{\rm D},{\rm E},{\rm F}\}$で、$X$と$Y$を16進数としてみたとき$X \lt Y$ならば<、$X \gt Y$ならば>、$X=Y$ならば=を出力します。


Ruby(24Byte)

putc 61.+gets[0]<=>$_[2]


まずgets[0]<=>$_[2]を読みます。

getsは入力を1行読み込むとともにその値を$_に代入します。文字列のインデックスは文字を取り出すので、これは「入力の1文字目($X$)と3文字目($Y$)を<=>で比較する」という意味になります。(文字の比較はアスキーコード順ですから、正しい大小関係が得られます。)

<=>は左辺と右辺の比較結果に応じて<=>-1===>0>=>1のいずれかを返す演算子です。

ここで出力する文字<=>のアスキーコードを確認すると、606162と見事に並んでいます。

$X \lt Y$
$X = Y$
$X \gt Y$

gets[0]<=>$_[2]の結果
-1
0
1

出力したい文字のアスキーコード
60
61
62

したがって、61gets[0]<=>$_[2]を足せば答えが得られます。

優先順位の関係から、本来なら61+(gets[0]<=>$_[2])と書くところなのですが、Rubyの演算子はほとんどがメソッド呼び出しの糖衣構文であり、メソッド呼び出しは引数の括弧を省けるので、61.+gets[0]<=>$_[2]を得ました。

最後に、putcでアスキーコードがあらわす文字に変換し、出力します。


ABC079 Good Integer


$N$


$N$を文字列として見たとき、同じ文字が3つ以上続けて並んでいればYes、そうでなければNoを出力します。


Sed(19Byte)

/\(.\)\1\1/cYes

cNo

\(.\)である1文字に\1という名前をつけ、\1\1でさらに2文字並んでいるかを確認します。入力の連続した3文字のどれかがこれにマッチすればYes、マッチしなければNoを出力します。


ABC080 Parking


$N \quad A \quad B$


${\rm min}(N \times A,B)$を出力します。


Awk(19Byte)

$0=$(($3<$2*=$1)+2)


$2*=$1を実行することで、$2$3のうち小さいほうを出力すればよくなります。

($3<$2*=$1)+2は、$3<$2であれば(1)+2==3を、$3>=$2であれば(0)+2==2を表しますから、この値をフィールド参照の演算子$で参照すれば求める値が得られます。

$0は必ずtrueになります。


ABC081 Placing Marbles


$s_1s_2s_3$


$s_{1,2,3}$のうち1であるものの個数を出力します。


Awk(7Byte)

9>$0%=9


入力を数値としてみれば$s_1 \times 100+s_2 \times 10+s_3$であり、$s_{1,2,3}$は0または1なので、9で割った余りは$s_1+s_2+s_3$になり、これが答えです。

9で割った余りは0になる可能性があるので、9と大小比較をすることでtrueを無理やり作っています。こういう書き方でもAWKは正しくパースして、先に$0%=9を行った後に大小比較をしてくれます。


ABC082 Round Up the Mean


$a \quad b$


$\lceil (a+b)/2 \rceil$を出力します。


Awk(19Byte)

$0=int(++$1/2+$2/2)


$0=int(($1+$2+1)/2)と意味もByte数も同じです。計算結果は常にtrueです。


ABC083 Libra


$A \quad B \quad C \quad D$


$A+B \gt C+D$ならLeft、$A+B=C+D$ならBalanced、$A+B \lt C+D$ならRightを出力します。


Perl(47Byte)

print$/=$",(Balanced,Left,Right)[<>+<><=><>+<>]


使っているテクニックが全く同じABC030と、それを短縮する方法としてABC054の下の方を参照してください。


ABC084 New Year


$M$


$48-M$を出力します。


Awk(8Byte)

$0=48-$0


計算結果は必ずtrueです。


ABC085 Already 2018


$S$


$S$の4文字目の78に変えて出力します。


Sed(6Byte)

s/7/8/


先頭4文字が2017だと保証されており、s/pattern/replacement/最初の/pattern/の出現をreplacementに置換するので、ほかの部分に7という文字列があっても問題ありません。


ABC086 Product


$a \quad b$


$a \times b$が奇数ならOdd、偶数ならEvenと出力します。


Sed(16Byte)

/[04]/cEven

cOdd

テストケースハックです。

正しい解法で最も短いコードを読むことにします。(これは言語別索引には入っていません。)


Sed(21Byte)

/[02468]\>/cEven

cOdd

2数の積が偶数であるというのは2数のいずれかが偶数であることと同値であり、ある数が偶数であるとは下1桁が0,2,4,6,8のいずれかであることと同値です。

つまり、入力文字列中に単語の末尾であるような0,2,4,6,8のいずれかが存在すればEven、しなければOddです。

「0,2,4,6,8のいずれか」は[02468]、単語の末尾(左にワード文字、右にワード文字でない文字(文字列の終端も含む)があるような場所)を表すのは\>です。


ABC087 Buying Sweets


$X$

$A$

$B$


$(X-A)\bmod{B}$を出力します。


Perl(16Byte)

print+(<>-<>)%<>


この記事の冒頭で説明したように、print()の間に+を入れます。


ABC088 Infinite Coins


$N$

$A$


$N \bmod{500} \le A$ならばYes、そうでなければNoを出力します。


Perl(21Byte)

print<>%500><>?No:Yes


裸の単語機能を使い、NoYesをクオートするのを省略しています。

入力が複数行にわたるときは、sedやAWKなどの「1行ごとに処理する言語」では少し難しくなるので、そこにPerlの付け入る隙が生まれます。


ABC089 Grouping 2


$N$


$\lfloor N/3 \rfloor$を出力します。


Perl(11Byte)

print<>/3|0


bitwise ORは演算される値を整数に切り下げるので、0とorをとることで値を変えずに切り下げを実現しています。

awkは切り下げるためにint関数を使う必要があるほか、計算結果が0になる可能性があるために文字列化をしなければならず、そこでPerlと差がつきました。


ABC090 Diagonal String


$c_{1,1}c_{1,2}c_{1,3}$

$c_{2,1}c_{2,2}c_{2,3}$

$c_{3,1}c_{3,2}c_{3,3}$


$c_{1,1}c_{2,2}c_{3,3}$と出力します。


Brainfuck(9Byte)

>,.,,,,+]


ABC-Aにおいては唯一のBrainfuckによる最短コードです。この問題はBrainfuckに優しく、他のAtCoderで使えるすべての言語に優しくない問題でした。

方針としては1文字読んで出力、4文字(改行も1文字なので)読んでEOFではなかったら最初に戻る、ということをします。

これを実現するコードは、EOFを読み込むとAtCoderの処理系では-1(実際は255)と処理されることを踏まえて

+[,.,,,,+]

なのですが、実はAtCoderで採用されているBrainfuckの処理系にはバグがあるらしく(各種サービスにおけるbrainfuck処理系について参照)、対応する[が存在しない]でジャンプしようとすると先頭付近(最初のコードでは先頭から2Byte目)に飛ぶようです。

これを利用して、[とその中に入るための+が削れ、コードが短縮されました。


ABC091 Two Coins


$A \quad B \quad C$


$A+B \ge C$ならばYes、そうでなければNoを出力します。


Awk(22Byte)

$0=$1+$2<$3?"No":"Yes"


やるだけ。


ABC092 Traveling Budget


$A$

$B$

$C$

$D$


${\rm min}(A,B)+{\rm min}(C,D)$を出力します。


Perl6(26Byte)

say [+] min(+get,+get)xx 2


まず、min(+get,+get)で「2行読み込み、数値型にしたものの最小値」という意味になります。

xxというのはリスト繰り返しの演算子で、リストは繰り返す度に評価が行われます。

今回は2回繰り返すことで${\rm min}(A,B)$と${\rm min}(C,D)$のリストを得ています。

+は加算の演算子ですが、[]で囲まれることでリストをfoldする演算子になります。

したがって、[+] min(+get,+get)xx 2は${\rm min}(A,B)+{\rm min}(C,D)$を表し、これを出力します。


ABC093 abc of ABC


$S$


$S$がabcの並び替えであればYes、そうでないならNoを出力します。


Sed(19Byte)

/\(.\).*\1/cNo

cYes

$S$にはa,b,cの文字しか含まれないので、同じ文字が2つあればNoです。

\(.\)によって1文字キャプチャして\1とし、そのあとにも\1が存在するかを調べていますが、間に何文字あるか定かではないので、「任意の文字が0文字以上」ということで.*を挟んでいます。


ABC094 Cats and Dogs


$A \quad B \quad X$


$A \le X \le A+B$であればYES、そうでなければNOを出力します。


Awk(28Byte)

$0=$1>$3~$1+$2<$3?"YES":"NO"


$1>$3が返す文字列と$1+$2<$3が返す文字列(どちらも1 or 0です)が等しいかどうかをマッチングを用いて判定しています。

$1>$3$1+$2<$3は両方が同時に成り立つことはないので、もしマッチングが成功したとしたら、どちらも偽であった場合、つまり$1<=$3かつ$1+$2>=$3であった場合であり、すなわち$A \le X \le A+B$なのでYESを出力します。

マッチングが失敗した場合は$A \gt X$または$A+B \lt X$のどちらかが成立したということなので、NOを出力します。


ABC095 Something on It


$S$


文字列$S$中に$n$個oが存在するとして、$700+100 \times n$を出力します。

この問題はAWKとRubyで同じ19Byteの提出があります。


Awk(19Byte)

$0=7+gsub("o",e)0 0


gusbは第3引数、なければ$0中の、第1引数のパターンの出現すべてを第2引数の文字列に置換し、置換が行われた回数を返します。

今回は第1引数に"o"1文字、第2引数に空文字列(ここは今回何でも構いません)、第3引数はなしで呼び出されたので、$0中のoの文字数が返ってくることになります。

これに7を足して100倍すればよいのですが、実は100倍するよりも文字列の"00"を連結するほうが短いです。それが後ろについている0 0で、間に何も挟んでいないので文字列連結がされ、$0に代入されます。(00は数値の0になってしまうので、スペースを間に入れて対処しています。)

$0trueとなるので、出力が行われます。


Ruby(19Byte)

p`dd`.sum%5*100+700


`dd`.sumについてはABC023を参照してください。

入力中に出現しうる文字の文字コードはそれぞれo=111x=120\n=10です。よって、$S$の長さが3であることを踏まえて、$S$の文字コードの合計を5で割った余りは入力中のoの数と等しくなります。


ABC096 Day of Takahashi


$a \quad b$


$a \le b$ならば$a$を、そうでなければ$a-1$を出力します。


Awk(9Byte)

$0-=$1>$2


$1>$2は$a \gt b$のとき1、そうでなければ0になるので、それを$0から引けばよいです。

制約から計算結果は必ず1以上になるので、出力が行われます。


ABC097 Colorful Transceivers


$a \quad b \quad c \quad d$


$|a-c|\le d \lor (|a-b|\le d \land |b-c| \le d)$ならばYes、そうでなければNoを出力します。


Sed(15Byte)

/[29]$/cNo

cYes

テストケースハックです。


Perl6(54Byte)元最短コード

$/=get.words;<No Yes>[so$3>=abs $0-$2|$0-$1&$1-$2].say


これを読む前に、下の元最短コードを読みます。


Perl6(57Byte)元最短コード

get~~m:g/\d+/;say $3>=abs($0-$2|$0-$1&$1-$2)??"Yes"!!"No"


get~~m:g/\d+/は、1行読み込んで正規表現によるマッチングを行っています。

正規表現m:g/\d+/m:g/\d+/に分解できます。

まず\dが「数字1文字」、+は「直前の正規表現が1文字以上」を表すので、/\d+で「連続した数字」です。

:gは「文字列全体を見てマッチする箇所すべてにマッチする」というフラグを表します。

mは後ろに続くものが正規表現であることを示します。

以上のことより、get~~m:g/\d+/は入力中の$a,b,c,d$それぞれとマッチするのですが、このときマッチした箇所を順番に$0,$1,$2,$3に代入します。よって、以降のソースコードでこの変数を使うことで入力された数値を得られます。

次に条件の判定部分$3>=abs($0-$2|$0-$1&$1-$2)を見ます。

|&はJunctionと呼ばれ、論理値の重ね合わせを表現します。今回のコードでは、$3>=abs($0-$2)||$3>=abs($0-$1)&&$3>=abs($1-$2)と書いたのと等しいです。そしてこれは解法の条件そのままなので、Trueであれば"Yes"を、Falseであれば"No"を出力します。(Perl6の三項演算子は?? !!です。)

さて、これまでは文字列のリストにインデックスでアクセスすることでYes/Noを出力してきましたが、実はJunctionはそのインデックスによってアクセスされたリストの値までも重ね合わせてしまうので、結果的にJunctionクラスの値が出力されることになり、正しい答えが得られません。三項演算子を使う必要があったわけです。ありませんでした。

さて、現在の最短コードを読みます。


Perl6(54Byte)

$/=get.words;<No Yes>[so$3>=abs $0-$2|$0-$1&$1-$2].say


まず、1行読み込んで単語に分割し、$/に代入しています。この$/というのは本来、正規表現の結果を取得するために用意された変数です。

元のコードでは$0$1などとして入力データにアクセスしたわけですが、実は$0というのは正規表現のために用意された変数ではなく、$/[0]の糖衣構文です。

つまり、$/=get.wordsによって変数$/の中身がリスト$\{a,b,c,d\}$である今、$/[0](=$a$)や$/[1](=$b$)が$0$1でアクセスできるようになっているということです。

以上より、get~~m:g/\d+/$/=get.wordsがもたらす結果はほとんど等しく、さらに後者のほうが1Byte短いのです。

もう一つ、出力部が更新されました。「Junctionはそのインデックスによってアクセスされたリストの値までも重ね合わせてしまう」と書きましたが、それはJunctionの値を確定させていないからです。

Junctionの値が確定するのは、真偽値の文脈で評価されたときなので、リストのインデックスとして使うためには自分で真偽値として評価してしまえばよいわけです。

prefix?またはsoを使用することで値を真偽値に強制できますが、?>=より優先度が高いため、括弧でくくらなければなりません。soではその必要がないため、こちらを採用しています。

この更新の副産物として、abs関数呼び出しの括弧が必要なくなりました。


ABC098 Add Sub Mul


$A \quad B$


${\rm max}(A+B,A-B,A \times B)$を出力します。


Awk(30Byte)

(a=$1+($2^2)^.5)>$0*=$2{$0=a}1


ABC040と同じテクニックを使って$0に答えを代入し、1を評価することで出力しています。計算の内容については下の元最短コードの説明を読んでください。(ただし、上のコードは答えが0になろうと問題なく出力されるので、下のコードのような嘘解法ではありません。)


Awk(34Byte)元最短コード

$0=(a=$1+($2^2)^.5)>$1*$2?a:$1*$2s


まず${\rm max}(A+B,A-B)$を計算します。これは$A+ {\rm max}(B,-B)=A+|B|$となるので、$2を2乗して0.5乗(省略して.5と書いています)することで$|B|$を得、それと$1の和を変数aに代入しています。

次に、a$1*$2の比較をします。この2つのうち大きいほうが答えなので、それを$0に代入します。

最後に、答えが0になってしまい出力が行われないことはないか確認します。

仮に、$A \ne 0 \land B \ne 0$とします。

まず、$A+|B|=0 \Leftrightarrow (B \lt 0 \land A=B )\lor(B \gt 0 \land A=-B)$です。

$B \lt 0 \land A=B $のときは$A \times B \gt 0$となり、よいです。

$B \gt 0 \land A=-B$のときは$A \times B \lt 0$となりますから、aを文字列化する必要がありますが、そういうテストケースは存在しませんでした。

次に、$A \times B =0 \Leftrightarrow A=0 \lor B=0$です。

$A=0 \land B \ne 0$のときは、$A+|B| \gt 0$なのでよいです。

$A \ne 0 \land B=0$のときは、$A \gt 0$ならば$A+B \gt 0$なのでOK、$A \lt 0$ならば$A \times B$が答えになるので、$1*$2を文字列化する必要があります。

$A=0 \land B=0$のときを考えると、a$1*$2も0となります。この場合、a>$1*$2が成り立たないので$1*$2が出力されるため、$1*$2を文字列化する必要があります。

以上より、(テストケースハックをして)$1*$2だけ文字列化しておけば正しく出力されることがわかりました。


ABC099 ABD


$N$


$N \lt 1000$ならばABC、そうでなければABDと出力します。


Sed(14Byte)

/1../cABD

cABC

テストケースハックです。

正しい解法で最も短いコードを読むことにします。(これは言語別索引には入っていません。)


Sed(15Byte)

/..../cABD

cABC

$N$が4文字であればABDです。.は任意の1文字を表す正規表現です。


ABC100 Happy Birthday!


$A \quad B$


$A \le 8 \land B \le 8$ならばYay!、そうでなければ:(と出力します。


Sed(16Byte)

/\B\|9/c:(

cYay!

$A$または$B$が9以上であるという条件を作ります。

9以上である、というのは「9である」または「2文字の数字である」ということです。2文字の数字であるということは、「ワード文字とワード文字に挟まれた場所」が存在するということと等しく、そのような場所は\Bであらわされます。

これと9\|(または)でつなぐことで$A$または$B$が9以上であるという条件が得られ、これを満たせば:(、満たさなければYay!を出力します。


ABC101 Eating Symbols Easy


$S$


0に$S$中の+の個数を足し、$S$中の-の個数を引いて出力します。


Ruby(14Byte)

p 186-gets.sum


gets.sumは文字列を1行読み込み、アスキーコードの和を求めます。(sumは文字列のチェックサムを求める関数のため、本来ならば2の累乗数で割った余りを返しますが、今回は入力のサイズが小さいので関係ありません。)

+のアスキーコードは43、-のアスキーコードは45なので、それぞれ44を引いたものを足し合わせて符号を反転すると答えが得られます。

getsは改行込みで読み込むので引くべき数は$44 \times 4 + 10=186$、符号を反転するためにアスキーコードの和から186を引くのではなく186からアスキーコードの和を引くとして、得られた数をpで出力します。


ABC102 Multiple of 2 and N


$N$


$N$が偶数なら$N$、奇数なら$2\times N$を出力します。


Awk(10Byte)

$0*=$0%2+1


偶数なら$N \times 1$、奇数なら$N \times 2$を出力すると見ると、かけるべき数は$N \bmod2+1$であることがわかります。

計算結果は必ずtrueになります。


ABC103 Task Scheduling Problem


$A_1 \quad A_2 \quad A_3$


${\rm max}(A_1,A_2,A_3)-{\rm min}(A_1,A_2,A_3)$を出力します。


Octave(23Byte)

disp(range(dlmread(0)))


dlmread(0)は、引数に与えられたファイルから入力を整数として読み込み、行列にして返します。0は標準入力を表します。

結果、1行3列の行列、つまり3要素の行ベクトルが返ります。

rangeはベクトルを受け取るとそれの最大値と最小値の差を計算します。

dispで出力します。内部的には実数型ですが、新しいジャッジなので先頭に空白があっても構いません。


Perl6(26Byte)元最短コード

say +^-minmax +<<get.words


+<<get.wordsで入力を1行読んで単語に区切り、数値化したリストが得られます。

minmaxは、リストから最小値と最大値を取り出し、それを両端としたRangeを作ります。Rangeは数値として扱うと範囲の内部に入る要素(ここでの要素とは元のリストの要素ではなく、値がすべて始点以上終点以下である公差が1の等差数列の要素)の個数を返し、これは今回の場合求める値よりも1だけ大きいはずです。

ところが、-1+minmax...とすると、Rangeで定義された+が行われるため、すべての要素に-1を足すという意味になってしまいます。

これを避けるために、bit反転と符号反転を用いてa-1 == ~-aとするテクニックを使います。

Perl6のbit反転の演算子は+^なので、+^-minmax...とすることで1引いたのと同じ値が得られます。


ABC104 Rated for Me


$R$


$R \lt 1200$ならばABC、$1200 \le R \lt 2800$ならばARC、$2800 \le R$ならばAGCを出力します。


Perl(29Byte)

print A.(B,R,G)[<>/50+8>>5].C


ABRGCは予約語ではないためすべてクオートされた文字列として扱われます。

$R$を50で割って、8を足して、右に5bitシフトするとどのような値になるでしょうか。(制約より$R \le 4208$です。)

$$R \lt 1200 \Leftrightarrow \frac{R}{50}+8 \lt 32 \Leftrightarrow \frac{R/50+8}{2^5}\lt 1$$

$$1200 \le R \lt 2800 \Leftrightarrow 32 \le \frac{R}{50}+8 \lt 64 \Leftrightarrow 1\le\frac{R/50+8}{2^5}\lt 2$$

$$ 2800 \le R \le 4208 \Leftrightarrow 64 \le \frac{R}{50}+8 \le 92.16 \Leftrightarrow 2 \le \frac{R/50+8}{2^5} \lt 3$$

よって、<>/50+8>>5は出力に応じて0,1,2の3種類の値をとることが分かったので、これをリストのインデックスとして出力の真ん中の文字B,R,Gを決めます。

.は文字列連結の演算子で、ACで左右から挟んだ文字列が答えなので、これを出力します。


ABC105 AtCoder Crackers


$N \quad K$


$N \bmod{K}=0$ならば0、そうでなければ1を出力します。


Awk(12Byte)

2>$0=$1%$2>0


$1%$2>0という大小比較は0または1で結果を返すので、これがそのまま答えになります。ただ、0はfalseとなってしまうので、2>$0として無理やりtrueを作っています。AWKはこう書いても2>($0=$1%$2>0)であると解釈してくれます。


ABC106 Garden


$A \quad B$


$(A-1)\times(B-1)$を出力します。


Awk(12Byte)

$0=--$1*--$2


ABC069と制約も入力形式も解法も何もかも一緒です。最短コードもそっくり同じでした。(提出された方も同じです。)


ABC107 Train


$N \quad i$


$N-i+1$を出力します。


Awk(10Byte)

$0-=$2-1


$N-(i-1)$です。この値は制約から必ずtrueになります。


ABC108 Pair


$K$


$\lfloor K/2 \rfloor \times \lfloor (K+1)/2 \rfloor$を出力します。


Perl6(12Byte)

say get²+>2


$K$が偶数のとき$K^2/4$、$K$が奇数のとき$(K-1)(K+1)/4=(K^2-1)/4$と式変形できるのですが、これは結局$\lfloor K^2/4 \rfloor$です。

まず、get²で$K^2$を得ます。

4で切り捨て除算をするのは右に2bitシフトするのと等しいので、右bitシフトの演算子+>で右に2bitシフトし、出力します。


ABC109 ABC333


$A \quad B$


$A$または$B$が2であればNo、そうでなければYesを出力します。


Sed(11Byte)

/2/cNo

cYes

制約から、2という文字が存在するか判定すればよいです。存在すればNo、しなければYesです。


ABC110 Maximize the Formula


$A \quad B \quad C$


$A+B+C+9\times{\rm max}(A,B,C)$を出力します。


Ruby(25Byte)

p eval$<.chars.sort*?++?0


$<.chars.sortで、入力をすべて読み込んで1文字ごとに区切り、アスキーコードでソートした文字の配列が得られます。?+とは'+'のことで、配列に右から文字列をかけると、その文字列でjoinされます。

仮に入力が5 1 3であったとすると、改行文字のアスキーコードは10、空白文字のアスキーコードは32でどちらも数字1文字より小さいことを踏まえて、$<.chars.sort*?+は文字列"\n+ + +1+3+5"になります。(先頭の"\n"は改行文字です。)

これに?0、すなわち'0'を右から足すと"\n+ + +1+3+50"となり、先頭にいくつかついた+は単項演算子と解釈されるので、これでRubyの有効なコードとなります。

また、この式を評価した値は${\rm max}(A,B,C)$だけを10倍して3数を足している式なので、求める値に等しいです。

よって$<.chars.sort*?++?0evalして出力します。


Ruby(29Byte)元最短コード

p gets.bytes.max*9+$_.sum-650


$A$、$B$、$C$はそれぞれ1桁の数です。

gets.bytes.maxは改行付きで1行読み込み、それぞれの文字のアスキーコードの最大値を返しますが、この値は'0'のアスキーコードが48であることから${\rm max}(A,B,C)+48$と等しいです。

$_.sumについてですが、$_にはgetsを実行したときに読み込んだ文字列が入っています。メソッドsumは今回は文字ごとのアスキーコードの総和を計算していて、これは空白文字(アスキーコード32)2つと改行文字(アスキーコード10)1つを含めて$(A+48)+32+(B+48)+32+(C+48)+10=A+B+C+218$と等しいです。

以上のことから、gets.bytes.max*9+$_.sumの値は$({\rm max}(A,B,C)+48)\times 9+A+B+C+218=A+B+C+9\times{\rm max}(A,B,C)+650$なので、これから650を引いて出力すれば求める答えが得られます。


ABC111 AtCoder Beginner Contest 999


$n$


$n$の19に、91にそれぞれ置き換えて出力します。


Sed(8Byte)

y/19/91/


yは文字ごとの置換をするコマンドです。置換する文字集合を19、置換先の文字集合を91と指定すると、問題で求められている通りの置換が行われます。同時に処理されるので、19が混じることもありません。


Bash(8Byte)

tr 19 91


sedのyはシェルコマンドのtrと同じです。引数で置換対象、置換先にそれぞれ1991を指定します。


ABC112 Programming Education

入力は次の2通りのうちどちらかの形式で与えられ、それぞれ出力すべきものが異なります。


$1$


Hello Worldを出力します。


$2$

$A$

$B$


$A+B$を出力します。


Perl(28Byte)

<>;print<>+<>||"Hello World"


<>が3回実行されるので、入力によってはEOFに達してからも読み込もうとする可能性があります。このようなとき、Perlでは空文字列を読み込んだようになります。空文字列は数値としては0に等しいです。

このことと$A+B \gt 2$であることを踏まえると、「2回目に読み込んだ値」+「3回目に読み込んだ値」の値が2以上である、もっと言えば非0であればそれを出力し、0と等しければ"Hello World"を出力すればよいことがわかります。

以上より、1行目を読み飛ばした上で<>+<>||"Hello World"を出力します。

論理和の演算子||は短絡します。左から順に評価を行い、「初めてtrueになった項」または「最後に評価された項」の値を返します。

つまり<>+<>||"Hello World"全体としての値は、<>+<>trueつまり非0であれば<>+<>の値に、そうでなければ"Hello World"という値になるので、上の場合分けの通りに正しく出力されます。


ABC113 Discount Fare


$X \quad Y$


$X+\frac{Y}{2}$を出力します。


Awk(8Byte)

$0+=$2/2


$0は数値として評価すると$1($X$)と等しいので、これに$\frac{Y}{2}$つまり$2/2を足し合わせると答えが得られます。

制約より$0は必ず2以上の数になり、出力されます。


ABC114 753


$X$


$X \in \{3,5,7\}$のときYES、そうでなければNOを出力します。


Sed(15Byte)

/[357]/cYES

cNO

もしかして:ABC006


ABC115 Christmas Eve Eve Eve


$D$


Christmasに続けて$25-D$回Eveを空白を挟んで出力します。


Perl6(29Byte)

say "Christmas"," Eve"x-get%5


" Eve"と空白を文字列に埋め込んでおけば、正しい位置に空白を入れることができます。

また、$22 \le D \le 25$より$0 \le 25-D \le 3$なので、$25-D \equiv -D \pmod 5$としてよいです。

以上のことより、文字列の繰り返し演算子x" Eve"-get%5回繰り返す上のコードができます。

sayは引数を出力する際に余計なものを挟まないので、これで正しく出力できます。

Perlではx%の優先順位が等しく、' Eve'x-<>%5ではなく' Eve'x(-<>%5)と書く必要が生じるため短くなりませんでした。


ABC116 Right Triangle


$|AB| \quad |BC| \quad |CA|$


$\frac{1}{2}|AB||BC|$を出力します。


Awk(8Byte)

$0*=$2/2


$0は数値としては$1、すなわち$|AB|$と等しいので、これに$\frac{|BC|}{2}$を掛けます。計算結果は正の整数になるので、出力が行われます。


ABC117 Entrance Examination


$T \quad X$


$\frac{T}{X}$を出力します。


Awk(6Byte)

$0/=$2


この問題は、ABC-Aとしては初めて「小数の出力」を求める問題です。

許される誤差が$10^{-6}$やそれより小さな値だと、AWKの組み込み変数OFMTControlling Numeric Output with print参照)を変更して出力する桁数を増やす必要がありましたが、この問題では$10^{-3}$までの誤差が許されており、デフォルトの出力形式で十分ACになります。

ちなみに、小数を出力する際、指数形式で出力してもたいていACになります。


ABC118 B +/- A


$A \quad B$


$B \bmod A=0$ならば$B+A$を、そうでなければ$B-A$を出力します。


Awk(19Byte)

$0=$2+=$2%$1?-$1:$1


$B$に$A$または$-A$を足します。+=を使うことで括弧をなくしています。

$B \bmod A \neq 0$のとき$B-A \neq 0$なので、$0には常に非0の数が代入され、出力が行われます。