37.50.48

%20 の ブログ

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以外 にできれば分岐ができる。

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

最初に入力を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\) 個かどうかを判定すればよいので明らか。

L ≤ x ≤ y ≤ R

「\(L,R\) が入力として与えられ、整数の組 \((x,y)\) \((L\le x\le R,L\le y\le R)\) であって、指定された条件を満たすものの個数を求める問題」を割と短期間で \(2\) 問見たのでなんか書く。

この記事では、以下のような記法を使う。

  • \(x_i\):非負整数 \(x\) の下から \(i\) 番目のビットの値。x>>i&1
  • \(\mathrm{MSB}(x)\):正の数 \(x\) に対し、\(x_i=1\) となるような最大の \(i\)。

 

問題 \(1\)

ABC138 F - Coincidence

\(L,R\) が与えられるので、\((x,y)\) を数えて \(\bmod 10^9+7\) で出力せよ。

条件

  • \(y\%x=y\oplus x\)
  • \(L\le x\le y\le R\)

制約

  • \(1\le L\le R\le10^{18}\)

条件を言い換えると、「\(\mathrm{MSB}(x)=\mathrm{MSB}(y)\) かつ、各ビットについて \((x_i,y_i)\in\{(0,0),(0,1),(1,1)\}\) を満たす」となる。
これにより、\(x\le y\) は必ず満たされることになるので、\(L\le x\) と \(y\le R\) についてだけ考えればよいということになる。

 

問題 \(2\)

Codeforces Round #597 (Div. 2) F. Daniel and Spring Cleaning

\(L,R\) が \(100\) 個以下与えられるので、それぞれについて \((x,y)\) を数えて出力せよ。

条件

  • \(x+y=x\oplus y\)
  • \(L\le x\le R\)
  • \(L\le y\le R\)
  • (\(x\le y\) でなくてもよい)

制約

  • \(0\le L\le R\le10^9\)

条件を言い換えると、「各ビットについて \((x_i,y_i)\in\{(0,0),(0,1),(1,0)\}\)」となる。よって、\(x=y\) かつ条件を満たすものは \((x,y)=(0,0)\) だけであるので、さらに言い換えができ、
「『\(x\lt2^{\mathrm{MSB}(y)}\)(このとき、必ず \(x_{\mathrm{MSB}(y)}=0\) となる)かつ、各ビットについて \((x_i,y_i)\in\{(0,0),(0,1),(1,0)\}\)を満たすもの』\(\times2\)(\(L=0\) なら、さらに \(+1\))」となる。
これにより、\(L\le x\) と \(y\le R\) についてだけ考えればよいということになる。

 

解法

「上位ビットから順に見て、\(i\) ビット目まで見た段階で、既に \(y\) の MSB が確定し、それ以降のビットを正しく埋めれば \(L\le x\le y\le R\) を満たすことができる、\((x_{\cdots,i+2,i+1,i},y_{\cdots,i+2,i+1,i})\) の個数」について DP をするために、次の \(4\) つの変数を用意する。
これらは、\(a,b,c,d\) から \(a',b',c',d'\) を計算し、\(a,b,c,d\) に \(a',b',c',d'\) を代入するようにして使う。

  • \(a\):\(L\le x\le y\le R\)
  • \(b\):\(L\le x\le y\lt R\)
  • \(c\):\(L\lt x\le y\le R\)
  • \(d\):\(L\lt x\le y\lt R\)

例えば \(c\) は、\(x\) が \(L\) を上回ることが確定しているが、\(y\) が \(R\) を下回ることが確定していないものについて数えるための変数である。
\(R_i=1\) のときに \(y_i=0\) にすれば、\(y\) が \(R\) を下回ることが確定するので、以降は \(d\) として数えることになる。

等号が外れるかどうかで分岐したいので、\(a\) からの遷移では \(L_i\) と \(R_i\) に注目し、\(b\) からの遷移では \(L_i\) に注目し、\(c\) からの遷移では \(R_i\) に注目する。

問題 \(1\) では、\(\left\lfloor\dfrac L{2^i}\right\rfloor\le1=1\le\left\lfloor\dfrac R{2^i}\right\rfloor\) のときに MSB として \((x_i,y_i)=(1,1)\) にすることができ、\(\le\) の等号が成立するかどうかで \(a,b,c,d\) のどれに該当するかを判定する。

問題 \(2\) では、\(\left\lfloor\dfrac L{2^i}\right\rfloor=0\lt1\le\left\lfloor\dfrac R{2^i}\right\rfloor\) のときに \(y\) のMSB として \((x_i,y_i)=(0,1)\) にすることができ、\(\le\) の等号が成立するかどうかで \(a,b\) のどちらに該当するかを判定する。

 

\(4\) つの変数を使うよりも、\(2\) つの bool 値を添え字とする配列を使ったほうがいい気がしているが、それについてはまだやってないので分からない。