「 ABC203の D問題って なんで突然 難しいんだぜ?」
「 👆 D問題は、緑コーダーや、青コーダーが解くぐらいの難しさみたいよ」
「 その図を見ると 黄色コーダーじゃないと 全完 できないじゃないか」
「 灰色でも全完してるとばかり思っていたが そんなことはなかった」
「 D が解けるようなら 実力は 茶色より上よ。 D を解きなさいよ」
「 10年ぐらい前の 二郎ラーメン大宮店初見客の『大盛』『大盛でいいんすか』『大丈夫、食えっから』 の伝説を感じるぜ」
「 Dが手の届かない壁なら E、Fは 大人になるのは1000年先だろう ぐらいに思っていた毛の生えていない小学生から見た大人ぐらいの気分だが
タイトルに Beginner と入っているコンテストで全完できないのは 煽られている気分なんで まず D をなんとかしようぜ?」
「 お父んが思ってるより AtCoder 全体のレベルが高いのでは?
ABC の後ろに AtCoder Regular Contest や、 AtCoder Grand Contest があるぜ?
だからやっぱり AtCoder Beginner Contest は、 AtCoder の中で ビギナーレベルなんだぜ」
「 ぜったい世間に そう思われてないと思うけどな。 ビギナーなプログラマーがやるコンテスト だと思われているはずだぜ」
「 思っているより 青の下位のレベルが難しいのが分かったのよ」
「 黄色コーダーや 赤コーダーでないと ビギナーと名の付いているコンテストを 全完 できないのかだぜ!」
📖 解説
「 じゃあ 累積和で元を辿っていくと出てくる いもす法 というのを調べるかだぜ」
📖 いもす法
「 👆 Ponanza Chainer んトコの会社じゃないか」
「 芋とまったく関係ない……? 焼きなまし法でもない……?」
「 分からない単語を 1つ1つ 埋めていこうぜ。
2次元1次 って何だぜ? 次が衍字(えんじ)なのか、元が脱字(だつじ)なのか?」
「 2次元なら 2次な気がするが、 2元1次 のことだろうか?」
「 👆 変数が2つなら2元、 2乗みたいなやつが どこにも付いてないから 1次 だぜ」
「 👆 絵がヘタクソで歪んでいるが 一次式(比例してるやつ)を満たす x と y の交点を 結んでいくと 直線になるぜ。
そりゃ めでてぇ! ってことで 一次式のことを 線形 と呼ぶことがあるぜ。 反比例してると違うけど」
「 この いもす の記事、2012年だぜ! そしてリンクをクリックしたら……」
「 👆 このページって Linux でアクセスしたら どうなんの?」
「 👆 ×ボタンをクリックするのも何が仕掛けられてるか分からないので、タスク・マネージャーから強制終了しろだぜ」
「 ちょっとPCを再起動してみようぜ? 再起動できるかな?」
「 👆 1次式でも、反比例のやつは 線形じゃないな。 そういえば 反比例なんてのもあったな」
「 中学の数学の先生が グラフの こう ぐいっとした感じとか 向きみたいな感じが 大事だから覚えておけって言ってたけど、
いつ役に立つ日が来るのかしら?」
「 大人になっても まだ数学やってたら この ぐいっとした感じを使うしかないな。
もう数学やってなかったら 使ってないな」
「 で、 いもす式 というのは 2次? 2次元? より大きな次元? でも便利というのが 2012年の研究成果のようだぜ」
「 👆 0次ってのは xが変化しても変わらないようなyだな。つまり定数」
「 お父んの説明を聞いても 次元 と 次 の違いが分からんなあ。
お父んの図を見ると 0次 と 1次元 が同じに見えるぜ」
「 👆 0次 というのは、 xがどんなに変わっても、yは動けね、という 動けないことを言ってんだぜ」
「 👆 0次元 というのは、 ここから動けね、 ということを 言ってんだぜ。ただ居るだけ」
「 👆 1次 というのは、 xが変われば、yは上下に動く、ということを言ってんだぜ」
「 👆 1次元 というのは、 道路の上みたいに動ける、ということを言ってんだぜ」
「 道路が 水槽になっても 便利に使えるんだろ。さらに上は 四次元 なんで、ネクタイ結んでも すかすかで首からずり落ちるぜ。
四次元を説明すると脱線するぜ」
「 はあー 分かんね。1次元上に0次関数を足すって 何なんだぜ?」
「 👆 1次元上 って、ジャンプできないスーパーマリオブラザーズみたいなもんだぜ」
「 👆 0次関数 って、xがどう変わっても、yが変わらないやつらだぜ」
「 👆 ひとまず 前後に動ける1次元の上には、xが動ける0次関数は 置けそうよね。
それで、yは動かないのよ」
「 👆 同じ高さの空中を飛んでるとでも思えだぜ。ジュゲムみたいに」
「 次元 は勝手に動いてしまう方向で、 次 は動きたい方向かだぜ?」
「 👆 足すということなんで、被ってるとこを ちょいと 切り取り 貼りつけ」
「 これは 1次元の場合なのよ。 いもす法は、 2次元でも 3次元でも 便利らしいのよ」
「 なんで こいつらは こんな奇妙なことを やってるんだぜ?」
「 👆 2次元上の1次関数に、1次関数を足すと こんな感じかだぜ?」
📖 ポピュラス
「 しかし だんだん 知ってる世界に近づいてきている気がするぜ」
「 いもす法 の、もう少し先の文章を読むと 発想がヤバいな……。
とりあえず 今日は寝る」
「 👆 0次関数が飛んでるとしようぜ?
ループでいうと 1~6 の間を 5ステップだぜ。
T は タイムと思えだぜ。問題の範囲みたいなもんだぜ。タイムがいくつかは問題文で教えてもらえだぜ。 T = 7
」
「 👆 2匹置いとこかな。 C は 何匹かを表していると思えだぜ。 C = 2
。 タイムは T = 10
。
じゃあ こいつらを 足してくれだぜ」
「 👆 現代のコンピューターは 並列処理をするのでもなければ 逐次実行計算だしな。
テープを順に読んでいく感じだぜ。テープって、セロテープじゃないぜ。
これ、 C × T
。 掛け算記号はめんどくさいんで省くんで CT
」
「 AtCoder は O(C × T)
なんていう計算量のプログラムを提出すると 0点 を付けてくるところなのよ。
O(C + T)
じゃないとダメなのよ」
「 腹の底から わらう。 掛け算を 足し算に入れ替えることができれば プログラマーは苦労しないぜ」
「 C + T
じゃなくて、 O(C + T)
なんだけどな。定数倍ぐらいは増えるぜ」
「 それと、C と T は変数なんで、無限の組み合わせがあって想像できないから、ぐいっとした感じをイメージしろだぜ」
「 コロナ・ウィルスは 掛け算の速さで感染するけど、掛け算の増え方の速さを知らない人は 感染者数の増え方は 足し算ぐらいの速さに思ってるのよ」
「 将棋や囲碁をやってるやつには、1手深く読もうとしたら枝が増えるあれ、と言えば 分かるだろ」
「 👆 いもす法 の発想は、表を横線で見るのではなく、縦線で見ましょう、というだけだぜ」
「 もう こんな記事読まなくていいわよ。凡人は天才のやってることを伝承するだけしかできないんだから」
「 👆 いもす法のアイデアは 入り口と 出口の2か所だけ押さえておけばいい、というやつだぜ。
入り口で 1増えたんだったら、 出口では 1減ったんだな」
「 そうでない愚直なやり方だと、 x=1 のとき y=1、 x=2 のときも y=1 と全部 押さえていたな」
「 👆 増えたところと、いなくなったところの2つを押さえるだけなら計算量はたかだか 2×C
、 計算量オーダーは O(C)
だな。
これが いもす法は 前準備をするタイプのアルゴリズムと言われているところだぜ」
「 問題文は 始まりと 長さがセットで渡されたりするから、入力1つ読み取るとともに 前準備の1ステップが完了するわよ」
「 じゃあ T (タイム)を進めていこうぜ。これ、シミュレート」
「 右から左へ1回進んでいるだけなのに デコボコが でけたぜ」
「 いもす法は これが 多次元でも 便利だと言っているのよ」
「 👆 この絵にも 前処理と シミュレートを やってみろだぜ」
「 👆 シミュレートは 水平の筋に沿って 行うとしましょう」
「 👆 入り口と出口は ここに置いておけば 1次元0次関数の出入口が縦に並んでいるのを 上から見るのと同じね」
「 その図の 並んでいる出入口も 1次元0次関数の形になっているから
さらに基本アイデアを使って オーダーを下げるのが いもす法 の研究成果なのだろう」
「 👆 これで前処理すればいいのは 8個 になったぜ。
青い枠に4つの点、赤い枠に4つの点があると考えれば 4C
、 オーダーにすれば 4の定数倍を消して O(C)
だぜ」
「 👆 シミュレートする方向は X方向と Y方向があるので、それを含めても O(C + XY)
。
前処理が C で、シミュレートが XY として、別々の処理なんで 足し算で済んでいるんだぜ」
「 いもす法を使わなければ 盤面全スキャンを 枠の数だけして O(CXY)
かな」
「 👆 四角形じゃなくても いもす法 が使えるという例で 3角形のサンプルが示されているので 見ておくかだぜ」
「 👆 この ボーリングのピンみたいな1が どんな前処理だったの、というのを 逆算していくぜ」
「 👆 桃色の筋に沿って 1 で初めて -1 で終わろうぜ。
また 1次元上の0次関数 が見えるな」
「 👆 黄緑色の筋に沿って 入り口と 出口を置こうぜ。
うまいこと 1次元上の0次関数が並んでいるのが見えるな」
「 👆 描くとこ狭かったんで 水色の筋に沿って x軸を逆向きにシミュレートするものとみなして
前処理を逆算すると こうだぜ」
「 👆 いもす法 を使う事で、 九九の表の 対角線上の数を作れるそうだぜ」
「 別に 九九の表の対角線上の数なんか いもす法で 求めたくないけどな」
「 👆 2次 の ぐいっとした感じ を思い出しておいてくれだぜ」
「 👆 最初は 1を2つ並べるそうだぜ。空いてるとこは 0 な」
「 ガウス関数分かんね。以上で いもす法 の勉強 終わりだぜ」
「 👆 じゃあ逆に、これ シミュレートしていったら キューブになんの?」
「 こんなパッチワーク見ても おもんないぜ。
わたしたちは数学がやりたいんだぜ」
「 👆 平面の矩形のリクツには収まらんのかも知らん。展開図にしよ」
「 こいつら、キューブになるという目的を忘れてんじゃないかだぜ?」
「 👆 35は 5と7 の素数の合成数なんで、立方体にはならないぜ」
「 橙色は 64 にならなかったな。累計和を続けても、キューブにはならないのか……」
Crieitは個人で開発中です。
興味がある方は是非記事の投稿をお願いします! どんな軽い内容でも嬉しいです。
なぜCrieitを作ろうと思ったか
また、「こんな記事が読みたいけど見つからない!」という方は是非記事投稿リクエストボードへ!
こじんまりと作業ログやメモ、進捗を書き残しておきたい方はボード機能をご利用ください!