Brainf**k講座(番外編) atcoderでの処理限界
はじめに
本記事は、Qiitaの競技プログラミングなんでも Advent Calendar 2024の、シリーズ2 14日目の記事です。
非常に残念なことに、複雑な処理の実装難易度が非常に高くなることもあり、atcoder等競技プログラミングでBrainf**kを使用して高難易度問題を解くのは困難です。
しかしながら、そのこととは別にatcoderではリソースの問題で解ける問題に限界があります。( もちろんそのような限界ができてしまうこと自体はBrainf**kの弱点ですが )
今回は、その限界に触れる事例を紹介します。
環境
先日Brainf**k講座(応用編) atcoderでの頻出処理である程度記載していますが、atcoder では bf という処理系を使用しています。それを踏まえた上でリソース的な環境を挙げると次のようになります。
- メモリ量
メモリ量の前に他の要素がネックになるため、実質制限なしと考えて良いです。 - 処理時間/ステップ数
取り組める問題だと大抵 2秒が上限となっています。これはステップ数に換算すると、大体10億ステップ数程度の体感となります ( 数倍のブレはあると思います )。
なお、ここで言うステップ数は単純に命令の数で良いのですが、<>+-のどれか同種の命令が続く時は、まとめて1ステップと換算します。 - コード容量(文字数)
提出できるコード容量は、512KiB となっています。そのため、ループ制御で同じ処理を繰り返すところを、同種の命令を重ねることで定数倍のステップ数削減を行うという対策にも制約があるということになります。
事例
それでは、今回は「なんとか制限内で解けたが、これ以上規模が大きくなると厳しそう」という事例を紹介し、制限内に抑えるための対策と限界の見積もりについて考察します。
問題
今回取り上げる問題は、agc007のB問題です。問題の概要は次の通りです。
- 入力
1行目にN p_1, p_2, \cdots, p_N - 出力
1行目にa_1, a_2, \cdots, a_N
2行目にb_1, b_2, \cdots, b_N
※末尾の空白は許容される、また2行目の末尾に改行はつけなくてもよい - 条件
1\le a_n, b_n\le 10^9 \{a_n\} \{b_n\} \{ a_{p_n}+b_{p_n} \} - 制約
2\le N\le 20,000 \{p_n\} 1\sim N
この問題を解くための方針ですが、仮に
そうすると、次のようなRubyでのコードが解になっていることが分かります。
n = gets.to_i + 10000
c = 10000
# a_n の出力
while (n -= 1) >= 10000
print "%5d0000 " % c
c += 2
end
print "\n"
xs = [0] * 20000
i = 0
# p_n 読み込みと調整値保存
gets.split.each{|q|
xs[q.to_i - 1] = i
i += 1
}
# b_n の出力
xs.each{|x|
break if (c -= 2) < 10000
print "%9d " % (c * 10000 + x)
}
この方針だと
なお、コード中の c の初期値を 10000 にしているのは c の万の桁を見るだけで判断することができるようになっています。
※最初に n に 10000 を足しているのも、
言うまでもないことですが、こういった工夫を行っているのは、Brainf**kに移植した時に実装で楽をするためです。
計算量見積もりと対策
さて、前章で示した実装ですが、大まかに次の3段階に分かれています。
-
N \{a_n\} -
\{p_n\} xsへのi保存 - 配列
xsの順次アクセスと\{b_n\}
この内、1., 3. は単純に計算量
ところが、2. は計算量的には
なお、この配列のランダムアクセスは次のような処理イメージとなります。
配列要素を格納する場所を飛び飛びに設け、その間を距離・値をまとめた塊を通していくような感じです。距離・値・配列要素1つのセットで1ブロックとしています。
しかし、atcoderのbfは、同じ処理であれば、例えば >>>> のように移動を連続させるような形で1ステップで実行することができます。このことを利用し、移動のステップ数を削減する対策があります。
ちょうど次の図のように、移動距離を桁で分けて分割して、それぞれを1ステップずつで捌くイメージになります。
これにより、ステップ数を
ただこのためには、万単位の移動をコード上に >>>>…>>>(万単位の文字数) のような形で反映させないとなりません。そのためコード量が膨大なものになりますし、今度は512KiBのコード容量への抵触を気にする必要が出てくるところがトレードオフとなります。
コード全体
それではここで、実際にACした91813B版コードを、コメント付きにしたものを下に挙げます。
ただ、文字数が多いところをそのまま載せると膨大な量となるため、例えば - が48文字続くところは -{48} のようにまとめた形で書いています。
** construct 256w barrier **
-[-[->+<]->]-
** input n **
>>>>>>,+[
++>>+>-[----<<<[->]>>-]
<[-<,+>]
<]
>>>[+]-
** setup for printing As **
>>>>>>>>>>++++[-<s---->]-<+[-<+]+<<<<<<<<<m+>>>>>l
** As printing loop **
l>-[
<+l[
-[->+[+++++++>+]->>-<]
>[<]
+<+]
>->+<<<l<<<<<m[ ** continuing **
m>>>>>l>-
** print c as A **
>>>+[
+{47}
.
-{48}
>+]
** increment c by 2 **
-<<<<<<++[
----------[+++++++++++[-<+]->]
<+]
-
>]
>[ ** break **
[>]
>>]
<<]
** clear n and s **
<l+.[[-]<]+[->+]<s[+]>>-
** Ps input loop **
>>>>>>>,+[
** compare **
++>>+>-[----<<<[->]>>-]
<[- ** number: update as duodecimal **
** x10 **
<<<-<<<<<+[-
[-<++++++++++>]
>+]
>[-<<<+>>>]
** divmod by 12 loop **
<<<+[
[>[+>>>>>]<[<+>>----------->>>>]<<<<<-]
>-<<]
->>[++++++++++++>]
>>]
>>[[-] ** delimiter: store at X(p) **
** copy J **
>-<+[-<+]-<<<<<+[-
[-<+>>>>>>>>>>>>+<<<<<<<<<<<]
>+]-
>>>>>+[-
<<<<<<<[->+<]
>>>>>>+]-
** increment J ( original ) **
<+[
----------[+++++++++++[->+]->]
<+]-
** move block **
>
** 1st move **
>[
[
-[-
>{16x12x12x12}
+
<{16x12x12x12}
]
>+]
>{16x12x12x12}
-<<<<<<<<<]
** 2nd move **
>[
[
-[-
>{16x12x12}
+
<{16x12x12}
]
>+]
>{16x12x12}
-<<<<<<<<]
** 3rd move **
>[
[
-[-
>{16x12}
+
<{16x12}
]
>+]
>{16x12}
-<<<<<<<]
** 4th move **
>[
[
-[-
>{16}
+
<{16}
]
>+]
>{16}
-<<<<<<]
** store **
>+[-
[->>>>>>+<<<<<<]
>+]
** go back **
>>>>>>-<<+[-<{256}+]
-[>{16}]+[->+]->>>>>>>>>>
]
<<<,+]
** move c **
<<<<<<<<<<<<<-<<<<<+[-
[-
>{29}
+
<{29}
]
>+]
** Bs printing loop **
>{29}-[
** decrement c by 2 **
<+[
-[->+[++++++++>+]->]
<+]
>+<-<-
** print B **
<<<<[ ** c ge 10000: continuing **
** copy c for the next loop **
+[-
[->>>>>>+>>>>>>>>>>+<{16}]
>+]
** print **
>[
+{47}.
>+]
+{32}.
,+]
>>>>>>-]
焦点となるのは、** move block ** の ** 1st move ** から ** 4th move ** までの分割したブロック移動移動です。これは、p として読み込んだ値を4桁の12進数として展開し、4段階に分割したものです。
※移動する値としての j は10進数として扱っています。
ブロック自体は p:12進数4桁 + ( j:10進数5桁 + 区切り1桁 ) × 2(x分) の16セル単位で扱うため、** 1st move ** の移動単位は
実を言うと、長距離移動のステップ数ということでは、配列に値を保存してから次の値を扱うために戻る処理も同じような問題を抱えています。
これも段階ごとにマーカーを設ければステップ数を抑えられるのですが、コード量が更にかさむことになるため、今回は移動幅をブロック単位16でなく、その16倍の256にするという定数倍のステップ数削減でなんとかしています。( ** go back ** の部分 )
移動幅256の受け皿になるため、コードの先頭で 256 のマーカー地帯を設け、どこから戻っても対処できるようにしています。
※なお、データの移動が絡まないため、段階に分けなくてもステップ数
限界の考察
今回の問題規模ですが、
-
N - 処理ステップ
O(Nlog^2N)
※O(N^2) - 処理時間 0.7s で、制限の約1/3
- コード量 91813B で、制限の約1/6
※移動処理を段階に分けるにしても、何か所にも適用できるほど余裕はない
ということを考えると、類似の1次元配列操作がある問題で、数万要素規模がatcoderでのBrainf**k実装の限界だろうと推測できます。
逆に言うと、今回は限界直前を垣間見ることができる、丁度いい具合の問題だったのではないでしょうか。
おわりに
今回は、具体的な実装の解説というよりも、問題規模の限界とステップ数・コード量のトレードオフを探るのが主眼の番外編として構成しました。
複雑だったり大規模だったりする問題でBrainf**kでは手が届かないものが多いのも事実ですが、それでも、今回のような実装が、手が届く範囲を見積もるのに役立てられれば幸いです。
Discussion