Hatena::Grouptopcoder

ぷろこんメモ用紙

 | 

2012-05-25

Codeforces Surprise Language Round #6

02:56

いつのまにか名前が変わっていたSurprise Language Round.

今回はRoco.とにかくコルーチンで全てを書く言語.らしい.

5位以内に入るとTシャツがもらえる.

ABCDEFGHTotalPlace
00:0700:2500:2200:3000:3700:5301:28(+1)01:3838036th

無理.

変にハマらなければ30位くらいにはなれたっぽいけど,それ以上のスコアは出せる気がしない.

基本方針としては,コルーチンであることを無視して関数っぽく書く.

関数の引数とか返り値の受け渡しは,脳内で適当にエリアを割り当ててやる.

A - Hexagonal Numbers

インタプリタを落としてきて,ソース1つだけというミニマルさにびびる.

とりあえず言語仕様を眺める.変数は全部アドレス直指定なのね.

サンプルをいくつか見て書き方を覚える.

Aは計算するだけだし書けるだろう.AC

iin [0]
mul [1] [0] [0]
mul [1] 2 [1]
sub [1] [1] [0]
iout [1]
ac

C - LCM

問題一覧を見たらCを先に解いてるっぽい人がいて,名前的にも簡単そうだし先にこっちをやってみる.LCMを求めるだけ.

とりあえずGCD書けばいいんだよね…….

ハマる.

ちゃんとサンプルを読んでいなかったせいで,コルーチンは勝手にループするというのを理解していなくて頑張って再帰を書こうとしていた.

気分転換にサンプルを読んだらAC

co gcd {
    mod [2] [0] [1]
    set [0] [1]
    set [1] [2]
    eq [4] [1] 0
    if [4]
    ac
}

co swap {
    set [2] [0]
    set [0] [1]
    set [1] [2]
    yi ro
}

iin [0]
iin [1]
mul [3] [0] [1]
gt [2] [1] [0]
if [2]
yi swap
ca gcd
div [3] [3] [0]
iout [3]
ac

B - A + Reverse B

Cで無駄に時間食ったのでさくっと通したい.

2つの数AとBが与えられて,A+B.to_s.reverse.to_iを求める問題.

逆転させるだけ?ループ書ける今となっては余裕.

このへんで,フラグ変数は大きい数字にしといて脳内セグメント分けするテクニックを思いつく.

co inv {
    mul [2] [2] 10
    mod [3] [1] 10
    add [2] [2] [3]
    div [1] [1] 10
    eq [100] [1] 0
    if [100]
    ac
}
iin [0]
iin [1]
ca inv
add [0] [0] [2]
iout [0]
ac

D - Asterisks

i行目にはi個のアスタリスク,をN段出力する問題.

これもやるだけ.

ループの終了判定にeqを挟まないといけないのがちょっと面倒臭く感じてくる.eqの後にif書くの忘れがちだし…….

co ast {
    cout 42
    dec [1]
    eq [100] [1] 0
    if [100]
    ac
}
co loop {
    set [1] [2]
    ca ast
    cout 10
    inc [2]
    eq [100] [2] [0]
    if [100]
    ac
}

iin [0]
inc [0]
set [2] 1
ca loop
ac

E - HQ9+

HQ9+のプログラムが何かを出力するか判定する.

HQ9のどれかがあればYES.

終端判定どうすんだろ,と思ったら改行を見るらしい.

co yes {
    cout 89
    cout 69
    cout 83
    cout 10
    ac
}
co no {
    cout 78
    cout 79
    cout 10
    ac
}
co ans {
    if [200]
    yi yes
    yi no
}

cin [0]
eq [100] [0] 10
if [100]
yi ans

eq [100] [0] 72
add [200] [200] [100]
eq [100] [0] 81
add [200] [200] [100]
eq [100] [0] 57
add [200] [200] [100]

F - Binary Notation

与えられた数の2進表記を求める問題.

Nを超えない2の冪を求めてシフトしながら比較するだけ……と思いきやハマる.

0と1の出力をyieldで分けると継続渡しみたいになってきれい!と思って書いたら,コルーチンの復帰をちゃんと理解してなくて1の後のyieldは常に0が出力されるようになって,原因究明に時間を食う.

最終的には諦めて,マスクとの比較結果の0/1に48を足したものを出力するようにした.

co ordret {
    div [1] [1] 2
    ac
}
co ord {
    gt [100] [1] [0]
    if [100]
    yi ordret
    mul [1] [1] 2
}

/**ハマったやつ**/
co out1 {
    cout 49
    ac
}
co out0 {
    cout 48
    ac
}
co binout {
    if [100]
    yi out1
    yi out0
}
/*****************/

co bin {
    lt [100] [0] [1]
    sub [101] 1 [100]
    add [102] 48 [101]
    cout [102]
    if [101]
    sub [0] [0] [1]
    div [1] [1] 2
    eq [100] [1] 0
    if [100]
    ac
}

iin [0]
set [1] 1
ca ord
yi bin

G - Array Sorting

数列をソートする.

アドレスにオフセットかけるの面倒臭そうだし0からを配列に割り当てよう,ということで100番台をワーキングエリアにする.

ソートはバブルソート書けばいいよね……でハマる.

終端判定をltとgtだけで書こうとかよく分からないことをしていたせいで,境界条件をミスってoff-by-one errorが多発(外側のループ回数が1回足りなかったり,内側が1回多くて0を持ってきてしまったり).普通にeqも使ってand取ればよかったのに…….

あとacはコルーチンの末尾に持ってこないと,次回呼び出しの際の挙動が関数的でなくなることにようやく気づく.

書き上げて投げたらWA.要素数1のときおかしかったのでad-hocに対処.

co input {
    iin [[101]]
    inc [101]
    eq [102] [101] [100]
    if [102]
    ac

}

co swap {
    set [200] [[102]]
    set [[102]] [[103]]
    set [[103]] [200]
    ac
}
co inner {
    /*
    cout 105
    cout 32
    iout [102]
    cout 10
    */

    add [103] [102] 1 /* cmp 102 and 103 */
    gt [104] [[102]] [[103]]
    if [104]
    ca swap
    inc [102]
    add [104] [102] 1
    lt [104] [104] [101]
    sub [104] 1 [104]
    if [104]
    ac
}

co outer {
    /*
    cout 111
    cout 32
    iout [101]
    cout 10
    */

    set [102] 0
    ca inner
    dec [101]
    eq [102] [101] 0
    if [102]
    ac
}

co print {
    iout [[101]]
    cout 32
    inc [101]
    eq [102] [101] [100]
    if [102]
    ac
}

iin [100]
set [101] 0
ca input

set [101] [100]
gt [102] [101] 1
if [102]
ca outer
set [101] 0
yi print

H - Stack

逆ポーランド計算機を実装する.

え,スタック書くだけ?これGより簡単なんでは…….

適当に書いてAC

co ans {
    dec [200]
    iout [[200]]
    ac
}

co plus {
    dec [200]
    set [300] [[200]]
    dec [200]
    set [301] [[200]]
    add [[200]] [300] [301]
    inc [200]
    ac
}

co mul {
    dec [200]
    set [300] [[200]]
    dec [200]
    set [301] [[200]]
    mul [[200]] [300] [301]
    inc [200]
    ac
}

co num {
    sub [100] [100] 48
    set [[200]] [100]
    inc [200]
    ac
}

cin [100]
eq [101] [100] 10
if [101]
yi ans

eq [101] [100] 43
if [101]
ca plus

eq [101] [100] 42
if [101]
ca mul

gt [101] [100] 47
lt [102] [100] 59
and [101] [101] [102]
if [101]
ca num
 |