yukicoder No.1852 Divide or Reduce

この記事は yukicoder No.1852 Divide or Reduce の解説です。

操作 Y が行えない状況の場合、山同士は互いに影響を与えない、独立したゲームです。
独立したゲーム（二人で交互に操作する手番が来るようなゲーム）が複数ある場合、その状況に対する Grundy 数は、独立したそれぞれのゲームに対する Grundy 数たちの bitwise xor（ \(\oplus\) で表します。）によって計算できます。
列 \(a\) に対し、操作 Y が行えないと仮定した場合の（嘘の）Grundy 数を \(g(a) = g(a_1) \oplus g(a_2) \oplus \cdots \oplus g(a_{|a|})\) と表すことにします。
列 \(a\) に対し、操作 Y も考慮した本当の Grundy 数を \(G(a)\) と表すことにします。

• \(G(a) \ne 0\) ならば手番のプレイヤーが勝ち
• \(G(a) = 0\) ならば手番のプレイヤーが負け

です。
よって、初期状態の列 \(A\) に対する Grundy 数 \(G(A)\) が \(0\) かどうかが分かればよいということになります。

\(\mathrm{mex}\) を（可変個の）引数に含まれない最小の非負整数を返す関数とします。
\(g\) について計算してみると、

• \(g(1) = \mathrm{mex}(\emptyset) = 0\)
• \(g(2) = \mathrm{mex}(g(1) \oplus g(1)) = \mathrm{mex}(0) = 1\)
• \(g(3) = \mathrm{mex}(g(1) \oplus g(2)) = \mathrm{mex}(1) = 0\)
• \(g(4) = \mathrm{mex}(g(1) \oplus g(3), g(2) \oplus g(2)) = \mathrm{mex}(0,0) = 1\)
• \(g(5) = \mathrm{mex}(g(1) \oplus g(4), g(2) \oplus g(3)) = \mathrm{mex}(1,1) = 0\)
• \(\vdots\)

のようになり、

• \(g(奇数) = 0\)
• \(g(偶数) = 1\)

であることが分かります。

• \(\min(A) = 1\) のとき
• 操作 Y はできないので、初期状態の列 \(A\) に対し、\(G(A) = g(A)\) です。
• よって、どちらが勝つか分かります。
• \(\min(A) \gt 1\)のとき
• \(g(A) = 1\) のとき
• 操作 X を行い、操作後の列 \(A'\) が \(g(A') = 0\) を満たすようにできます。
• さらに、操作対象の \(A_i\) を \(A_i-1\) と \(1\) に分割することによって \(\min(A') = 1\) にできるので、\(G(A') = g(A') = 0\) を満たすようにすることができます。
• \(G(A') = 0\) となるように操作できる状態だったので、初期状態に対する Grundy 数は \(G(A) \ne 0\) であったことが分かります。
• \(g(A) = 0\) のとき
• 操作 X を行うと、操作後の列 \(A'\) は \(g(A') = 1\) を満たします。\(g(A') = 1\) のとき \(G(A') \ne 0\) なので、これは相手を勝たせてしまう操作になります。
• ということで、操作 Y を行うのが最善です。操作 Y を行うと列の要素のそれぞれが偶奇反転されます。
• 要素数 \(|A|\) が奇数のとき
• 必ず \(g(A') = 1\) になるので \(G(A) = 0\) です。
• 要素数 \(|A|\) が偶数のとき
• \(g(A') = g(A) = 0\) なので、手番の人が操作 Y を行うことを \(\min(A)-1\) 回繰り返すことになります。
• ということで、\(\min(A)\) の偶奇が分かればよいです。
• \(\min(A)\) が偶数のとき、\(G(A) \ne 0\)
• \(\min(A)\) が奇数のとき、\(G(A) = 0\)
• です。

\(\min(A) \gt 1\) を満たす入力しか来ないつもりで実装しても、\(\min(A) = 1\) の場合も上手くいきます。

実装例（C++17）

TSG LIVE! 5 2日目のコードゴルフの問題をStarryで解いた

うらさんの記事 を参考にしました。

 

Starryの標準入力の仕様について詳しくなかったので調べた。

この言語のインタプリタはRubyで実装されていて、入力に関する部分は次のようになっている。

      when :char_in
        push($stdin.getc.ord)
      when :num_in
        push($stdin.gets.to_i)

EOFを読み込むと、char_in では undefined method `ord' for nil:NilClass (NoMethodError) となってエラー終了するのに対し、
num_in では nil が整数に変換され、スタックに 0 が積まれる（終了しない）。

EOFで自動的に終了してくれたほうが楽なので char_in を使って書いた（83B）

          + + +  * +  **` + , ,  + ,  ** +   +   * +. +   +  *   +      + *  * * +'

今回の問題では大小比較をして 0 または 1 を作りたいので、大きめの整数 x を使って (a+x)/(b+x) のような切り捨て除算をするという方法が考えられる。

, , + , ** の部分が入力を読む部分で、改行の文字コードが 10 なのを利用して、十の位を表す数字の文字コードを10倍するのに使っている。

（例："39\n" は文字コード列では 51,57,10 なので、57+51*10=567）

これにより、10～99は538～627に変換される。

最初に仮の最小値としてよい値は627～1075ということになる。上のコードでは5+(5^2)^2=630にした。

入力の最初の要素が98か99のとき以外なら625でも通るという嘘解法をすると3B縮む。

Pythonでいうとこんな感じ（意訳）

a=630
while True:
    b=int(input())+528
    c=a//b
    print(c,end='')
    a=b*c-a*(c-1)

 

num_in を使ってみたが、長かった（92B）

          + +* +  * +* +,`          + +* +  ** +   +   * +. +   +  *   +      + *  * * +, +'

意訳

a=200
b=int(input())
while b!=0:
	b+=100
    c=a//b
    print(c,end='')
    a=b*c-a*(c-1)
    b=int(input())

200を作るために100を経由するので、スタックに常に100を残しておけば縮むかも？という気はするが、dupしかないのでつらい。

追記

なんかめっちゃ縮んだ（37B）

,`      + `. +, +   +   *'     +  + '

割り算した結果を 0 または 1 にする必要はなくて、0 または 0以外 にできれば分岐ができる。

0 や 1 をスタックに積むのは短く書けるので書けばよい。

最初に入力を1回読んで無条件で 1 を出力するようにして、そこにラベルを設置した。

num_in だとEOFを読むだけでは終わってくれないが、今度はゼロ除算で終わってくれるようになった。めでたしめでたし。

五月祭2020 Live CodeGolf Contest Day2 参加記

TSG LIVE! 5（2日目）のライブコードゴルフ大会に、こたつがめさんとともに外部ゲストプレイヤーとして参加させてもらいました。

TSG LIVE! でコードゴルフ大会が行われていることは以前から知っていて、参加したいと思っていたので、参加できる機会を与えてくださったことに感謝しています。

リンク

• アーカイブ動画
• こたつがめさんによる参加記（この記事を書き終わってから存在を知ったので、この記事に載っている情報は若干古いです）

競技規則

• 競技時間は75分
• 出力の空白・改行は余計にあってもよい
• 出力が正しければエラー終了でもよい
• 出力が正しく言語内最短を更新したときのみマスをとれる
• 自分チームがとったマスと隣接するマスにのみ提出できる
• 自分チームの提出コードは見ることができる
• 相手チームの提出コードは見ることができない
• 相手チームの提出言語、ジャッジ結果、コード長、提出時刻、提出者名は見ることができる
• チームメイトとテキストでコミュニケーションをとってもよい

参加記

C

こたつがめさんが開始から3分で提出（55B）

main(a,p){for(;~scanf("%d",&a);)puts(p>a?p=a,"1":"0");}

ぱっと見で縮みそうなところがなかったので放置していた。結局これが最後まで最短として残った。

Ruby

とりあえずできたので提出した（38B）

x=100;p *$<.map{x>(a=_1.to_i)?a/x=a:0}

入力はランダムに1ケース作られるだけなので初期値を 99 にしてもバレなさそう（37B）

x=99;p *$<.map{x>(a=_1.to_i)?a/x=a:0}

p を内側に入れて * を消した（36B）

x=99;$<.map{p x>(a=_1.to_i)?a/x=a:0}

文字列として扱ったほうが短いよね（32B）

x=?:;$<.map{p x>_1 ? (x=_1;1):0}

まだ縮むような気もするが競技時間は75分しかないので別の言語へ。

後に相手チームのうらさんが提出したコード（31B）

s=?@
$<.map{p _1<s ?(s=_1;1):0}

それはそう。Rubyでは ? がいろいろな意味を持つので、条件演算子の ? の前後にスペースが必要になる場合があるが、この条件がややこしいので、分からなければ全部試すというのが有効で、きちんと試し切っていれば31Bにできていた。

Go

こたつがめさんがやっていた。Goに詳しくないので見ても分からないだろうと思い、ほとんど見ていない。

序盤にとりあえず提出し、終盤に縮めたようだ（87B）

package main
import."fmt"
func main(){p:=100;for{a:=0;Scan(&a);if p>a{p=a};Print(p/a)}}

Python3

Pythonは相手チームにも提出権があり、しかもRubyと似ているのでとりあえず提出した（54B）

x=':'
while 1:
 t=input()
 u=x>t
 if u:x=t
 print(u+0)

バージョンを確認していなかったので := をcheckerで試した結果、使えないらしいという結論を得ていた。

が、これは勘違いで、すぐにこたつがめさんが := を使って縮めていた（52B）

x=':'
while t:=input():
 u=x>t
 if u:x=t
 print(u+0)

:= を使って縮むところがもう1か所（50B）

x=':'
while t:=input():
 if u:=x>t:x=t
 print(u+0)

単項の + でも整数に変換できるらしい（49B）

x=':'
while t:=input():
 if u:=x>t:x=t
 print(+u)

後に相手チームのhakatashiさんが提出したコード（48B）

j="Z"
for n in open(0):j=min(j,n);print(1-(j<n))

Python3ゴルフで入力を読み込む常套手段である open(0) を利用しているが、実は while t:=input(): と for n in open(0): の字数は同じ。

今までに見た中での最小値を更新してしまってから更新があったかどうかを判定しているのが短縮ポイントらしい。

Perl

相手チームはPerlの提出権がないのでGolfScriptをやろうとしていたが、できなかったのでPerlをやった。

とりあえず提出したコード（29B）

print$~gt$_?$_/($~=$_):0for<>

$~ は初期値が "STDOUT" なので、"99\n" よりも辞書順で大きい。結局これが最後まで最短として残った。

終了後の今見ると、ジャッジ環境の $$（PID）の値次第だが縮む可能性がある（28B）

print$$>$_?$_/($$=$_):0for<>

GolfScript

こたつがめさんがやっていた（27B）

今までにGolfScriptを触った経験から、もっと縮むはずと思っているので詳細は省略。

相手チームが提出してこなかったので一応勝ちは勝ち。

Crystal

こちらのチームがGolfScriptに提出したのを見て相手チームが防衛のために縮めていたらしい。

元々のコード（60B）

j=99
while l=read_line.to_i
p(if j > l
j=l;1
else
0
end)
end

縮めた後のコード（42B）

j="Z"
STDIN.each_line{|n|p j>n&&(j=n)?1:0}

見るからに入力を読み込む部分が長いなぁという印象。

Crystalは一応書いたことはあるものの、入力の読み込み方を忘れたので調べてみると、gets でできるらしい。

後置 while や $_（gets で読み込んだ文字列が自動的に代入される変数）がないことに対して不便だなぁと思いながら適当に書いたら相手チームより短かった（39B）

x=":"
while s=gets
p x>s ?(x=s;1):0
end

直後にこたつがめさんが1B縮めた（38B）

x=":"
while a=gets
p x>a ?(x=a;1):0end

Whitespace

相手チームの提出権がないので急ぐ必要はないものの、残り時間も減ってきたのでやった（79B）

スペースを S、タブを T、改行を N に変換したコードで解説する。

コード	意味	備考
SS(S)[TTSSTSS]N	push 100	(S)=+,[TTSSTSS]=100
NSS[]N	label ""	ラベル名は空にできる
SNS	dup
SNS	dup
SNS	dup
TNTT	readnum	整数の入力を1行読み込み、配列の(top of stack)番目に代入する
TTT	retrieve	配列の(top of stack)番目の値をスタックに載せる
STS(S)[T]N	copy 1	(S)=+,[T]=1
TSST	-	(読み込んだ値)-(現在の最小値)
NTT[S]N	jump(<0) "S"
SS(S)[]N	push 0	0の場合は符号だけで可
TNST	writenum
NSN[]N	jump ""
NSS[S]N	label "S"
TTT	retrieve	もとの最小値が今スタックトップにあることを利用
SS(S)[T]N	push 1
TNST	writenum
NSN[]N	jump ""

以前は古いPCでWhitespace用のエディタを自作して使っていた（バックアップはとっていなかった）のだが、そのPCが割と最近壊れたので、メモを紙に書いた後、普通のエディタで書いた。その結果、少し間違えた（ちょうどその部分が放送で映されている）。

終了後に見返すと、自明な無駄と容易な改善方法があって、計6B縮む。

3連続dupは1回余計で、全く使われることなく残ってしまう要素があるので2連続dupでよい（76B）

分岐の仕方を、a-b<0?c:d から b-a<0?d:c に変えることで、copy 1 の代わりに dup が使えるようになる（73B）

コード	意味	備考
SS(S)[TTSSSTT]N	push 99
NSS[]N	label ""
SNS	dup
SNS	dup
SNS	dup
TNTT	readnum
TTT	retrieve
TSST	-	(現在の最小値)-(読み込んだ値)
NTT[S]N	jump(<0) "S"
TTT	retrieve
SS(S)[T]N	push 1
TNST	writenum
NSN[]N	jump ""
NSS[S]N	label "S"
SS(S)[]N	push 0
TNST	writenum
NSN[]N	jump ""

><>

Whitespaceの前に書こうか迷っていた。こたつがめさんが46B、45B。たぶんまだ縮むので詳細は省略。

相手チームの提出権がないので縮める必要もなかった。

この言語の厄介なところは、入力を1Bずつしか読み込めないことと、エラーメッセージが全て同じことで、命令が豊富な割に、書いてみると結構つらい。

Node.js

よく知らない。相手チームがやっていた。提出権はあったのでやろうとしても良かったかもしれない。

Starry

終盤でCrystalをとったことで提出権を得たが、時間が足りないのでやろうとしなかった。

分岐命令が !=0 しかないので書きづらいが、方針は立っているのでそのうちやりたい（やるとは言ってない）

yukicoder No.731 等差数列がだいすき

この記事は、yukicoder No.731 等差数列がだいすき の解説です。

\(0\)-indexed とする。\(\sum\) はすべて \(\displaystyle\sum_{i=0}^{N-1}\) の略として用いる。

最小二乗法は分からないので次のように式変形する。

\(\sum(a_i-b_i)^2\\ =\sum(a_i-(b_0+di))^2\\ =\sum(a_i^2+b_0^2+d^2i^2-2a_ib_0+2b_0di-2a_idi)\\ =Nb_0^2+(\sum2i)b_0d+(\sum i^2)d^2+(\sum-2a_i)b_0+(\sum-2a_ii)d+(\sum a_i^2)\)

これにより、\(b_0\) と \(d\) についての \(2\) 変数関数が得られた。これを \(f(b_0,d)\) とする。

一般に \(2\) 変数関数 \(F(x,y)\) が \((x,y)=(a,b)\) で極値をとるとき、\(F_x(a,b)=0\) かつ \(F_y(a,b)=0\) が成り立つ（逆は成り立つとは限らない）。
（ここで、\(F_x\) は \(x\) 偏微分、\(F_y\) は \(y\) 偏微分）

ジャッジ形式を見ると、出力が一意に定まることが分かるので、\(f(b_0,d)\) には極値があり、それを求めればよいことが分かる。
\(b_0,d\) のそれぞれで偏微分すると、どちらも \(b_0^2,b_0d,d^2\) の項が消え、\(b_0,d\) の項と定数項だけが残るので、あとは普通に \(2\) 元 \(1\) 次連立方程式 \(\begin{eqnarray} \left\{ \begin{array}{l} f_{b_0}(b_0,d)=0\\ f_d(b_0,d)=0 \end{array} \right. \end{eqnarray}\) を解けば、極値をとる \(b_0,d\) の値が求まる。

yukicoder No.680 作れる数

この記事は yukicoder No.680 作れる数 の解説です。

問題文を読解すると、

\(29\) 要素からなる数列 \(A=(2^1-1,2^2-1,\cdots,2^{29}-1)\) が与えられる。 \(A\) の中からいくつかの要素を選び、それらの総和をちょうど \(N\) にする方法は存在するか？

という問題を解けばよいことが分かる。

要素数が少ないので（要素の特徴を無視して）半分全列挙して二分探索すれば解ける。

yukicoder No.515 典型LCP

この記事は、yukicoder No.515 典型LCP の解説です。

遅い解法だが、C++で実装した場合、実行時間制限には間に合う。
ローリングハッシュを使ったいくつかの解法がチャレンジケースで落ちたらしいが、Trie を使えば同様のことがローリングハッシュよりは高速にできる。

生配列で Trie を作る。int Trie[800001][26];（ vector<vector<int>> でもよいが生配列のほうが速い）
今までに作った頂点数を覚えておいて、初めて見る接頭辞が来た時に頂点を増設するようなイメージでやる。

各文字列に対して Trie を辿った頂点番号の列を覚えておく。これを \(d\) とする。
サンプル \(1\) に対しては \(d\) の値は次のようになる。

• \(d_1=(0,1,2,3,4,5,6,7)\)
• \(d_2=(0,1,8,9,10)\)
• \(d_3=(0,11,12,13,14,15,16,17,18)\)
• \(d_4=(0,1,8,9,19,20,21,22)\)

\(2\) つの文字列 \(s_i,s_j\) が長さ \(k\) 以上の共通接頭辞をもつとき（に限り）、\(d_{i,k}=d_{j,k}\)（ \(k\) は \(0\) -indexed）となるので二分探索ができる。

クエリの回数が \(M \le 3 \times 10^6\) と非常に多いので、

for k in 1 .. M
    略
    x = (x + d) % (n * (n - 1))

を

nn = n * (n - 1)
x %= nn
d %= nn
for k in 1 .. M
    略
    x += d
    if x >= nn:
        x -= nn

にするだけで 200 ms ぐらい速くなる。

実装列 #427272

yukicoder No.832 麻雀修行中

この記事は、yukicoder No.832 麻雀修行中 の解説です。

\(H[i]=\)「牌 \(i\) の枚数」とする。
各牌がアガリ牌かどうかを判定するために、以下のようにする。

その牌が元々 \(4\) 枚ある牌の場合、（この問題の定義では）アガリ牌ではないので判定対象から除外する。
実際にその牌を追加する（ \(H[i]+=1\) ）（後で元に戻す）。
雀頭（ジャントウ：問題文でいう「 AA 」）を仮定する。
同じ牌を \(2\) 枚使うので、\(2\) 枚以上ある牌だけが雀頭の候補となる。
雀頭にした牌を \(2\) 枚使う（ \(H[i]-=2\) ）（後で元に戻す）。
アガリ牌と雀頭を仮定すると、残り \(12\) 枚を \(4\) 面子（メンツ：\(3\) 枚 \(1\) 組のやつ）に分けることになる。
\(111222333\) は、\(\{123,123,123\}\) の代わりに \(\{111,222,333\}\) と解釈することができるので、同じ順子（シュンツ：\(123\) や \(567\) など）は \(2\) 個までしかないと決めつけてよい。

次のような DP を考える。

• \(dp[i][j][k]=\)「牌 \(i\) まで見て、順子の先頭が \(j\) 個、順子の真ん中が \(k\) 個あるという状態を作れるかどうか」

ここで、「先頭」は例えば \(567\) の \(5\)、「真ん中」は例えば \(234\) の \(3\) を指す。
次のように初期化する。

• \(dp[0][0][0]=\mathrm{true}\)
• \(dp[0][j][k]=\mathrm{false}\)（ \((j,k)\ne(0,0)\) のとき）

順子の先頭や真ん中として使う牌を決めたとき、それより \(1\) 大きい牌を予約したことになる。予約されているはずの牌が足りなければ無効な遷移である。
予約された牌を使い終わって残った牌の枚数が \(3\) 以上なら \(3\) 枚で刻子（コーツ：\(222\) や \(999\) など）ができる。
よって、次のような遷移になる。

• for \(i\) in \(1\cdots9\)
• for \(j\) in \(0\cdots2\)
• for \(k\) in \(0\cdots2\)
• \(t=H[i]-j-k\) として、\(t\ge0\) のとき、\(dp[i][t\%3][j]|=dp[i-1][j][k]\)

\(dp[9][0][0]=\mathrm{true}\) ならば仮定は正しい。

七対子は \(H[i]=2\) となる \(i\) の個数が \(7\) 個かどうかを判定すればよいので明らか。