何をするのか
IchigoJamでAtCoder Beginner Contest 005の問題を解くプログラムを作ります。
AtCoderの問題とは
- 何をするのか
- どのような入力が与えられるのか (形式と範囲)
- どのような出力をするのか
- 実行にどのくらいの時間とメモリを使えるか
が指定され、条件に合うプログラムを書くという問題です。
AtCoderには簡単な問題から難しい問題まで様々な問題がありますが、
今回は簡単な問題が多いAtCoder Beginner Contestの問題を解いてみました。
いかに入力を得るか
今回はシリアル通信を用いて入出力をすることにします。
出力には、素直にPRINT命令を使うことができます。
しかし、入力は単純にはいきません。
ここでは、今回解く問題で出てくる「1～100の整数」を読み込むことのみを考えます。
まず、INPUT命令を使うことを考えてみます。
INPUT命令を使うと数値を読み込むことができますが、余計な?が出力されてしまいます。
AtCoderでは、余計な出力をするとWrong Answer(出力が求めるものと違う)という誤答になってしまいます。
さらに、INPUT命令では空白区切りの整数をうまく読み込むことができないようです。
したがって、INPUT命令は使えません。
次に、INKEY()関数を使うことを考えてみます。
INKEY()関数は、シリアル通信を1文字ずつ受信することができます。
しかし、INKEY()命令では、今回の読み込み処理には遅いと考えられます。
経験上、IchigoJamのシリアル通信は、
1文字あたり20ミリ秒程度のウェイトを入れて送信しないと文字がこぼれてしまうようです。
今回は、多い時は800文字以上を読み込み、2秒以内に答えを出さないといけない問題があります。
1文字を渡すのに20ミリ秒かかっていたら、800文字では16秒もかかってしまい、余裕でオーバーしてしまいます。
したがって、IchigoJamの標準機能であるINKEY()関数は使えません。
というわけで、今回はマシン語を使って読み込むことにします。
今回入力に出てくる整数は1～100のみなので、1バイトで表せます。
そこで、最初に入力を全部読み取ってしまい、VRAMに置いておくことにしました。
今回用いるのは以下のコードです。
@START
R3 = PC + 128
PUSH {R4, R5, R6, R7, LR}
' R7にVRAMの先頭アドレスを入れる(コードが#700から置かれている前提)
R7 = R3
' R6にUSART操作レジスタの先頭アドレス(#40008000)を入れる
R6 = #40
R6 = R6 << 16
R6 += #80
R6 = R6 << 8
' USART受信割り込みをオフにする
R1 = [R6 + 1]L
PUSH {R1}
R0 = 1
BIC R1, R0
[R6 + 1]L = R1
' ここに入力処理を書く
@LOOP
GOSUB @GETINT
R0 & R0
IF !0 GOTO @LOOP
' 復帰処理
POP {R1}
[R6 + 1]L = R1
POP {R4, R5, R6, R7, PC}
' シリアルポートから数値を1個読み込んでR7の指す場所に格納し、R7をインクリメントする
' 読み込んだ数値を返す
@GETINT
R0 = 0
R2 = 10
' シリアルポートに入力が来るまで待機する
@GETINT_LOOP
R1 = [R6 + 5]L
R1 = R1 >> 1
IF CC GOTO @GETINT_LOOP
' 来た入力を読み込む
R1 = [R6 + 0]
' 入力の文字を数値に変換する
R1 -= 48
' 空白や改行が来たら今回の読み込みを終わる
IF MI GOTO @GETINT_END
' 入力を反映させる：R0 = R0 * 10 + R1
R0 *= R2
R0 = R0 + R1
' 次の文字を読みに行く
GOTO @GETINT_LOOP
@GETINT_END
' 読んだ数値をメモリに書き込む
[R7 + 0] = R0
' 書き込む位置を進める
R7 = R7 + 1
RET
「ここに入力処理を書く」～「復帰処理」の部分は問題によって変え、残りは共通です。
読み取る個数は入力に依存して事前にわからないことがあるため、問題固有の部分が必要になります。
この例では、0が入力されるまで入力を読み取る処理を入れています。
USART受信割り込みを無効にしておかないと、入力のうち大部分の文字が読み取れませんでした。
IchigoJam標準機能の方に入力が取られてしまっているのであると考えられます。
実際に問題を解く
以下、「何をする問題か」は、問題を解釈した内容を書いています。
もともとの問題文は、それぞれの問題ページを参照してください。
A - おいしいたこ焼きの作り方
何をする問題か
2個の整数が与えられるので、割り算(小数点以下切り捨て)した商を出力する。
解法
素直に割り算をする。整数の割り算はIchigoJamの標準機能でできる。
入力用マシン語の固有部分
' ここに入力処理を書く
GOSUB @GETINT
GOSUB @GETINT
ソースコード
10 'ABC005 A
20 POKE#700,127,163,224,181,31,70,64,38,54,4,128,54,54,2,113,104,13,70,1,32,129,67,113,96,0,240,4,248,0,240,2,248,117,96,224,189,0,32,10,34,113,105,73,8,252,211,49,120,48,57,2,212,80,67,64,24,246,231
30 POKE#73A,56,112,127,28,112,71
40 A=USR(#700,0)
50 X=PEEK(#900)
60 Y=PEEK(#901)
70 PRINT Y/X
B - おいしいたこ焼きの食べ方
何をする問題か
整数のリストが与えられるので、最小値を出力する。
解法
暫定の最小値をリストの最初の値で初期化し、リストの値を順に見ていく。
見た値が暫定の最小値より小さければ、暫定の最小値を見た値に更新する。
リストを見終わったら、暫定の最小値が最小値になっている。
入力用マシン語の固有部分
' ここに入力処理を書く
GOSUB @GETINT
R4 = R0
@LOOP
GOSUB @GETINT
R4 = R4 - 1
IF HI GOTO @LOOP
ソースコード
10 'ABC005 B
20 POKE#700,127,163,240,181,31,70,64,38,54,4,128,54,54,2,113,104,13,70,1,32,129,67,113,96,0,240,7,248,4,70,0,240,4,248,100,30,251,216,117,96,240,189,0,32,10,34,113,105,73,8,252,211,49,120,48,57
30 POKE#738,2,212,80,67,64,24,246,231,56,112,127,28,112,71
40 A=USR(#700,0)
50 N=PEEK(#900)
60 M=PEEK(#901)
70 FOR I=1 TO N
80 T=PEEK(#900+I)
90 IF T<M M=T
100 NEXT
110 PRINT M
C - おいしいたこ焼きの売り方
何をする問題か
たこ焼きができるタイミングと客が来るタイミングが与えられる。
客が来たとき、指定の秒数以内(0秒でも可)にできて売れていないたこ焼きがあれば、それを1個売る。
与えられるすべての客にこの条件でたこ焼きを売れるかを判定する。
解法
たこ焼きができる時刻を配列の添字として用い、それぞれの時刻でいくつたこ焼きができるかをまとめる。
売れる(指定の秒数以内の)たこ焼きの中で前にできたものから売っていくといいので、
どの時刻のたこ焼きを売るかを管理しておく。
客が来たとき、売るたこ焼きができた時刻と客が来た時刻の差が指定の秒数を超える場合は
指定の秒数になるように売るたこ焼きができた時刻を進める。
そして、その時刻にできたたこ焼きが残っていない間、さらに進める。
このとき、客が来た時刻を超えてしまった場合、この条件で売ることは失敗である。
全ての客について売ることが失敗にならなければ、売ることができると判定する。
入力用マシン語の固有部分
' ここに入力処理を書く
GOSUB @GETINT
GOSUB @GETINT
R4 = R0
@LOOP1
GOSUB @GETINT
R4 = R4 - 1
IF HI GOTO @LOOP1
GOSUB @GETINT
R4 = R0
@LOOP2
GOSUB @GETINT
R4 = R4 - 1
IF HI GOTO @LOOP2
ソースコード
10 'ABC005 C
20 VIDEO 0
30 POKE#700,127,163,240,181,31,70,64,38,54,4,128,54,54,2,113,104,13,70,1,32,129,67,113,96,0,240,16,248,0,240,14,248,4,70,0,240,11,248,100,30,251,216,0,240,7,248,4,70,0,240,4,248,100,30,251,216,117,96
40 POKE#73A,240,189,0,32,10,34,113,105,73,8,252,211,49,120,48,57,2,212,80,67,64,24,246,231,56,112,127,28,112,71
50 A=USR(#700,0)
60 FOR I=1 TO 100:[I]=0:NEXT
70 T=PEEK(#900)
80 N=PEEK(#901)
90 FOR I=1 TO N
100 Y=PEEK(#901+I):[Y]=[Y]+1
110 NEXT
120 B=#902+N:M=PEEK(B):A=1:I=1
130 C=PEEK(B+I):IF A+T<C A=C-T
140 IF [A]>0 [A]=[A]-1:GOTO170
150 A=A+1:IF C<A ?"no":GOTO190
160 GOTO 140
170 I=I+1:IF I<=M GOTO 130
180 PRINT "yes"
190 VIDEO 1
D - おいしいたこ焼きの焼き方
何をする問題か
正方形のグリッド上に値が割り当てられている。
このグリッドから与えられる面積以下の長方形の領域を選ぶとき、その中の値の合計の最大値を求める。
解法
グリッド上の値の累積和を取る。
グリッドの中の長方形の領域を全探索し、面積ごとに合計の最大値を求める。
それぞれの面積の最大値から、それぞれの面積「以下」の最大値を求め、クエリに応じて出力する。
ただし、この問題ではグリッドのサイズが最大50×50となっており、
読み込むだけでIchigoJamで利用可能なRAMのサイズを超えてしまう。
フラッシュメモリを活用するなどの方法も考えられるが、処理時間もかかりすぎてしまうことが予想される。
したがって、今回は部分点が得られる5×5以下のグリッドを対象とする。
入力用マシン語の固有部分
' ここに入力処理を書く
GOSUB @GETINT
R4 = R0
R4 *= R0
@LOOP1
GOSUB @GETINT
R4 - 25
IF LS GOTO @LOOP1_SAFE
R7 = R7 - 1
@LOOP1_SAFE
R4 = R4 - 1
IF HI GOTO @LOOP1
GOSUB @GETINT
R4 = R0
@LOOP2
GOSUB @GETINT
R4 - 25
IF LS GOTO @LOOP2_SAFE
R7 = R7 - 1
@LOOP2_SAFE
R4 = R4 - 1
IF HI GOTO @LOOP2
ソースコード
10 'ABC005 D
20 VIDEO0
30 POKE#700,127,163,240,181,31,70,64,38,54,4,128,54,54,2,113,104,13,70,1,32,129,67,113,96,0,240,21,248,4,70,68,67,0,240,17,248,25,44,0,217,127,30,100,30,248,216,0,240,10,248,4,70,0,240,7,248,25,44
40 POKE#73A,0,217,127,30,100,30,248,216,117,96,240,189,0,32,10,34,113,105,73,8,252,211,49,120,48,57,2,212,80,67,64,24,246,231,56,112,127,28,112,71
50 A=USR(#700,0):N=PEEK(#900):IFN>5?"too large":VIDEO1:END
60 M=N+1:D=N*N+1:E=D+M*M:FORI=0TON:[D+I]=0:[D+I*M]=0:NEXT
70 FORI=0TON-1:FORJ=1TON
80 [D+(I+1)*M+J]=PEEK(#900+I*N+J):NEXT:NEXT
90 R=#901+N*N:Q=PEEK(R)
100 FORI=1TOQ:[E+I]=PEEK(R+I):NEXT
110 FORI=0TON*N:[I]=0:NEXT
120 FORI=1TON:FORJ=1TON
130 P=D+I*M+J:[P]=[P]+[P-1]
140 NEXT:NEXT
150 FORJ=1TON:FORI=1TON
160 P=D+I*M+J:[P]=[P]+[P-M]
170 NEXT:NEXT
180 FORI=0TON-1:FORJ=0TON-1
190 FORK=I+1TON:FORL=J+1TON
200 A=(K-I)*(L-J)
210 T=[D+K*M+L]-[D+I*M+L]-[D+K*M+J]+[D+I*M+J]
220 IF[A]<T[A]=T
230 NEXT:NEXT:NEXT:NEXT
240 FORI=1TON*N
250 IF[I-1]>[I][I]=[I-1]
260 NEXT:FORI=1TOQ
270 PRINT[[E+I]]:NEXT:VIDEO1
IchigoJamとは
2,000円前後で購入することができ、BASICによるプログラミングが可能なパソコンです。
こどもパソコン IchigoJam - はじめてのプログラミングパソコン(1500円)
また、プログラムをWebブラウザ上で実行できるサービスもあります。
IchigoJam web by WebAssembly
※今回のプログラムはマシン語を用いているため、今のところこのサービスでは動きません
※「IchigoJam」はjig.jpの登録商標です