prime's diary

そすうの日々を垂れ流しちゃうやつだよ

AtCoder Heuristic Contest 003で5位(2.921T点)を取りました

AtCoder Heuristic Contestは、最近始まったAtCoderの定期コンテストで、最適解を出すのが難しい問題に対し、出来るだけ良い解を作成するコンテストです。 1週間程度の長期コンテストと、数時間程度の短期コンテストが交互に行われます。

atcoder.jp

今回のコンテストでは参加者1000人中5位と、非常にいい成績をとれました。 システムテスト前の得点(コンテスト中に表示される暫定得点、100ケースの合計)は97,323,736,361(97.32G)点、システムテスト後の得点(3000ケース合計)は2,921,245,705,250(2.921T)点でした。

今回のコンテストでやったこと、やらなかったこと、考えたこと等をまとめます。

問題概要

30*30のグリッドグラフ上で、ジャッジが指定した2点間に対して最短経路を求めるクエリが1000回投げられます。 しかし、各辺の長さは隠されており、自分のプログラムの返した経路の長さ(に0.9~1.1の範囲の一様乱数を掛けた値)のみを知ることができます。

得点は、各クエリに対して、真の最短経路aを自分のプログラムの返した経路の長さbで割った値a/bを、後半のクエリほど大きな重みを付けて和を取った値です。 1テストケースあたりの得点の上限がほぼ109点になるように定数が掛けられています。

辺の重みの決定方法が若干特殊で、Mというパラメータがテストケース毎にランダムで1か2になり、その値によって重みの付け方が異なります。 また、D \in [100,2000]というパラメータもテストケースごとに一つ生成されます。(これらの値を直接知ることはできません)

M=1のとき

各行、各列ごとに、基準となる重みを[1000+D,9000-D]の範囲から一様ランダムに生成し、ここに各辺に対して[-D,D]の一様ランダムな値が加えられる。

M=2のとき

各行、各列ごとに、基準となる重みを[1000+D,9000-D]の範囲から一様ランダムに二つ(ここではW_0, W_1とします)生成し、また、"切れ目"を1~28の範囲から一様ランダムに生成し、 グリッドの片方の端から"切れ目"までをW_0を基準、そこからもう片方の端までをW_1を基準とし、ここに各辺に対して[-D,D]の一様ランダムな値が加えられる。

詳細についてはhttps://atcoder.jp/contests/ahc003/tasks/ahc003_aを参照。

自分の解法

ここからは時系列順にやったことを書いていきます。見出しの得点はpretest時の得点。

愚直解 (61.67G)

Submission #22782181 - AtCoder Heuristic Contest 003

まずは入出力が正しくできるか確かめるため、常にすべての辺の重みが一定であると仮定した状態で、毎回Dijkstra法で最短経路を求めるコードを書きました。

今回は提出コードをRustで書きましたが、proconioが内部のバッファリングの影響か、インタラクティブ環境でうまく動かなかったので、温かみのある入力パースを行いました。

勾配降下法の実装 (81.59G)

Submission #22784737 - AtCoder Heuristic Contest 003

i番目のクエリの応答の経路の長さy_iは、辺jの重みを w_j、その経路に含まれる辺の番号を  p_{i,1} , p_{i,2} , ... , p_{i,k_i} とすると、

 \displaystyle
y_i = \sum_{j=0}^{k_i} w_{p_{i,j}}

と書けます。ここで、行列 A=(a_{ij})i番目の経路に辺jが含まれていれば1、そうでなければ0として定義すると、

 \displaystyle
\textbf {y} = A \textbf{x}

と書くことができます。これを\textbf{x}について解けば辺の重みが分かりますが、辺の数が1740あるのに対し、経路の数は高々1000個しかないため、一意な解は存在しません。 また、帰ってくる経路長は乱数でスケーリングされているので、解が存在するとも限りません。

ここではとりあえず、辺の重みの近似値を、 \textrm{min}(||A \textbf{x}- \textbf{y}|| _2)(最小二乗法)を勾配降下法によって求めることにしました。 スケーリングは正規分布ではなく一様分布であるため、最小二乗法でいいのかという問題はありますが、とりあえず計算が簡単なのと、このあとCG法を使ってみようと思ったためこうしました。

勾配降下法の高速化、辺の重みの初期値の調整 (87.74G)

Submission #22785943 - AtCoder Heuristic Contest 003

雑に疎行列演算等を実装したところ、各クエリに対して20回しか勾配降下法のステップを回しただけで1200msほどかかっていたので、不要なメモリ確保をなくすなどの高速化をして、30ステップほど回すようにしました。 また、未探索の辺を積極的に調べるため、未探索の辺の重みを期待値である5000よりも若干小さくしました。

高速化、学習率の調整 (92.19G)

同時に疎行列ベクトル積を高速化して、クエリごとに50ステップ程回せるようになりました。 get_unchecked (配列の境界チェックをせずに配列の要素にアクセスするunsafe関数)使ったら速くなった!(これでいいのか?)

もう少し1ステップで更新する大きさ(学習率)増やしても行けそうだったので、5倍(0.0001→0.0005)にしました。 また、Dijkstra法は負辺/負閉路があるとまずいので、辺の重みを1000-9000の間になるようにclampした(Rust 1.42.0にはclampがなかったのでminとmaxで書いた)。

共役勾配法の導入 (92.83G)

二乗誤差の最小化 \textrm{min}(||A \textbf{x}- \textbf{y}|| _2)は、実は方程式 A^tA \textbf{x} = A^t \textbf{y} (正規方程式)を解くことによっても求められます。 これは線型の連立方程式なので様々な方法で解けますが、行列サイズが1740*1740とかになるのでガウスの消去法等では計算量が大きすぎます。 しかし、Aはほとんどの要素が0の疎行列なので、これを生かした高速な求解アルゴリズムがいくつか存在します。 ここでは共役勾配法(CG法)を使いました。

大きすぎる/小さすぎるweightの抑制(正規化) (93.15G)

辺の重みは1000-9000の間にありますが、経路長に誤差が乗っているため、方程式はその範囲外の値を解としてもってしまうことがあります。 これを補正するために、|すべての辺の重みの平均-5000|も最小化対象になるように、行列Aに入れました。 さらに辺の重みの初期値をいじって93G点に乗せました。

重大な事実に気付く

ここまで初日の内容で、このときは1桁順位で満足していましたが、土日が明けた頃には40位程度まで落ちていました。 で、上位の得点を見ると、すでに96G点台になっていました。 この時点ではなんとまだMパラメータの存在に気付いておらず、1740辺に対し1000経路では明らかに情報が不足して、こんなに精度が出るのはおかしくないか?と思っていました。

何か勘違いとしているとまずい、ということで問題文やテストケースの生成方法をよく読むことにしました。 すると、Mというパラメータがあり、とくにM=1の時は同じ行/同じ列の辺の重みはほとんど同じになっていることに(今さら)気付きました。 たしかにこれを使えば大きくスコアを改善できそうです。

隣り合う辺の重みの差の抑制 (95.53G)

ということで、同じ行/列の辺であって、隣り合っているものについて、その重みの差を最小化対象に入れました。 これはAに片方の辺にw、もう片方の辺に-wを掛けて足す行を追加すればよいです。

解と行列の使いまわし (96.85G)

いくらCG法が高速に収束するとはいえ、TLEしない10回程度の反復では、得られる解(辺の重み)の精度は限られています。 そこで、辺の重みベクトルをクエリ間で使いまわすようにします。すると、前回得られた解からスタートするので、多くの場合今回求めるべき解の近くからスタートすることになり、収束が速くなります。 また、これまでは行列やベクトルをクエリごとに再構築していたのを、使いまわすようにして高速化し、反復回数を増やせるようにしました。

この時点で暫定2位まで来ました。びっくりです。 さすがに3日目まで問題文をよく読んでない人ばかりではないと思うので、おそらくCG法によって1740辺個別に重みを推定できるようになったのが大きく効いたのではないかと思います。

重みスケーリング (97.02G)

M=2のときは、行中のどこかで辺の重みが一気に変わる場所が存在するはずで、このとき隣り合う辺の重みの差を抑制していると、真の重みから遠い重みを推定してしまいます。 そこで、隣り合う辺の重みの差によるペナルティーがどれくらいかかっているかに応じて、ペナルティーを軽減したり増やしたりするようにしました。

パスの長さによる正規化 (97.13G)

これまで、各経路に対して、| \sum x_{i_j}-b_i| (と他の正規化項)の二乗和を最小化してきましたが、| \sum x_{i_j}-b_i|は経路中の辺の数が多いほど大きくなりやすいです。 二乗和の最小化なので、この場合長い経路ほど頑張って誤差を最小化しようとすることになります。 しかし、得られる経路の長さが真の値に対して0.9~1.1倍スケールされていることを考えると、短い経路の結果も長い経路の結果も同程度に重視すべきです。

そこで、経路中の辺の数n_iを用いて、|Σ(1/n_i)*x_{i_j}-b_i/n_i| (と他の正規化項)と正規化してやると、スコアが伸びました。

Mの推定、その他微調整 (97.32G)

M=2かどうかをlossを見てアドホックに推定して、それに応じてペナルティーをいじるようにしました。 あとは細かい改良を積み重ねたり、optunaでハイパーパラメータチューニングをしたりして、スコアを積み上げていきました。 最後までM=2でDが小さいときに対するうまい対処法を思いつけなかったのが残念です。

解法そのものとは関係なくやったこと

複数テストケースを並列で走らせて、たくさんのテストケースについての得点を素早く集計する

問題の性質上、テストケースによって点数が大きくずれる、また、パラメータによって得点傾向が違うことから、少数のテストケースのみで変更点の有効性を確認するのは危険です。 コンテスト中の提出は30分に一回しかできず、また、100ケースしかないため、かなり大きな改善でないと有効性を言えるほどの点差がつきません。 さらに、改善が進むにつれ、一つの変更による得点の上昇が少なくなっていくので、その分テストケースの数を増やしていかないとテストケースに対して過学習を起こしやすくなります。

そのため、ローカルでたくさんのケースについて得点を集計する仕組みを構築しました。 複数ノードにバイナリをばらまいて、各ノードで計算を走らせ、それを集計するスクリプトRubyで書いて、コマンド一つでできるようにしました。 最終的には家の計算機5台(Ryzen 7 Pro 4750GE * 4 + Ryzen 9 5950X * 1)の計48コア96スレッドで7680ケースについて回すようにしました。

性質上、並列度はテストケースの数だけ増やせるはずなので、次回の長期コンテストまでにはAWS Lambda等を用いて1000並列とかで回せるベンチマークシステムを構築したいです。

M,Dの値とスコアの関係をプロット

これも考察に大いに役立ちました。M=2のときだけでなく、Dの大きいときもかなりスコアが下がっていることが確認できました。 コードをいじった時にも、どういうところでスコアが改善・悪化しているかが見てわかるので良かったです。

f:id:PrimeNumber:20210603100712p:plain
パラメータの値とスコアの関係

optunaによるハイパーパラメータチューニング

使いどころが難しい(本質的な改善の方が大事)ですが、次のような場合に使ってとてもいい感じでした。

  • 他のパラメータとの相対的な重みの大きさが変わるような変更の後

パスの長さによる正規化を実装したとき、経路に関するlossは(辺の数で割られるので)かなり小さくなります。 それに応じて他の正規化パラメータの大きさも小さくする必要がありますが、複数パラメータ間のバランスをとるのは大変で、ここでoptunaで自動的にチューニングできたのはとても便利でした。

  • これから寝るとき

寝てるだけでスコアが良くなって便利。

  • もうできることが思い浮かばないとき

ボーっとしてるだけでスコアが良くなって便利。

  • 計算機を温めたいとき

マイニングでもしとけ。

512ケース程度ではかなり過学習してしまうので、かなり計算資源が必要なのが難しいところだと思います。 最初に128ケースまわしてとても悪そうだったらそこでやめて、悪くなさそうならもっとたくさんのケースを回す、とか工夫の余地はありそうです。

特に、今後クラウドで回そうとするならば、そのへんの計算量削減策を考えないとすぐにお金が融けていきそうです。

やったけどうまくいかなかったこと

隣接辺の重みの差をペナルティにするのではなく、ダミー辺との重みの差をペナルティにする

  • M=2のときに全然上手く行かなかった
  • M=1のときもスコアの分散が大きくなっただけであまり改善されず
  • 辺ごとの重み推定を捨てて、行ごと(60変数や120変数/180変数のモデルにする)でやればよかったかも

経路の結果を正規化する際に、辺の数ではなくスコアで正規化

  • 他のパラメータの重みもずらす必要があるのでoptunaで最適化もしたが、それでもだいぶ悪かった
  • 経路長に乱数がかかった後の値がやってくるのがまずそう?

やっておけばよかったこと

M,Dの推定値によるモデルの切り替え

これをできなかったのは結構良くなかったな、という気持ち… M=2の時のモデルをどうするか、というのが本質的に難しそうですが… Dが大きいときには、わりとできることは少なそうで、ここの改善はあまり期待できなさそうです。

事前の環境整備

インフラ回り等、事前に準備できることは結構あるはずなので、そのへんを次回の長期コンまでにやっていきたいです。

感想

とてもよくできた問題だと感じました。 これがM=3とかがあると、割と打つ手がなさそう(複雑度に比べて、得られる情報が少なすぎるため)で、かといってM=1だけだとすぐほぼ理論値までたどり着いてしまうはずで、この辺の塩梅が良かったように感じます。

結果にはとても満足していて、望外のいい結果を得られてとてもうれしいです。 今後もいい結果を残せるように頑張ります。

AtCoder Heuristic Contest 001 解法メモ

最終スコア(システムテスト後)は980,823,067,375点で95位でした。

atcoder.jp

自明解の生成

広告の希望(x, y, r)に対して、長方形( (x, y), (x+1, y+1) )は解の条件を満たす

スコア計算

  • 解の条件を満たしているかを判定する
  • 満たしていれば、各広告についての点数の和を取って全体のスコアを算出する

基本方針

山登り法、乱数の値の幅を徐々に小さくする

1点探索 (resize_1way)

広告を一つランダムに選択する 任意の方向に適当な大きさ伸ばし/縮めることを試す これを何度も繰り替えす

1点探索 (move)

他の広告の邪魔になっているところを解消するため、広告を平行移動する 広告を一つランダムに選択する 任意の方向に適当な距離移動させることを試す

2点探索 (redelineate)

接触している2つの広告のペアをランダムに選択する 接触している境界線をどちらかの方向に適当な距離移動させることを試す

スコア計算の最適化

  • 解の条件を満たしているかを判定するのがO(n2)かかっており、遅い
  • 操作前に解の条件を満たしていることを仮定すると、上記の操作では、変更した広告と他の広告のペアについて、解の条件を満たしているかを判定すれば十分
  • 判定にO(n)、スコア計算にO(n)で全体でもO(n)でスコアを計算できる
  • また、スコア計算自体も差分更新できる(依然として判定にはO(n)かかるので、オーダーレベルでの改善にはならない)
  • そもそも、スコアをずっと持っておく必要もなく、スコアが増大するかどうかが関心の対象なので、変更した広告の得点だけを見ればよい

greedy

何度も改善を繰り返し、制限時間を迎えたとき、shake操作等により広告間に隙間ができていることがある もったいないので、改善できるなら貪欲に改善する

redelineate skip 最適化

自明解から広告を拡大している途中では、広告同士が接触していることはまれ 2点探索は接触判定にO(n2)かかっており遅いため、最初のうちは行わないことで高速化

全体再配置 (gravity)

方向をランダムに選択する すべての広告を、他の広告にぶつからず、位置の制約を満たす範囲で選択した方向に平行移動する この際、平行移動の代わりに拡大してスコアを改善できれば、する

1点探索 (resize_2way)

1方向だけに対してサイズ変更をした場合、すでに要求の大きさに近い面積になっていると、これ以上拡大・縮小が不可能になることがある 2方向に対してサイズ変更をすることで、これを緩和する

複数回探索 (多点スタート)

局所解に嵌ってしまうと、抜け出すのは困難なため、何度も探索してもっともよさそうな解に対してさらに最適化を掛ける

2点探索高速化

2点探索では、接触判定の計算量O(n2)が支配的で、その後の試す部分では解の条件判定にO(n)掛かる他は定数時間で終わる。 そのため、一度接触判定をしたら、その後たくさんのペアに対して変更を試すことで、変更当たりの計算量を削減して高速化できる。

2点探索 (dodge)

接触面を平行移動するのではなく、接触面を0にするようにそれぞれの広告の大きさを変更した後、もとよりスコアが改善するように接触面のあった方向に広告を伸長する

resize_1way強化

resizeの結果他の広告にぶつかった場合も、そこで失敗判定にせずに、ぶつかった広告を縮小して回避できるときは回避することを試す

AtCoder橙/Codeforces International Grandmasterになりました

この記事は色変記事アドベントカレンダー1日目の記事ではありません。

AtCoderで橙色、CodeforcesでInternational Grandmaster(IGM)になったので振り返り記事を書きます。

f:id:PrimeNumber:20210117052734p:plain
AtCoderのレーティング推移
f:id:PrimeNumber:20210117052826p:plain
Codeforcesのレーティング推移
まあ、Codeforcesの方はIGMになった後GMに落ちちゃったんですが…

感想

Codeforces IGMは昔からの憧れでもあったので、とても感慨深いものがあります。というか、自分がなれるものだとは思っていなかった節があります。 一方で、AtCoder橙は訓練を積めばそのうちなれると信じていたんですが、結果としてCodeforces IGMの方が早く達成できてしまいました。こういう人あんまりいないみたいで謎です。

やったこと

ABC-EF埋め

2020年2月ごろに全部埋めた。(今は数問埋まっていない…) 典型問題の処理がうまくなると、難しい問題の方針も立てやすいし、なにより序盤の簡単な・典型的な問題で時間ロスをしにくくなると思います。

黄Diff(🧪含む)埋め

2020年4~5月 AtCoder ProblemsでDifficultyが黄色になっている問題を全部解きました。黄色Diffばっかりやるのは黄Diff問題に頭が過学習する感じがあってあんまりよくなくて、橙や青Diffも混ぜて解くべきでした。 文字列系の問題は、これまでZ-algorithmとかSuffix Arrayとかほとんど使ったことがなかった(解けない or ローリングハッシュで殴りがち)ので、ここで復習できたのは良かったです。

同じ黄Diffでも体感難易度にはかなりばらつきがあって、これは自分の得意不得意の偏りだけでなく、そもそものDifficultyの算出精度の限界もありそうです。

黄Diffを全部埋めた後は橙Diffと青Diffを解こうとしましたが、橙Diffは全然解けなくて挫折してしまiいました。今年は橙Diffと正面から向き合っていきたいです。

コンテストに出る

これが自分にとってはかなり効いた感じがします。 というかこれまであんまり出てなかったのが良くなかったです。

コンテスト時間いっぱいあきらめずに噛り付くとか、実装の簡単な方針を考えるとか、複数の問題が残っているときにスッと戦略を切り替えるとか、そういう力が結構養われたように感じています。

今後について

この先の色変目標となると、AtCoder赤とかCodeforces Legendary Grandmasterになりますが、正直全然なれる気がしないので、あまり気負わずじわじわと強くなれるといいなと思っています。

どうしても平日は労働で疲弊してしまうのと、趣味で競プロ以外にもやりたいことがいっぱいあって、正直あまり多くの時間を割けない気はしますが…

まずはAtCoder橙/Codeforces IGMで安定できるようにしていきたいと思います。

あといい加減今使っている競プロライブラリがつらい(C++03/11、ICPC想定で可読性より短さ重視)ので、一新していくつもりですが、今のところリポジトリだけ作って放置しています…

github.com

フラグメントシェーダを用いて、VRChatのワールドで計算機を作る 【KMCアドベントカレンダー 2日目】

この記事はKMCアドベントカレンダー 2日目の記事です

adventar.org

概要

最近遊んでいるVRChatというゲームにはユーザーの作成したアバターやワールドをアップロードできる機能があります。さらに、アバターやワールドのバーテックスシェーダー*1/フラグメントシェーダー*2を自分で作ったものに差し替えてアップロードすることができます。

これを悪用(?)し、fragment shaderにBrainf*ckという難解プログラミング言語インタプリタを実装することで、VRChatで、ゲームプレイ中に指定した任意の計算を実行することができるような仕組みを実装しました*3

GPGPUとは

みなさんが普段ゲームなどのグラフィック処理をするときには、大抵GPU(Graphic Processing Unit)という装置*4が使われます。 GPUは、三次元のポリゴンの移動・変形や、陰影処理等の計算を行うために、たくさんの演算機を備えています。

この演算機の演算能力をグラフィック処理以外にも使おうというアイデアが、GPGPU(General Purpose compution on GPU)と呼ばれています。 今日では、GPGPUはCUDAやOpenCL、OpenACC、グラフィックAPIのCompute Shader等によって比較的手軽に行えるようになりました。

VRChatにおける演算

VRChatはゲームなので、これらの便利なGPGPUプログラミング環境を使う方法はありませんが、アバターやワールドのバーテックスシェーダー/フラグメントシェーダーなどである程度の計算を行うことができます。 バーテックスシェーダーでは各頂点ごとに、フラグメントシェーダーでは画面の各画素ごとにシェーダーのプログラムが実行されます。 が、通常これらのシェーダーは状態を保存したり、他の頂点/画素と通信することはできません。GPUはたくさんのプログラムを並列で計算することでスループットを稼いでいるため、単一の要素に対する計算はあまり高速ではありません。 したがって、まともな速度でゲームが進行するためには、1頂点/画素あたりの計算量は十分小さくないといけません。 つまり、これらのシェーダーで大規模な計算をすることはできません(完)。

という問題を解決する方法がいくつかあり、今回はCustomRenderTextureを使いました。 CustomRenderTextureでは、ダブルバッファリングを有効にすることで、フラグメントシェーダー上で「前のフレームの演算結果」をテクスチャの色情報として得ることができます。また、他のテクスチャ(他のCustomRenderTextureを含む)を入力として受け取ることもできます。 これを利用すると、テクスチャ上に状態を保存することで、フレームをまたいだ計算が可能になります。 また、前のフレームの別の画素の色情報を得ることもできるので、フレームをまたぐことで別の画素と通信が可能になり、並列計算への道が開かれます。 テクスチャは2048x2048程度は問題なく持つことができるため、400万ワードほどのメモリを持つことができます。

これにより、理論上は任意の計算を他のプレイヤーのGPU上で走らせることができます。 とはいえ、shaderのプログラムはアップロード時に決定されてしまうため、このままでは動的に(ゲームプレイ中に)実行するプログラムを差し替えることはできません*5

そこで、fragment shaderに何らかの仮想計算機を実装し、何らかの方法でゲームプレイ中にプログラムを与えることで、ゲームプレイ中にプログラムを差し替えて計算することができるようになります。

Brainf*ck

Brainf*ck*6は難解プログラミング言語と呼ばれる、「プログラミングすることが難しい」プログラミング言語のひとつです。Brainf*ckではソースコードは8つの命令のみで構成されていて、それぞれごく単純なことしかできません。 詳しくは、Brainfuck - Wikipediaなどを参照してください。 例えば、現在VRChatのBF Interpreterワールドに置かれている、4段のハノイの塔のパズルの解法を計算するプログラムは次のようになります。見やすさのために改行やインデントを入れています。 gist.github.com

Brainf*ckでまともな計算をすることはとても難しいですが、Brainf*ckの処理系(コンパイラ/インタプリタ)を作ることは(他のプログラミング言語に比べて)比較的簡単です。 今回は今後より実用的な処理系を作る練習として、実装の容易なBrainf*ckインタプリタを実装することにしました。

処理系の構成

f:id:PrimeNumber:20201202235407p:plain
BF処理系の全体像

処理系本体

処理系の本体はこの図の赤色の部分で、Interpreter Shaderが計算を、Memory/State Textureが状態を保存する役割を果たしています。 Memory/State Textureは64x64pxのRGB値を持ち、最初の1行が命令カウンタなどの状態管理用レジスタ、残りの行がBrainf*ckプログラムの使用するメモリ領域になっています。 状態管理レジスタは[命令カウンタ, データポインタ, 動作モード(実行/前方にジャンプ/後方にジャンプ/プログラム終了), 入力済みバイト数, 出力済みバイト数, 出力データ, ジャンプ時の[ ]の対応を見るカウンタ, 出力validフラグ]の8個となっています。 シェーダー内部では、R,G,Bの各色に対して8bitのデータをエンコードして持たせることで、1画素あたり24bitのデータを保持しています。

処理系の動作はおおむね次のように動きます。 状態管理レジスタに該当する画素: 各レジスタの次フレームの値を計算する - 命令カウンタなら、1進めたり、ジャンプ命令では戻ったり - データポインタは> <命令を実行する状態になっているときのみ増減させる - 出力validフラグは、.命令を実行する状態になっているときのみ1、それ以外を0にする など メモリ領域に該当する画素: データポインタが自身のアドレスと一致しているときのみ、いま命令カウンタが指している命令が+ - ,なら、適切に値を変更する

このような実装により、1フレームに1命令(ジャンプ時はジャンプ場所を線形探索するため何フレームもかかりますが)処理する処理系ができました。

Control Panel

ワールドに設置したカメラでアバターを検出することにより、タッチパネルを実現し、状態のリセットを行うことができます。カメラで撮影した画像をRenderTextureに出力する機能を利用しています。これにより他のシェーダーがプレイヤーの操作を受け取ることができます。 Control Shaderはカメラの入力画像をparallel reductionにより使いやすい形に変換しています。

Output Buffer / Output Text Buffer

出力バッファー用のシェーダーとテクスチャです。 Memory/State Textureの出力validフラグが来たら1文字読み、次の書き込み位置を一つずらします。 Output Text Bufferでは、改行が来たときにも次の書き込み位置を次の行の先頭に移動します。

表示用のシェーダー/テクスチャ

処理系内部では数値はRGB値にエンコードされているので、これを人間が理解できる形式に変換する処理が必要です。 デバッグ用の出力は2進数に変換して黒/白で表示しているだけです。 ソースコードと出力のテキスト表示は、しみさんの

をお借りして実現しています。図がぐちゃぐちゃになるので、上の構成図からはフォント用のテクスチャは省略してあります。 フォントデータが2値画像(をRGBA32bitに詰め込んだもの)なので、大きく表示したときにジャギーが目立つと感じたので、中央値を基にしたジャギー軽減アルゴリズムを実装しています。

今後の課題

  • ソースコードを編集する機能がないので、簡易なテキストエディタを実装して、プレイ中にソースコードを差し替える仕組みを作る
  • ワールドにはインターネット上から画像をダウンロードする方法が存在するので、これにより外部から動的にソースコードを持ってこれるようにする
  • より高級な計算用仮想マシンを実装する
    • Piet DM's Esoteric Programming Languages - Piet の処理系ができると見た目に楽しそう ただし、カラーブロックの連結成分の大きさを高速に求めるのは簡単ではない。
  • 並列計算が可能な仮想マシンアーキテクチャを実装する
    • フラグメントシェーダーはその仕様上、「指定した場所に値を書き込む」という仕組みの実現が難しい(複数フレームを掛けてデータをルーティングする必要がある)
  • 高級で並列計算可能な計算機で、実用的な計算速度を得る

*1:ポリゴンの頂点位置を計算するプログラム

*2:色や陰影を計算するプログラム

*3:CPU側に干渉するわけでもなく、負荷も軽いので他のプレイヤーが困ることはないです

*4:これは物理的に個別のユニットとして存在することもあれば、CPUと同じチップ内に存在することもあります

*5:数個程度なら条件分岐で差し替えることはできる

*6:*にはuが入ります

競技プログラミングはISUCONの役に立つ 【ISUCON10予選参加記】

単なる普通のISUCON参加記です。 そんなに競技プログラミングの話はないので、そういう話を期待していた人はごめんなさい。

こういうのは忘れないうちに書かないと書けないがち。

isucon.net

ISUCON10にチーム「:羽付きのお札:」で nana ( 久我山 菜々🐇🏰🕛🥕 (@nonamea774) | Twitter ) と yu3 ( ゆー (@yu3mars) | Twitter ) のメンバーで出て、最終1195点(時間中の最高点は1400点ほど)で予選落ちでした。

開始前日まで

チームでどの言語を使うかを事前にGo言語に決めて、Go言語の勉強ついでに、練習として去年の予選問題を解いたりしていた。 ちなみに自分では23,000点ぐらい(当時のスコアで言うと全体の6位くらい)出せていた(もちろん他の人のブログとかを参考にした)。

開始直前

nanaは偶然にも(?)東京に来ていたので私の部屋で一緒にやることにした。yu3とはslack call等でコミュニケーションを取る。 開始が遅れたのでゆっくり朝食をとった。

なぞって検索

開始するとさっそくポータルが502で落ちていた…まあ数分で見えるようになったので問題を呼んだりsshで入れることを確認したり、実際にブラウザで触ったりした。 明らかに「なぞって検索」がやばそう。案の定広い範囲を囲うとめちゃくちゃ遅い。 ポータルが不調で、まだベンチマークに掛けられなかったので、なぞって検索について考える。

こういう二次元データを囲った範囲に入る点を求めるのは、大抵なんらかの賢いデータ構造(kd-treeとかそういうやつ)が必要になるはず(これは割と競技プログラミングの経験が役に立った感じ)。 でもこれを手で実装するのはしんどそうで、nanaに相談したら、GISデータとかをmysqlとかでうまく扱える仕組みがあるはず、と教えてくれたので調べることにした。 なるほどたしかに、Geometryという形式で格納して、Spatial indexを有効にしておくといい感じにやってくれるらしい。 のでこれを実装することにした。

物件の追加クエリとかスキーマ定義はまだいいとして、初期化時に使う.sqlファイルを更新するのがだるい。 コンテスト後にgenerated columnsというのがあるというのを知ったが、このときは知らなかったので、Rubyでクエリ文をパースするスクリプトを書いて書き換えた。

途中で、「椅子を通せるドアかどうかを判定する方法」(椅子にはH,W,Dの情報、ドアにはH,Wの情報が与えられるので、椅子を直方体だと思ったときにうまく回転させることでドアを通せるかどうか)を計算するのに、すべての回転を調べるのは非効率なのでなんとかしたい、という相談をnanaから受けた。 ちょっと考えると椅子の大きさのうち、最大のものは考えなくて良い(その方向を奥行き方向に持ってくれば、残り2方向がドアを通せれば良く、それで通せなければ通らない)ことに気付いた。 ここでも競技プログラミングの経験が効いた気がする。

実装が終わってちゃんと動くようになると、ちゃんとスコアが跳ねて喜ぶ。(700店くらい?) そしてスロークエリログを眺めると自明にインデックスを張れる場所があるので張ると、さらにスコアが跳ねた。 この時点で20位ぐらいだったかな?

インフラまわりとかデプロイ周りとか

基本的にゆーさんとnanaに任せていたので詳しくはわかっていないけど、botを弾くとかが若干効果があったのかな? デプロイはmake deployとかを叩くと、Makefilessh hogehogeとか書いてあるのでそれでローカルのバイナリとかをサーバーに送って、アプリ等を再起動する、というあたたかみのある方法になった。 とはいえ、ISUCONの短時間という制約ではそんなに悪くない方法だと思う。終了後に知ったetckeeperとかは今後試してみたい。

物件・椅子の入稿

ここまで来て、原因不明の「critical error」でスコアが0になることが何度か起きた。 とくにエラーが起きるような変更は見当たらなかったのでだいぶ悩んだが、スロークエリログを眺めると、COMMITで5秒かかっていて、どうやらここでタイムアウトしているらしい。 アプリを眺めると明らかに物件・椅子の入稿がやばい(トランザクション内で、csvの行数だけINSERTが発行される)ので、これをどうにかすることを考える。 nanaが文字列結合等を駆使して巨大なINSERTを1回だけ発行する方法を、私がPrepareをつかって1クエリの負荷を低減する方法を実装した。 結果的に同じとこをいじることになったのは、短い時間の使い方としては失敗だったかも。 ちなみにどちらの実装でもタイムアウトは回避でき、failは回避できるようになった。

検索クエリの改善

ここまで来て、物件・椅子の検索が支配的になってきたので、これを考える。 うまく行きそうなインデックスを張ってみるが、範囲指定が2個出てきたりすると、普通に張ったのでは速くならないっぽいので困ってしまった。 実はMySQL8にすると行けるらしいが、知らなかったしかなり罠が多かったみたいなので、うっかり足を踏み入れなくてよかったかもしれない(?)

大きさに関するクエリは、範囲として指定できるのがそれぞれ4種類(+指定なし)しかない。 したがって、範囲に0〜3のIDを割り振れば、HeightRank = 2みたいなクエリになってインデックス使えそう、となって実装し始めるが、これは最終的には間に合わなかった。 ここもgenerated columnsを知っていればサクッと実装できた気がするので悲しい。

nanaは色や椅子の種類をIDに変換するコードを書いていた。けっこうバグってたけど最後にはちゃんと動いていた。

DBの負荷分散

mysqlがCPUの85〜95%程度を食っていたので、この負荷を分散したかったが、更新があるのでレプリケーションは実装間に合わなさそう(この時点で残り1時間程度)、と思って却下した。 しかし、終了後に教えてもらったこととして、このアプリは椅子と物件でJOINすることがないので、二つのデータベースを別マシンに分けることで、負荷分散が比較的簡単に可能という構造になっていた。 このあたりは、よくアプリの構造を観察することで見つけられたはず(こういうところも競技プログラミングみがある)で、かなり悔しいポイント。 物件検索と椅子検索でそれぞれ半分くらい時間がかかっていたので、もしDB分割をやっていれば、2倍程度のスコアになったと思われ、これは本戦出場ライン近辺になるので、取り組めていれば…と悔やむ。

終了後

終了後は高速に nanaとチーム「百万円ドリブン」の twitter.com と、偶然来ていた ten986 (@ten986) | Twitter とうしとらに打ち上げに行った(そのあとさらに2軒はしごした)。びーるうめえ。

良かった点

事前に練習したおかげで、Go言語の実装・コード読解で詰まることが少なかった。 チームメンバーと互いに相談して、より良い解決策に近づけた。 競技プログラミングの経験を役に立てられた。

反省点

DBに関する知見(generated columns)がまだまだ足りない。 アプリの構造をよく観察するべき。 決勝に進みたい!

試してみたい点

Go言語、静的型付け言語とは何だったのかというレベルで静的検査が弱くてつらいので、Rust使いたい(ほんまか?????)

オンラインBrainf*ckインタプリタ・デバッガを作った【Brainf*ck Advent Calendar 2019とその他のAdCの17日目】

はじめに

この記事はBrainf*ck Advent Calendar 17日目・KMC Advent Calendar 17日目・LeapMind Advent Calendar 17日目の記事です。

adventar.org

adventar.org

adventar.org

概要

難解プログラミング言語の一つであるBrainf*ckのオンラインデバッグ環境を作った話をします。

作ったものは……これ!!!👉👉👉👉👉Online Brainf*ck debugger👈👈👈👈👈

Brainf*ckデバッガについて

Brainf*ckはその仕様上、極めてバグを埋め込みやすいです。具体的には、

  • 変数名とかそういうものはなく、アドレスだけで値を参照・操作する
    • そのうえ、アドレス移動は相対移動(元の位置から+1/-1のみ)しかできないので、参照先を間違えやすい
  • 関数とかいう便利な機能もないので、重複したコードが登場しやすい
  • +, -, >, <命令はよく連続して使われて数え間違えやすく、しかも使う個数を1個でも間違えるとバグる

したがって、(特に大規模な)Brainf*ckプログラムを作成する上ではデバッガの存在はとても大切です。

ということで数年前に

moon.kmc.gr.jp

というデバッガを作ったのですが、如何せん古くなってきたので新しく作り直すことにした、というのが今回の内容です。

現在の機能

インタプリタ

  • Brainf*ckのコードを実際に実行することができます。標準入力を与えることもできます。
  • デバッグモードを有効にすると、100msごとなど指定した時間間隔で命令を実行させられます。
  • 入出力をUTF-8の文字列と解釈するか、16進数と解釈してバイナリを扱うかを選択できます。
  • Brainf*ckではEOFに達したときに入力命令を実行した場合の値は規定されていませんが、これを0と-1(255)で選択できます。

デバッグ機能

  • プログラムカウンタとデータポインタの位置を表示します。
  • @命令に達するとそこで実行を停止させることができます。停止させた後はステップ実行などで細かくプログラムの動作を追うことが可能です。
  • :命令に達すると標準エラー出力に今のポインタの指す値を出力します。.標準エラー出力版です。
  • 指定した範囲のメモリの内容を見ることができます。

その他

  • インタプリタをWebWorkerで動かすことで、重いプログラムを動かしてもUIが重くならず、無限ループに陥ってもページを再読込する必要がない
  • インタプリタjQueryで頑張って書いていたが、Vue.jsを使ってまともなコードになった

今後追加したい機能

旧デバッガにあった機能

  • 今のプログラムカウンタの位置やデータポインタの位置を視覚的に表示する
  • 命令実行ログを取得する
  • ログを遡って実行を逆再生できるようにする
    • ステップ実行などで通り過ぎると悲しいため

あると嬉しそう

  • デバッグ時のステップ実行より高度なデバッグ実行機能
  • デバッグ時のメモリ内容書き換え
  • コードスニペット(あるいはより強力なマクロ機構)
  • コードテスト機能
  • デザインをかっこよくしたい
  • @命令はプログラムカウンタに対してトリガを掛けるが、データポインタとかメモリ上の値に対してトリガを掛けられるようにする
  • コードに対してシンタックスハイライトとか自動インデントとか補完とかしたい(エディタとしての機能をつける)
  • デバッグOFF時の性能向上

ということで半分ぐらい実装できてないですが、便利ではあるのでぜひ使ってみてください! もし欲しい機能やバグがあれば、

github.com

このリポジトリにIssueを立てるか、自分で実装してPull Requestを投げてください!

ではよきBrainf*ckプログラミングライフを!

いろいろなBrainf*ck処理系における値の0初期化、ムーブ、コピー、便利なイディオム 【Brainf*ck Advent Calendar 2019 5日目】

この記事はBrainf*ck Advent Calendar 2019 5日目の記事です。

adventar.org

4日目の記事はmatsu7874さんによる「RustでBrainfuckインタプリタを実装した話を書けるだろうか?」の予定です。 6日目の記事はあんでぃ@量産型テ徒???? /-500/さんによる

unidentifiedexe.hatenablog.com

です。

この記事は

adventar.org

5日目の記事でもあります。空いていたので埋めました。 4日目の記事はnakarioさんによる

qiita.com

6日目の記事はdnek_さんによる

www.dnek.app

でした。

Brainf*ck処理系同士の非互換性

Brainf*ckの処理系(コンパイラおよびインタプリタ)にはもとの言語仕様の曖昧さ等から、様々な細かい仕様の違いが存在します。

例えば、EOFの扱いで、多くの処理系では、 . を実行したときにEOFに到達していた場合は0または-1が格納されます。

これについては、予め実行する処理系がわかっていれば、比較的簡単に対処することができる場合が多いです*1

他にも用意されるセルサイズや、負番地への進入・アクセスができるか、文字コードの扱いなどの違いもあります。

しかし、最も対処が大変な差異の一つが、一つのセルに格納できる値の範囲と、セルの値がオーバーフローした際の挙動です。

値の範囲とオーバーフローの扱いについてざっと上げられるだけでも、

  • セルサイズ: 1bit、8bit、16bit、32bit、多倍長など
  • 値は符号付きか符号なしか、符号付きの場合の表現方法
  • オーバーフロー時にwrap-aroundするか、saturateするか、多倍長整数によりオーバーフローが起こらないか、はたまた実行時エラーになるか
    • wrap-around: オーバーフロー時に反対側(最大値に1を足してでオーバーフローしたなら最小値、最小値から1を引いてオーバーフローしたなら最大値になる)
    • saturate: オーバーフロー時の結果を表現できる値に切り詰める(最大値に1足しても最大値のまま、最小値から1引いても最小値のまま)
    • bignum: 多倍長整数を使って値を格納するので、原理上オーバーフローは起こらず、(メモリの許す限り)任意の大きさの数を格納できる
    • runtime error: オーバーフローでランタイムエラーになる

といった違いがあります。 符号の有無とオーバーフローの挙動を表にするとこんな感じで少なくとも8通りが考えられるわけです。

符号 あり なし
wrap-around 1 2
saturate 3 4
bignum 5 6
runtime error 7 8

wrap-aroundの場合は符号の有無はあまり関係ない(符号付きで2の補数じゃないBrainf*ck処理系、ある…?) wrap-aroundが一番多く、例としてはUbuntuのaptで入るbfUbuntu – Details of package bf in bionicのデフォルト挙動とか。 bfはオプションでwrap-aroundではなくruntime errorにすることもできる。

0初期化とムーブ、コピー

ここで問題になるのが、あるセルに対して、その値を0にしたい、あるいはコピーやムーブといった基本操作がしたいというときです。

ムーブはあるセルの値を他のセルに代入し、元のセルの値は0にするという操作です。はたまた コピーはあるセルの値を他のセルに代入し、かつ元のセルの値はそのまま保持する操作です。

brainf*ckでは大抵の操作が破壊的操作なため、ムーブよりコピーのほうが複雑で、値のコピーはかなり重要なテクニックになります。

これらの処理はwrap-around環境では簡単で、0初期化なら[-]あるいは[+]で0初期化できます。 また、符号なしの場合はどの仕様でも(最適化がしょぼくて時間がかかるかもしれませんが)[-]で常に0初期化できます。 隣のセルへの値のムーブも[>+<-]で行うことができ、それを応用して[>+>+<<-]>>[<<+>>-]などで隣のセルへ値をコピーできます。

問題は符号ありでwrap-aroundでない場合で、たとえばセルの値が負の数の場合に[-]を実行すると永久に終わらないか実行時エラーになってしまいます。

これに対する対策はいくつかあります。まず簡単なものとして2つあり、

  1. セルに入っている値の符号がわかっている場合: 0初期化なら符号に応じて[-][+]を使い分ける。ムーブなら[>+<-][>-<+]を使い分ける。符号なしの場合は[-][>+<-]だけでできるのはこれの特殊な場合。
  2. セルに入っている値の範囲(a<=x<=b)がわかっている場合(runtime error環境の場合は、さらにb-aがオーバーフローしないこと): aを引くことで非負の値にすることができ、あとは0初期化なら[-]を実行し、ムーブなら[>+<-]を実行し、aを足せば良いです。これにより、saturate環境での0初期化が行えます(最小値の絶対値(あるいはそれ以上の値)を足す)。saturate環境では、aの減算でsaturateが起こる可能性があるので、このままではムーブはできませんが、そもそもsaturate環境で情報を失わずに値を更新することが不可能なため、これはあきらめて、自前で値の範囲を管理して、saturateが起こらない範囲で計算すべきです。

さて、問題はこのどちらの仮定も満たさない場合です。 Brainf*ckにはセルの値の符号を直接確認する方法がないため、1つめの方法に帰着するのは難しそうです。一方、bignum環境ではセルの値の範囲は全くわからないため、2つめの方法に帰着するのも難しそうです。

ちなみにruntime error環境やsaturateまたはwrap-aroundだが値の範囲が232とか264とかめちゃくちゃでかく、かつ値の0初期化やムーブ、コピーに対する最適化がない場合、saturateより更に厳しく、絶対値の大きい値をいじると死にうる*2ので、でかい値にしないように値の範囲の制御を常に頑張る以外の選択肢はないです。

3. 単調減少/増大列と大小比較による方法

特定の範囲内に値があるかを判定する

Brainf*ckではうまく工夫することによって、あるセルの値が指定した範囲内にあるか判定することができます。 いま、隣り合う2セルがあり、左側のセルの値が正であることがわかっているとしましょう。

0 1 2 3 4 5 6 7
0 1 1 x(>0) y 0 0 0

この例では3番地と4番地の値x,yについて、0<=y<xであるかを判定したく、3番地の値xが正であるとしましょう。 上の表のように値がセットされており、いまポインタが0番地にあるとすると、

>>>
[
    [->]>>+<<<<<[<]>>>
]
>>>

これを実行すると最終的にポインタは6番地に移動し、もし0<=y<xであるならば6番地の値が正(x-y)になり、そうでなければ0になります。 本質は[->]で、「ポインタの指す先が0でないなら1を引き、ポインタを1進める」という処理になります。このループの開始直前はポインタは3番地にあり、その値は正(0<x'<=x)です(0になっていれば外側のループを抜けるため)。 そのため、まずx'から1を引き、ポインタは4番地に移動します。4番地の値y'が0ならそこでループが終了し、そうでないなら1を引いて5番地に進みます。

ここで、ループ終了時のアドレスがずれているのがポイントで、その後の+の足す先がずれます。これによりループ中で4番地の値y'が0になったかどうかを検出することが可能になります。 単純なBrainf*ckプログラミングでは、ループ内でポインタが徐々に移動させるとループ終了時にポインタの指す先がずれて、この後のプログラムの実行が大変になるので、そのようなコーディングは避けられがちですが、こういう場面では非常に役に立ちます。 その後、[<]の直前ではポインタは1番地または2番地を指しており、1,2番地が1で0番地が0なので[<]の直後ではポインタはどちらの場合でも0番地になり、分岐していたアドレスが統一されます。 これにより外側のループの中身の終了時に3番地にいることが保証され、0<x'<=xの間ループを回すことが可能になります。

ということで、任意の値yが範囲0<=y<xにあるかどうかを判定することができました。これを任意の範囲a<=y<bにしたいときは、式変形をして0<=(y-a)<(b-a)、つまりyからaをひき、かつx=b-aとすればよいです。

bignum環境における0初期化

もし仮にyがa<=y<bを満たすなら、2番目の方法の通り、y-aは非負なので、[-]によって0初期化できます。しかし、bignum環境では値の範囲がわからないので予めa,bを決めてしまうと、もし範囲内になかったときにどうしようもなくなってしまいます。

そこで、次のように考えます。a,bを決め打つのではなく、a_0<=y<b_0, a_1<=y<b_1, a_2<=y<b_2, ...のような条件式を無限に作り、もしこれを満たすa_n,b_nがあればy-anに対して[-]をすれば0初期化できます。 このようなnが常にするためには、a_0>a_1>a_2>..., b_0<b_1<b_2<...かつa_nは負の無限大に発散し、b_nは正の無限大に発散すれば良いです*3

Brainf*ckでこのような列を作る方法として簡単な方法として、値に1を引く/足す、あるいは定数倍するという方法があります。1回の比較にO(b-a)かかることを考えると、毎回定数倍してa_n, b_nを指数的に変化させる方が良いでしょう。

これを踏まえた実装は次のとおりです。4番地を0初期化したいとします。

>+>+>+[
  [>++>++<<-]>>[<<++>>-]<<
  [
    [->]>+<<<<[<]>>>>>[<<[-]<-<->>>>>[-]<-]<<
  ]
  >>>[<<<+>>>-]<<<
]

1回ループを実行するとyがy-a-(b-a)=y-bに変化しますが、aやbを毎回4倍しているので、判定範囲は正と負の両方に単調増大し、結果的にyがどんな値でも0初期化が可能です。また、yが0になった瞬間にループを抜けられるような作りになっています。

ムーブやコピーもこのテクニックを応用することで可能です。ぜひ考えてみてください。

非負整数ペアによる整数表現

ここまで符号も範囲もわからない数を相手になんとかプログラムする方法を扱ってきましたが、整数を扱う方法は直接セルに値を格納するだけではありません。 ここでは非負整数のペア(二つ組)によって整数を扱う方法を紹介します。

具体的には、非負整数のペア(a, b)は整数a-bを表すことにします。このようにすることによって、整数演算を非負整数の演算に帰着することができます。

  • 足し算: (a, b) + (c, d) = (a+c, b+d)
  • 引き算: (a, b) - (c, d) = (a+d, b+c)
  • 掛け算: (a, b) * (c, d) = (ac+bd, ad+bc)
  • 等号比較: (a, b) = (c, d) ⇔ a+d = b+c
  • 大小比較: (a, b) < (c, d) ⇔ a+d < b+c
  • 割り算: 上5つの演算を組みあわせることによって実現可能 ここで、a,b,c,d同士の演算として足し算と掛け算しか出てきていないことに着目すると、(オーバーフローがなければ)これらの計算によってペアの中身が負になることはなく、非負整数で演算が閉じている、つまりちゃんと整数演算を非負整数の演算に帰着できていることがわかります。 非負整数同士の演算はBrainf*ck界でもよく知られているように、そんなに大変ではないので、だいぶ楽になると思います。

この方法により負の数を登場させなければ、符号なし環境のように単純なコードでプログラミングすることができます。

ただし、足し算と掛け算しか出てこないため、演算のたびに数値はどんどん大きくなります。したがって、オーバーフローのある環境では演算を繰り返すうちに(たとえ真の値a-bの絶対値が小さくても)オーバーフローが起こる可能性があります。これは、オーバーフローする前にaとbの大小比較を行い、a>=bなら(a-b, 0)、a<bなら(0, b-a)と"標準化"することで回避できます(そのぶんコードは増えますが、生の整数を扱うよりは楽ではないでしょうか)。

このへんはコード長やメモリ消費量、プログラミングのしやすさなどを見極めながら適宜選択していくことになるでしょう。

Q: bignum環境って見たことないんだけど

A: 私がさっき作った

github.com

ゆっくりしていってね

まとめ

  • Brainf*ckの処理系には非互換性がある
  • 特にオーバーフローまわりはいろいろある
  • それにより0初期化・ムーブ・コピーといった基本操作に困難が発生する場合がある
  • ちょっとしたテクニックで対策は可能
  • 整数を直接扱わず、非負整数操作に帰着することも可能
  • bignum環境を作ったので遊んでみてね!

*1:バイナリ入力でEOFが0あるいは符号なしで255だと普通のデータと区別付かなくて困りますが

*2:runtime errorになったり非現実的な時間がかかったりする

*3:a_n, b_nが整数列なので発散することは単調減少/増大列であることから従います