脳log[20200615]

2020年06月15日 (月) [AtCoder] 「【競技プログラミング】青コーダーが灰～茶コーダを緑diffの問題をACに導く Part1【考察過程】 - YouTube」■すごく、すっごくもどかしい。でも自分がもどかしい側に立っていることを知っている。実際、教えている青色の人が一瞬で問題を掴んで解法の見当をつけたところでは問題の理解が完了していなかった。教わっている人がサンプルの答えとなる数列を列挙している時間と図を使って、見ているこちらでも具体的な解法がわかった。実のところ題意を満たす満たさないを問わない部分列の全列挙がそう簡単なタスクではない。開始位置と終了位置の組み合わせで特徴付けられると気がつくまで、本当に網羅できているか不安があった。問題の輪郭と扱っている対象がはっきりしてくるまでに、手の運動と、目への刺激と、時間が必要なのだ。■「累積和」という単語で２つめの解法を新たに知った！ 最初に N 要素を順に足してメモして、それは増加列だから二分探索で題意を満たす最小の範囲が確定できる。題意を満たしているかは引き算で。■■■高校３年生ですって。人生２周目でも追いつけないよ！「超高速！多倍長整数の計算手法【前編：大きな数の四則計算を圧倒的な速度で！】 - Qiita」■■■@2020-06-19 今日は蟻本で BIT(Binary Indexed Tree) という構造について読んだ。とりあえず累積和を記録するのに使えることがわかったけど、普通に配列にそれまでの総和を記録していくのと比較した強みがなんなのかがはっきりしなかった。たぶん更新がないなら普通に総和を記録していくのでいいと思う。定数時間で値の取得ができるし(BIT なら対数時間)。BIT を使いたいのは値の更新があるときだろう。普通に配列にある要素までの総和を記録していた場合は、値を更新するのにある要素より後ろのすべての要素が関わってきて線形の時間がかかる。BIT なら値の更新も対数時間で済む。