ABCのD問題って、何なの(^~^)!

ぱじゅー(^~^)! 公開下書き

ABCのD問題って、何なの(^~^)!

20210124shogi2a2b1.png
「 ABC203の D問題って なんで突然 難しいんだぜ?」

kifuwarabe-futsu.png
「 諦めたか」

📖 AtCoder Beginner Contest

ohkina-hiyoko-futsu.png
「 👆 D問題は、緑コーダーや、青コーダーが解くぐらいの難しさみたいよ」

ramen-tabero-futsu2.png
「 その図を見ると 黄色コーダーじゃないと 全完 できないじゃないか」

kifuwarabe-futsu.png
「 黄色コーダーになれよ」

ramen-tabero-futsu2.png
「 灰色でも全完してるとばかり思っていたが そんなことはなかった」

ohkina-hiyoko-futsu.png
「 D が解けるようなら 実力は 茶色より上よ。 D を解きなさいよ」

ramen-tabero-futsu2.png
「 10年ぐらい前の 二郎ラーメン大宮店初見客の『大盛』『大盛でいいんすか』『大丈夫、食えっから』 の伝説を感じるぜ」

kifuwarabe-futsu.png
「 その例えでは 誰も分からん」

ramen-tabero-futsu2.png
「 Dが手の届かない壁なら E、Fは 大人になるのは1000年先だろう ぐらいに思っていた毛の生えていない小学生から見た大人ぐらいの気分だが
タイトルに Beginner と入っているコンテストで全完できないのは 煽られている気分なんで まず D をなんとかしようぜ?」

kifuwarabe-futsu.png
「 お父んが思ってるより AtCoder 全体のレベルが高いのでは?
ABC の後ろに AtCoder Regular Contest や、 AtCoder Grand Contest があるぜ?
だからやっぱり AtCoder Beginner Contest は、 AtCoder の中で ビギナーレベルなんだぜ」

ramen-tabero-futsu2.png
「 ぜったい世間に そう思われてないと思うけどな。 ビギナーなプログラマーがやるコンテスト だと思われているはずだぜ」

kifuwarabe-futsu.png
「 なんで 人の目を気にするんだぜ。ほっとけだぜ」

ohkina-hiyoko-futsu.png
「 思っているより 青の下位のレベルが難しいのが分かったのよ」

ramen-tabero-futsu2.png
「 黄色コーダーや 赤コーダーでないと ビギナーと名の付いているコンテストを 全完 できないのかだぜ!」

kifuwarabe-futsu.png
「 まだ言うか!」

ohkina-hiyoko-futsu.png
「 早く赤コーダーにさせましょう。 うるさいから」

Pond

📖 解説

ohkina-hiyoko-futsu.png
「 👆 解説が出てるわよ」

ramen-tabero-futsu2.png
「 じゃあ 累積和で元を辿っていくと出てくる いもす法 というのを調べるかだぜ」

📖 いもす法

kifuwarabe-futsu.png
「 👆 Ponanza Chainer んトコの会社じゃないか」

ramen-tabero-futsu2.png
「 芋とまったく関係ない……? 焼きなまし法でもない……?」

kifuwarabe-futsu.png
「 分からない単語を 1つ1つ 埋めていこうぜ。
2次元1次 って何だぜ? が衍字(えんじ)なのか、が脱字(だつじ)なのか?」

ramen-tabero-futsu2.png
「 2次元なら 2次な気がするが、 2元1次 のことだろうか?」

20210531math59.png

ramen-tabero-futsu2.png
「 👆 変数が2つなら2元、 2乗みたいなやつが どこにも付いてないから 1次 だぜ」

20210531math59a1b2.png

ramen-tabero-futsu2.png
「 👆 絵がヘタクソで歪んでいるが 一次式(比例してるやつ)を満たす x と y の交点を 結んでいくと 直線になるぜ。
そりゃ めでてぇ! ってことで 一次式のことを 線形 と呼ぶことがあるぜ。 反比例してると違うけど」

kifuwarabe-futsu.png
「 この いもす の記事、2012年だぜ! そしてリンクをクリックしたら……」

20210531blog56.png

ohkina-hiyoko-futsu.png
「 👆 このページって Linux でアクセスしたら どうなんの?」

20210531blog57.png

📖 【注意喚起】マイクロソフトセキュリティアラームにご注意

ramen-tabero-futsu2.png
「 👆 ×ボタンをクリックするのも何が仕掛けられてるか分からないので、タスク・マネージャーから強制終了しろだぜ」

kifuwarabe-futsu.png
「 ちょっとPCを再起動してみようぜ? 再起動できるかな?」

ramen-tabero-futsu2.png
「 おっ、再起動でけた でけた……」

20210531math60.png

ramen-tabero-futsu2.png
「 👆 1次式でも、反比例のやつは 線形じゃないな。 そういえば 反比例なんてのもあったな」

ohkina-hiyoko-futsu.png
「 中学の数学の先生が グラフの こう ぐいっとした感じとか 向きみたいな感じが 大事だから覚えておけって言ってたけど、
いつ役に立つ日が来るのかしら?」

ramen-tabero-futsu2.png
「 大人になっても まだ数学やってたら この ぐいっとした感じを使うしかないな。
もう数学やってなかったら 使ってないな」

ramen-tabero-futsu2.png
「 で、 いもす式 というのは 2次? 2次元? より大きな次元? でも便利というのが 2012年の研究成果のようだぜ」

kifuwarabe-futsu.png
「 じゃあ 1次元0次 って何だぜ?」

20210531math61.png

ramen-tabero-futsu2.png
「 👆 0次ってのは xが変化しても変わらないようなyだな。つまり定数」

20210531math62.png

ramen-tabero-futsu2.png
「 👆 1次元ってのは、線の上を動く気分のやつだな」

kifuwarabe-futsu.png
「 お父んの説明を聞いても 次元 と  の違いが分からんなあ。
お父んの図を見ると 0次 と 1次元 が同じに見えるぜ」

20210531math63.png

ramen-tabero-futsu2.png
「 👆 0次 というのは、 xがどんなに変わっても、yは動けね、という 動けないことを言ってんだぜ」

20210531math64.png

ramen-tabero-futsu2.png
「 👆 0次元 というのは、 ここから動けね、 ということを 言ってんだぜ。ただ居るだけ」

kifuwarabe-futsu.png
「 フーム」

20210531math65.png

ramen-tabero-futsu2.png
「 👆 1次 というのは、 xが変われば、yは上下に動く、ということを言ってんだぜ」

20210531math66.png

ramen-tabero-futsu2.png
「 👆 1次元 というのは、 道路の上みたいに動ける、ということを言ってんだぜ」

kifuwarabe-futsu.png
「 フーム」

ohkina-hiyoko-futsu.png
「 いもす法は、 もっと高次元 の空間でも便利らしいのよ」

ramen-tabero-futsu2.png
「 道路が 水槽になっても 便利に使えるんだろ。さらに上は 四次元 なんで、ネクタイ結んでも すかすかで首からずり落ちるぜ。
四次元を説明すると脱線するぜ」

1次元上に0次関数を足すとは?

kifuwarabe-futsu.png
「 はあー 分かんね。1次元上に0次関数を足すって 何なんだぜ?」

20210531math67.png

ramen-tabero-futsu2.png
「 👆 1次元上 って、ジャンプできないスーパーマリオブラザーズみたいなもんだぜ」

kifuwarabe-futsu.png
「 はあー 0次関数って何だぜ?」

20210531math68.png

ramen-tabero-futsu2.png
「 👆 0次関数 って、xがどう変わっても、yが変わらないやつらだぜ」

kifuwarabe-futsu.png
「 はあ~~~~」

20210531math69.png

ohkina-hiyoko-futsu.png
「 👆 ひとまず 前後に動ける1次元の上には、xが動ける0次関数は 置けそうよね。
それで、yは動かないのよ」

kifuwarabe-futsu.png
「 はあー 何をやってるんだぜ、こいつらは?」

20210531math70.png

ramen-tabero-futsu2.png
「 👆 同じ高さの空中を飛んでるとでも思えだぜ。ジュゲムみたいに」

kifuwarabe-futsu.png
「 次元 は勝手に動いてしまう方向で、  は動きたい方向かだぜ?」

ramen-tabero-futsu2.png
「 次(つぎ)というぐらいだしな」

kifuwarabe-futsu.png
「 お父んが 適当だぜ、はあ~~~~~~」

kifuwarabe-futsu.png
「 じゃあ 0次関数 を足してみてくれだぜ」

20210531math70a1.png

ramen-tabero-futsu2.png
「 👆 2匹飛んでるだぜ、0次関数が」

kifuwarabe-futsu.png
「 はあ~~~~~~~~」

20210531math70a2.png

ramen-tabero-futsu2.png
「 👆 足すということなんで、被ってるとこを ちょいと 切り取り 貼りつけ」

20210531math70a3.png

ramen-tabero-futsu2.png
「 👆 3匹に増えたぜ」

kifuwarabe-futsu.png
「 はあ~~~~~~~~~~~~~~~~」

ohkina-hiyoko-futsu.png
「 これは 1次元の場合なのよ。 いもす法は、 2次元でも 3次元でも 便利らしいのよ」

20210531math71.png

ramen-tabero-futsu2.png
「 👆 2次元上の1次関数 も、もちろん描けるぜ」

kifuwarabe-futsu.png
「 なんで こいつらは こんな奇妙なことを やってるんだぜ?」

20210531math71a1b1.png

ramen-tabero-futsu2.png
「 👆 2次元上の1次関数に、1次関数を足すと こんな感じかだぜ?」

📖 ポピュラス

kifuwarabe-futsu.png
「 👆 ポピュラスみたいだな」

kifuwarabe-futsu.png
「 しかし だんだん 知ってる世界に近づいてきている気がするぜ」

20210531math72.png

ramen-tabero-futsu2.png
「 👆 3次元上の2次関数は 加速するぜ」

kifuwarabe-futsu.png
「 なんか 思ってたのと違うな……」

ohkina-hiyoko-futsu.png
「 なんでそうなるの!? 平面上を歩かないの?」

ramen-tabero-futsu2.png
「 2元じゃなくて 1元だしな」

kifuwarabe-futsu.png
「 じゃあ 3次元というのは 3次3元のことかだぜ?」

ramen-tabero-futsu2.png
「 3次1元だな。N×N×N。1は略すので3次、元」

kifuwarabe-futsu.png
「 こんな適当で D問題を取れるのだろうか……?」

ramen-tabero-futsu2.png
「 いもす法 の、もう少し先の文章を読むと 発想がヤバいな……。
とりあえず 今日は寝る」

愚直なやり方と、いもす法のやり方の比較

20210601math1a2b2.png

ramen-tabero-futsu2.png
「 👆 0次関数が飛んでるとしようぜ?
ループでいうと 1~6 の間を 5ステップだぜ。
T は タイムと思えだぜ。問題の範囲みたいなもんだぜ。タイムがいくつかは問題文で教えてもらえだぜ。 T = 7

20210601math1a1b2.png

ramen-tabero-futsu2.png
「 👆 2匹置いとこかな。 C は 何匹かを表していると思えだぜ。 C = 2。 タイムは T = 10
じゃあ こいつらを 足してくれだぜ」

kifuwarabe-futsu.png
「 Y を足すということかだぜ?」

ramen-tabero-futsu2.png
「 そうだぜ」

20210601math1a3.png

kifuwarabe-futsu.png
「 👆 こうだぜ」

ohkina-hiyoko-futsu.png
「 重なってるところを足すなんて カンタンじゃないの」

ramen-tabero-futsu2.png
「 それは最初に全体図を見たからだぜ」

20210601math4a2b1c1.png

ramen-tabero-futsu2.png
「 👆 現代のコンピューターは 並列処理をするのでもなければ 逐次実行計算だしな。
テープを順に読んでいく感じだぜ。テープって、セロテープじゃないぜ。
これ、 C × T。 掛け算記号はめんどくさいんで省くんで CT

ramen-tabero-futsu2.png
「 オーダーで言うと O(CT)

ohkina-hiyoko-futsu.png
「 AtCoder は O(C × T) なんていう計算量のプログラムを提出すると 0点 を付けてくるところなのよ。
O(C + T) じゃないとダメなのよ」

kifuwarabe-futsu.png
「 腹の底から わらう。 掛け算を 足し算に入れ替えることができれば プログラマーは苦労しないぜ」

20210601math5a0b1.png

kifuwarabe-futsu.png
「 👆 言ってしまえば C + T って こんなんだぜ?」

ramen-tabero-futsu2.png
「 C + T じゃなくて、 O(C + T) なんだけどな。定数倍ぐらいは増えるぜ」

ramen-tabero-futsu2.png
「 それと、C と T は変数なんで、無限の組み合わせがあって想像できないから、ぐいっとした感じをイメージしろだぜ」

20210601math6.png

ramen-tabero-futsu2.png
「 👆 C × T の感じ」

20210601math7.png

ramen-tabero-futsu2.png
「 👆 C + T の感じ」

kifuwarabe-futsu.png
「 掛け算は ヤバい」

ohkina-hiyoko-futsu.png
「 コロナ・ウィルスは 掛け算の速さで感染するけど、掛け算の増え方の速さを知らない人は 感染者数の増え方は 足し算ぐらいの速さに思ってるのよ」

ramen-tabero-futsu2.png
「 将棋や囲碁をやってるやつには、1手深く読もうとしたら枝が増えるあれ、と言えば 分かるだろ」

20210601math8.png

ramen-tabero-futsu2.png
「 👆 いもす法 の発想は、表を横線で見るのではなく、縦線で見ましょう、というだけだぜ」

kifuwarabe-futsu.png
「 はい 天才。 解散」

ohkina-hiyoko-futsu.png
「 もう こんな記事読まなくていいわよ。凡人は天才のやってることを伝承するだけしかできないんだから」

20210601math8a0b1.png

ramen-tabero-futsu2.png
「 👆 いもす法のアイデアは 入り口と 出口の2か所だけ押さえておけばいい、というやつだぜ。
入り口で 1増えたんだったら、 出口では 1減ったんだな」

ramen-tabero-futsu2.png
「 そうでない愚直なやり方だと、 x=1 のとき y=1、 x=2 のときも y=1 と全部 押さえていたな」

20210601math8a1.png

ramen-tabero-futsu2.png
「 👆 増えたところと、いなくなったところの2つを押さえるだけなら計算量はたかだか 2×C、 計算量オーダーは O(C) だな。
これが いもす法は 前準備をするタイプのアルゴリズムと言われているところだぜ」

ohkina-hiyoko-futsu.png
「 問題文は 始まりと 長さがセットで渡されたりするから、入力1つ読み取るとともに 前準備の1ステップが完了するわよ」

kifuwarabe-futsu.png
「 隙が無いぜ。 C の数だけの前準備で終わるぜ」

20210601math9a1.png

20210124shogi2a2b1.png
「 じゃあ T (タイム)を進めていこうぜ。これ、シミュレート」

kifuwarabe-futsu.png
「 お父ん、余裕だな」

20210601math9a2.png

ramen-tabero-futsu2.png
「 T=1 のときに y は +1 だな」

ohkina-hiyoko-futsu.png
「 出入り(ではい -)をカウントするのね」

20210601math9a3.png

ramen-tabero-futsu2.png
「 👆 T=3 まで変化 無いな」

20210601math9a4.png

ramen-tabero-futsu2.png
「 👆 T=4 で y は +2 だな」

kifuwarabe-futsu.png
「 指し手が早いぜ。もう詰んでんだろな」

20210601math9a5.png

ramen-tabero-futsu2.png
「 👆 T=6 は変化無しだぜ」

20210601math9a6.png

ramen-tabero-futsu2.png
「 👆 T=7 のときに y は -1 だな」

20210601math9a6.png

ramen-tabero-futsu2.png
「 👆 T=9 まで変化無いな」

20210601math9a7.png

ramen-tabero-futsu2.png
「 👆 T=10 で y は -2 だな」

kifuwarabe-futsu.png
「 右から左へ1回進んでいるだけなのに デコボコが でけたぜ」

ohkina-hiyoko-futsu.png
「 いもす法は これが 多次元でも 便利だと言っているのよ」

20210601math10.png

ramen-tabero-futsu2.png
「 👆 この絵にも 前処理と シミュレートを やってみろだぜ」

20210601math11a3.png

ohkina-hiyoko-futsu.png
「 👆 シミュレートは 水平の筋に沿って 行うとしましょう」

20210601math11a2.png

ohkina-hiyoko-futsu.png
「 👆 入り口と出口は ここに置いておけば 1次元0次関数の出入口が縦に並んでいるのを 上から見るのと同じね」

ramen-tabero-futsu2.png
「 その図の 並んでいる出入口も 1次元0次関数の形になっているから
さらに基本アイデアを使って オーダーを下げるのが いもす法 の研究成果なのだろう」

20210601math11a4.png

ramen-tabero-futsu2.png
「 👆 垂直の筋に沿って シミュレートするとしようぜ?」

20210601math11a5.png

ramen-tabero-futsu2.png
「 👆 これで前処理すればいいのは 8個 になったぜ。
青い枠に4つの点、赤い枠に4つの点があると考えれば 4C、 オーダーにすれば 4の定数倍を消して O(C) だぜ」

ohkina-hiyoko-futsu.png
「 凄まじすぎるわねえ」

ramen-tabero-futsu2.png
「 👆 シミュレートする方向は X方向と Y方向があるので、それを含めても O(C + XY)
前処理が C で、シミュレートが XY として、別々の処理なんで 足し算で済んでいるんだぜ」

kifuwarabe-futsu.png
「 いもす法を使わなければ 盤面全スキャンを 枠の数だけして O(CXY) かな」

三角形で いもす法

20210601math12a1.png

ramen-tabero-futsu2.png
「 👆 四角形じゃなくても いもす法 が使えるという例で 3角形のサンプルが示されているので 見ておくかだぜ」

20210601math12a2.png

ramen-tabero-futsu2.png
「 👆 この ボーリングのピンみたいな1が どんな前処理だったの、というのを 逆算していくぜ」

20210601math12a3b1.png

ramen-tabero-futsu2.png
「 👆 桃色の筋に沿って 1 で初めて -1 で終わろうぜ。
また 1次元上の0次関数 が見えるな」

20210601math12a4.png

ramen-tabero-futsu2.png
「 👆 黄緑色の筋に沿って 入り口と 出口を置こうぜ。
うまいこと 1次元上の0次関数が並んでいるのが見えるな」

20210601math12a5.png

ramen-tabero-futsu2.png
「 👆 描くとこ狭かったんで 水色の筋に沿って x軸を逆向きにシミュレートするものとみなして
前処理を逆算すると こうだぜ」

ohkina-hiyoko-futsu.png
「 三角形の辺の両端を押さえているわねぇ」

二次関数で いもす法

20210601math13.png

ramen-tabero-futsu2.png
「 👆 いもす法 を使う事で、 九九の表の 対角線上の数を作れるそうだぜ」

ohkina-hiyoko-futsu.png
「 平方数ねぇ」

kifuwarabe-futsu.png
「 別に 九九の表の対角線上の数なんか いもす法で 求めたくないけどな」

20210601math14.png

ramen-tabero-futsu2.png
「 👆 2次 の ぐいっとした感じ を思い出しておいてくれだぜ」

20210601math15.png

ramen-tabero-futsu2.png
「 👆 最初は 1を2つ並べるそうだぜ。空いてるとこは 0 な」

kifuwarabe-futsu.png
「 出口は無いのかだぜ?」

ramen-tabero-futsu2.png
「 出口は無い」

kifuwarabe-futsu.png
「 じゃ、シミュレートしてくれだぜ」

20210601math15a1.png

ramen-tabero-futsu2.png
「 👆 ほい」

ohkina-hiyoko-futsu.png
「 0次が出てきたわねぇ」

kifuwarabe-futsu.png
「 次も、シミュレートしてくれだぜ」

20210601math15a2.png

ramen-tabero-futsu2.png
「 👆 ほい」

kifuwarabe-futsu.png
「 あれま。 奇数になったぜ」

kifuwarabe-futsu.png
「 次もシミュレートしろだぜ」

20210601math15a3.png

ramen-tabero-futsu2.png
「 👆 ほらよ」

kifuwarabe-futsu.png
「 出た」

kifuwarabe-futsu.png
「 ただ 足してるだけで そうなるのかだぜ?」

20210601math16a2.png

ramen-tabero-futsu2.png
「 👆 見てみろだぜ」

kifuwarabe-futsu.png
「 んあー?」

20210601math16a2.png

ramen-tabero-futsu2.png
「 👆 鳥になって上から見て 数えろよ」

kifuwarabe-futsu.png
「 鳥ー?」

20210601math16a3.png

ramen-tabero-futsu2.png
「 👆 曲がってるところは 伸ばせば 見やすくなるぜ」

kifuwarabe-futsu.png
「 こんなん 勝手に伸ばして いいのかだぜ?」

20210601math16a4.png

ramen-tabero-futsu2.png
「 👆 見事だぜ」

kifuwarabe-futsu.png
「 いや、何が見事なのか わからないが」

ramen-tabero-futsu2.png
「 ガウス関数分かんね。以上で いもす法 の勉強 終わりだぜ」

自習

20210601math16a1.png

ramen-tabero-futsu2.png
「 👆 じゃあ逆に、これ シミュレートしていったら キューブになんの?」

ohkina-hiyoko-futsu.png
「 なるんじゃない?」

kifuwarabe-futsu.png
「 やってみようぜ?」

20210603math17.png

ramen-tabero-futsu2.png
「 👆 ぱっと 思いつくのは こうだぜ」

kifuwarabe-futsu.png
「 こんなパッチワーク見ても おもんないぜ。
わたしたちは数学がやりたいんだぜ」

ohkina-hiyoko-futsu.png
「 赤<緑<水色<橙<紫<茶 の順番は満たしたくない?」

20210603math17a1.png

ramen-tabero-futsu2.png
「 👆 せいぜい、こう。 水色をどこに置くか思いつかない」

ohkina-hiyoko-futsu.png
「 正方形に収めてるけど、スケールしないんじゃない?」

20210603math17a3.png

ramen-tabero-futsu2.png
「 👆 平面の矩形のリクツには収まらんのかも知らん。展開図にしよ」

20210603math18.png

ramen-tabero-futsu2.png
「 👆 さらに シミュレート」

kifuwarabe-futsu.png
「 うわっ、マンデルブロー集合みたいで 気持ちわりっ」

20210603math19a1.png

ramen-tabero-futsu2.png
「 👆 さらに シミュレート」

kifuwarabe-futsu.png
「 こいつら、キューブになるという目的を忘れてんじゃないかだぜ?」

20210603math20.png

ramen-tabero-futsu2.png
「 👆 さらに シミュレート」

ohkina-hiyoko-futsu.png
「 見てて 面白いものじゃないわね」

kifuwarabe-futsu.png
「 緑色の数字の 8 は もうキューブになってるのでは?」

20210603math21.png

ramen-tabero-futsu2.png
「 👆 35は 5と7 の素数の合成数なんで、立方体にはならないぜ」

ohkina-hiyoko-futsu.png
「 水色は さっき 27 だったわよ?」

ramen-tabero-futsu2.png
「 橙色は 64 にならなかったな。累計和を続けても、キューブにはならないのか……」

D問題

ohkina-hiyoko-futsu.png
「 いもす法を 覚えただけでは D問題は解けないのよ」

kifuwarabe-futsu.png
「 わらう」

ramen-tabero-futsu2.png
「 解説読んでも 見ても 分からんしな。どうすっかな」

何度でもクリック!→

むずでょ@きふわらべ第29回世界コンピューター将棋選手権一次予選36位

光速のアカウント凍結されちゃったんで……。ゲームプログラムを独習中なんだぜ☆電王戦IIに出た棋士もコンピューターもみんな好きだぜ☆▲(パソコン将棋)WCSC29一次予選36位、SDT5予選42位▲(パソコン囲碁)AI竜星戦予選16位

Crieitは個人で開発中です。 興味がある方は是非記事の投稿をお願いします! どんな軽い内容でも嬉しいです。
なぜCrieitを作ろうと思ったか

また、「こんな記事が読みたいけど見つからない!」という方は是非記事投稿リクエストボードへ!

こじんまりと作業ログやメモ、進捗を書き残しておきたい方はボード機能をご利用ください!

ボードとは?

むずでょ@きふわらべ第29回世界コンピューター将棋選手権一次予選36位 の最近の記事