はじめに
drken さんの精選過去問 10 問を難解言語の Hexagony で解いてみました.難解言語の Whitespace で解いてみたに続いて難解言語編の第 2 弾です.
コンテストページはこちらです.
仕様を知らないで読んでもつまらないかなと思ったので言語の解説も書きました.やっていることは公式の和訳に近いです.
TL; DR
Whitespace は簡単だった.
いざ出陣
現状,AtCoder では Hexagony を用いることができません(えーん).そのため,今回は C++ でインタプリタを実装し,Hexagony のソースをそこに埋め込む形で提出しました.
インタプリタを作りつつ提出していたので,最初の数問のインタプリタにはバグがあります.もし私のインタプリタを使いたい場合は新しいものからコピペするなどしてください.
まだ実装ミスがあったり仕様の勘違いがあるかもしれません.任意長の整数に対応していないのは甘えですが,許してください.
追記
インタプリタにバグがあることが今さら(2018.08.18)判明しました.直したインタプリタは こちら)
0 問目:PracticeA - はじめてのあっとこーだー(Welcome to AtCoder)
整数 $a$,$b$,$c$ および文字列 $s$ が与えられるので $a+b+c$,' '
,$s$,'\n'
を出力します.
Brainf*ck とは違い,整数の入出力で苦しむことはありません.やるだけです.
↑Whitespace のときのコピペです.
? { ? <
/ { + ' /
@ > ? ' + <
/ , ; 0 P ! /
. / , ; ~ \
, > . ~ <
_ . . .
EOF
が来たら終了する,みたいなことを書いています.
1 問目:ABC086A - Product
整数 $a$,$b$ が与えられるので $a\times b$ の偶奇を判定します.
「$a$ が偶数なら 'Even'
」「$b$ が偶数なら 'Even'
」「それ以外なら 'Odd'
」という方針でもよいですが,面倒なので指示された通り掛け算をすればよいです.
↑Whitespace のときのコピペです.
? { ? ' * \
/ ' 2 * { < .
. % . . . . . .
. . | . > ; v < .
. . . . E > ; \ ; .
. . \ . < O / d < | .
. . . . _ . ; . e .
. . @ . ; ; < ; .
. . ; . . . n .
@ ; 4 g ; < .
. . _ . . .
Odd
は O;d;;
とするだけで出力できます.
2 問目:ABC081A - Placing Marbles
文字 $s_1s_2s_3$ が与えられるので,それらに含まれる '1'
の個数をカウントします.整数として受け取って 9
で割ったあまりを出力してもよいですが,甘えのような気がしたので指示通りやります....というのは面倒だったので甘えをします.
? { 9
. . @ .
' % ! g \
. . . 4
. . ;
数日前に書いたものなのであまり覚えていませんが,9
を踏んでも出力には影響がないのでその先に @
を置く,みたいなことをしているように見えますね....当然のように制御フローを追えてしまっているんですが,読者の方々がどの程度ついてこられているんでしょう.
3 問目:ABC081B - Shift only
$N$ 個の整数 $A_1$ から $A_N$ が与えられるので,それらの二進数表示の trailing zero の最小個数を求めます.
? ' 2 { } z \ .
. / . = ' ' < . _
. . > $ > ? . . < "
. . . . \ # c [ ~ / "
. . . . . . . _ . . . |
. . . . . . . : ' / ! < .
> $ > " % $ > < . ) > g 4 \
. . . . . . % . | . } @ ; < .
. \ . . ] = $ < . . | . . .
. . . . . . . . . { . . .
. . . \ } & z = < . . .
/ } & = * } & \ . . .
> * " ' = \ - . . .
. / # f < = . . .
. > . $ \ | $ .
六角形が大きくなってきましたね.まず,命令ポインタ 123450
にそれぞれ abcdef
でジャンプできることに注意します(Note: a
は 97
です).c
はループになっていて,制御に関する部分のみを抜き出すと以下のようになっています.
/ . . . . . . \ . . .
> . . . . \ . . . .
. / # f < . . . .
. > . $ \ | $ c
c
の部分に $
を置いていいんですが,当時の私はなぜかダメだと思っていました.
$N$ でループするのが面倒なので,入力が $0$ だったら答えを出力して終了するという方式を採っています.今後も同様です.c#
でジャンプした先では trailing zero の個数を求めて,最小を更新するまでをやっていた気がします.
無条件でメモリのどこかをコピーすることができないので,z&
とすることで右から値を取ってきています.左から欲しいときは z~&
などとします.z
である必要は特にありません.
たぶんビジュアライザ的なのを用いるといいんですが,用意できていません.私の提出コードをコンパイルして -d
オプションつきで実行するとそれらしいものが見えるはずなので,よければ試してみてください.
4 問目:ABC087B - Coins
整数 $A$,$B$,$C$,$X$ が与えられるので,$500a+100b+50c=X$ を満たす自然数解 $(a, b, c)$ の個数を数えます($0\in\mathbb{N}$). $a\le A$,$b\le B$,$c\le C$ です.
三重ループを書きたくなかったので工夫をしました.$a$ と $b$ の二重ループをして,$0 \le X-(500a+100b) \le 50c$ なら答えをインクリメントします.実際は $X$ が $50$ の倍数であることが保証されているので,各々 $50$ で割って楽しています.
二重ループもちょっと面倒で,b
が 0
になったら b
に $B$ を代入し,a
をデクリメントする,a
が 0
になったら... みたいなのをちゃんとやる必要があります(それはそう).難解言語的にはたぶん当然なんですが,メモリの特定位置に変数名とかラベルみたいなのがついていないので,こんなのでも大変です.
? ' 1 0 " " ? " & \
/ ' ' " ? " " 2 ' < .
. > ? { 5 0 ' : = { \ .
. . . . . . / . . . . . \
/ g ! ' ' ' < > # c < $ < .
. > 4 ; @ . . _ . . . . . . .
. . > } } . . . . . . . . . \ .
. . ~ / } } f ~ = # . . . . $ . .
. / < > / > . . . . . . . . \ . . .
. > / _ . \ { } ( < . . . . = . . . .
\ ~ ( ' " " & = < > ' " . $ < $ < .
. . . . . . . . _ > } { ) { { { /
. . . . > ~ " - < > { . } \ $ .
. . > < > } . . _ . . $ \ = /
. ~ . _ . . . . . f . . . .
\ - ' . \ . . . $ . . . .
. . . \ + ' * } " * < .
. . . . . . # . > { /
> . 0 # $ \ $ \ | $
大きいですね.
5 問目:ABC083B - Some Sums
整数 $N$,$A$,$B$ が与えられるので,$1$ 以上 $N$ 以下の整数のうちで 10 進法での桁和が $A$ 以上 $B$ 以下であるものの個数を数えます.
? " & ' 1 0 { } } \
/ { } } ? ' " ' ? < .
. . . > { } . . ! g 4 \
. . > < > " c # \ @ ; < .
. . \ . _ . . { < . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. / . . . . . . . . . . . . . { <
. . . . . . . . > { = A & } { { { /
/ . . / $ . \ $ \ + } } { { < . . . .
. . . . . \ . . . . { } { _ \ . . .
$ . . / } } = A ~ & " - < . . . .
/ { { } < . . . . / . < _ > / .
{ . . $ > - ' " = } < > < . .
( / . _ . . . % = / _ . & .
" > ' + { = A & { : { = /
\ . . % { - = { Z ' < .
& . . . . . > . . Z /
> " f # $ \ . . | $
大きいですがスカスカな部分があるのでもう少し圧縮できるかもしれません.やりたくはありません.
最初,何故か 9
で割ったりしていて直すのがつらかったです.
6 問目:ABC088B - Card Game for Two
$N$ 個の整数 $a_1$ から $a_N$ があり,値の大きい方から交互に二人で取り合うことを考えます.このとき,両者の得た整数の合計の差を求めます.
ソートして符号を入れ替えつつ足していけばよいのですが,Hexagony でソートを実装する気にはならなかったので,考察をします.
$N$ 個の整数に重複がある場合を考えます.同じ整数が二つあった場合,両者は交互に取り合うことから,差としては無視することができます.すなわち,各整数の個数の偶奇さえ持っておけばよいことになります.
...以上は Whitespace のときの考察です.Whitespace はメモリにランダムアクセスできていいですね!
今回はランダムアクセスもできず,スタック的なものも持っておけないため,もう少し工夫が必要です.以下のように配列を表現しました.
:
:
x[3] -> \ /
| <- 3
x[2] -> \ /
| <- 2
x[1] -> \ /
| <- 1
マークされていない /
たちは必要に応じて使う一時領域です.最初は 100
を格納し,それをデクリメントしたものを "'
で移動した位置に格納し,...というのを 0
になるまで繰り返して初期化完了です.
入力 $a_i$ をもらったら,$a_i$ が $0$ になるまでデクリメントしながら配列をたどっていき,$0$ になったら $x_{a_i}$ を $a_i - x_{a_i}$ で更新します.その後,添字が $0$ になるまで戻り,次の入力を受け取ります.
入力が EOF
に達したら答えを計算します.配列の各要素が離れているため面倒なのですが仕方ありません.$x_{i+1} > 0$ なら $x_{i+1}$ を $x_{i+1}-x_i$ で更新します.$x_{i+1} = 0$ なら $x_i$ で更新します.添字が 0
になったら配列の終端まで処理し終えたことを意味するので, $x_{101}$ に入っている答えを出力して終了です.配列境界外参照的なものが起きても未定義動作にはなりませんので!
ともあれ,これで $O(N\max a_i)$ で解けました.アクセスがシーケンシャルなせいで計算量がアです.ここで $\max$ はインスタンス内での最大値ではなく,入力として考えられる最大値を意味しています.より適切な記号があったりしますかね?
? d $ / " & ' A \ .
. . . . > _ ( & < . .
. . . > < $ | . . . > =
. > $ \ } ? < > $ > < > (
. . . . . . . _ . \ . _ . .
. \ . . . . . . . . . . . . .
. . . . \ . . . . > { ! g 4 ; @
A & \ . . \ { $ > < > { } = A ~ &
. " < $ < . . . \ . _ . . . . . . .
. . . . . . . . . / . ' " < . . . . .
. . . . . . . . . . . > . \ . . . .
- } = A ~ & } = $ > < . . $ . . .
} = A ~ & ' B & ' \ > . . / . .
& E ' & D ' & C < . . . . . .
. . . . . . . . . < . . . .
. . . . . . > A ~ & . . .
" B ~ & " < > } = - { =
. . . . . _ . . . . .
. . . . . . . . . .
7 問目:ABC085B - Kagami Mochi
$N$ 個の整数 $d_1$ から $d_N$ のうちで unique なものの個数を数えます.実質的に 6 問目と同じというのは無限回言われています.
ただし,更新はこちらの方が楽で,$x_{d_i}$ に A
を格納するだけでよいです(A
でなくてもよいのですが,複数回格納するときには数字は使えないため,適当な英字を用いています).最後は $x_i$ の総和を求め,A
で割って出力します.
? d $ / " & ' A \ .
. . . . > _ ( & < . .
. . . > < $ | . . . > =
. > $ \ } ? < > $ > < > (
. . . . . . . _ . \ . _ . .
. \ . . . . . . . . . . . . .
. . . . . . . . . > { { A ' : !
. . . . . \ { $ > < > { } = A ~ &
. . . . . . . . \ " _ & A = { + ' &
. . . . . . . . . / . ' " < . . . . .
. . . . . . . . . . . > . \ . . . .
. } = A . . } = $ > < . . $ . . .
} = A ~ & ' B & ' \ > . . / . .
& E ' & D ' & C < . . . . . .
. . . . . . . . . < . . . .
g 4 ; @ . . . . . . . . .
" B \ . . . . . . . . .
~ < . . . . . . . . .
. . . . . . . . . .
8 問目:ABC085C - Otoshidama
整数 $N$ と $Y$ が与えられるので,
\left\{\begin{array}{l}
x + y + z = N \\
10000x + 5000y + 1000z = Y
\end{array}\right.
の自然数解($0\in\mathbb{N}$)をひとつ出力します.存在しなければ '-1 -1 -1'
を出力します.
前述の通り,多重ループを回したくないので,ちょっと考えて $O(N)$ のループをします.日本語で解説を書くのがアレなので C++ のソースを以って代えさせていただきます.
#include <cstdio>
int main() {
int N, Y;
scanf("%d %d", &N, &Y);
Y /= 1000;
Y -= N;
for (int x=0; x<=N; ++x) {
if ((Y-9*x) < 0) continue;
if ((Y-9*x) % 4 > 0) continue;
int y=(Y-9*x)/4;
if (y > N-x) continue;
printf("%d %d %d\n", x, y, N-x-y);
return 0;
}
printf("-1 -1 -1\n");
}
わ,色がついてる!(それはそうか)
4 ' " ? " & ' ' \
/ ' : ' 0 d { ? < .
. > - ~ " & ' ' 9 = \
/ ) _ . . . " " ' " < .
. > < > ( ! { P 0 ; " ! {
/ | $ . ! ~ ' ; 0 P ! " ' _
. g \ . > ( { { } * ' - ~ < >
\ . $ \ . . . . . . . . . . > .
\ } { $ \ } } ) ' ' \ . . . . . .
. . . 4 | . . . . . . . . . . .
. . . \ . . " " < . . . . . .
. . . > ; @ . . . . . . . .
P 0 ; " ! g 4 ; @ . . . .
' ; 0 P _ ! } } { } \ .
~ " % < > : ' - ~ < .
. . $ > . ' . . $ >
. . . . . . . . .
9 問目:ABC049C - 白昼夢 / Daydream
文字列を後ろから読んでいって 'maerd'
,'remaerd'
,'esare'
,'resare'
のいずれにもマッチしない部分があれば 'NO'
,先頭までマッチさせ続けられれば 'YES'
を出力します.case-insensitive な愚者にならないように注意しましょう.
チャレンジ開始前はこれが一番鬼門だと思っていましたが,案外なんとかなりました.6 問目の方がつらかった気がします.
\ . . . _ . . . . . . $
\ $ > , < > " ' \ . . . >
. . \ { } / . . " . . . . ]
/ . . . . . . ' < . . . . . <
. . . > Y ; E ; S ; g 4 ; @ / ;
} $ > < . . . . . . . @ ; 4 g / .
/ . . ' / . . . . . . . . . . . . .
/ / . . . . . . . . . . . . . . . . .
/ / \ . _ . } = _ } } } \ $ = } _ } < .
. > r ] < > e ] < > m ] < > s ] < > } / .
/ . . . _ / # d _ / . . _ _ . . _ . . . _ .
. > m ] < > a ] < > e ] < > r ] < > d ] < | $
/ . . . / . . . > d # d / . . . > d # d / <
. . . . _ . . . _ . . . _ . . . . . . . ]
> e ] < > s ] < > a ] < > \ . . . . . >
< . . > d # . > d # d / . . . . . . .
O . . / d # d < . . . . . . > $ \ .
; . . > ] e < > ] r < . . . . . .
N . \ _ . . _ . . . . . < . . .
. / ~ f = } < $ . < . . . . .
. . / ' ' < > ~ < > - = < .
. . > f \ _ . . _ . > { /
. > $ \ ~ # . . $ \ | $
以前のような c#
のようなやり方では領域を一つ破壊してしまう上に文字数を食うので,]
を壁ではさむループをかませることで対処しました.
x ]
のような表現は「今読んでいる文字が x
なら一つ(先頭に向かって)読み進め,正でない値をメモリポインタが指すようにする」「x
でなければ位置はそのままで,正の値をメモリポインタが指すようにする」といったことをする関数の呼び出しです.また,d#
は 'NO'
を出力して終了する noreturn
関数です.
-
'r'
の後に'e'
以外が来たらNO
-
'rem'
が来たら'maerd'
を期待し,'m'
を読んだ分一つ戻る. -
'res'
が来たら'esare'
を期待し,'es'
を読んだ分二つ戻る. -
'm'
の後に'aerd'
以外が来たらNO
-
'e'
の後に'sare'
以外が来たらNO
- ブロックの初めの文字が
[rme]
以外ならNO
- 生き残れば
YES
のようなフローとなっています.'es'
で二つ戻るときに m'
' の一つ分とソースを共有しているのが工夫ポイントの一つです(9 行目の真ん中あたり).'ma'
のように途中で終わってしまっている場合でもうまく NO
判定をしてくれます.
提出コード
1263 ms と,実行時間が少々険しいです.最悪時は std::map
に要素が $3\times 10^5$ 個くらい入っていることになる気がするので,重いだろうなぁといった気持ち.
10 問目:ABC086C - Traveling
はいウィニングラン.普通にシミュレートをします.
dx+dy-dt
を計算しておいて,これが正なら No
,あるいはそれを 2
で割った余りが正でも No
.全部耐え抜けば Yes
.
2 { ? . . \ . .
/ . . > $ < Y ; e
. > . < > { { } ? "
. . . . _ . . . . . .
. . . . . . . . . . . .
. . . . . @ ; 4 g ; o ; N
. \ . . . . . . . . . . ( {
. . . . . . . . . . . . . . .
; s ; g 4 ; @ . . . . . . .
- } = T & { } { { ? " - \
/ - " ? { { { & X = } <
> } = Y & { { = + " \
. . < $ . . < . . .
} < > % " < > - <
. _ . . . _ . .
空間が $O(1)$ でいいとはいえ入力が $10^5$ だとさすがに重くて 519 ms かかってます.あと,下限が 0
なので,EOF
で終了するテクが使えなかったのがほんの少しつらかったかな.
あとがき
疲れましたが,なかなか楽しかったです.しばらくは <
が条件分岐命令に見える病に苦しめられることになるんじゃないかな.