なが月・11日目

11日目

午前

ABC129A-Dを解いた。Cは最も初歩的な動的計画法であり、k段目に至る上り方を通りと表すときの漸化式が成り立つ。ところが階段は一部崩れており、その段への上り方は通りである。ナイーブに実装すればであるが、if k in aの処理が重くTLEする（うっかりしてしまった）。毎段リストを走査してkがあるか探しているからである。二分探索木ならO(logM)ですむが、それをN回繰り返すのだからO(NlogM)となりそれでもある程度の時間がかかる。しかしリストのインデックスを指定して要素を取り出す・代入するのはそれより圧倒的に高速だから、まずリストpを0以外の数(-1にした)で初期化し、に0を代入していく。そしてのときにと代入することにすれば、探索ではなく当該要素の値を0と比較するだけなので間に合う（468ms, 460020KB）。

さらに、は次第に極めて大きな数になっていく（ので1000000007で割った余りを答えとして要求されている）が、ここで剰余の和は和の剰余に等しい

a ≡ x (mod p), b ≡ y (mod p)のとき a+b ≡ x+y (mod p)

ことを利用してと代入すれば大きな数の足し算を繰り返すことがないので時間計算量と空間計算量が劇的に減少する（60ms, 6900KB）。こうした大きな数の扱いについてhttps://qiita.com/drken/items/3b4fdf0a78e7a138cd9aを参考にしていきたい。

D問題は純粋な(標準モジュールの範囲での)Python3ではおそらく解けない。numpyによる行単位・列単位の一括加算を行ったり、numbaでJITコンパイルをしたりする必要があった。アルゴリズム自体は愚直な行・列方向のランレングスまたはカウントアップでよかったのだが、forではどうやっても間に合わないということが判明するまで長いこと実装の誤りや無駄を検討して時間を無駄にしてしまった。

しかしC++は圧倒的に速い。for二重ループで素直に回してもなおnumpyより何倍も速い。C++で競プロのコードを書くことで来学期の講義に向けた練習になるのではないかと思ったので、これから練習のためにC++で書こうと思う。

午後

C++初回。std::cout << "Hello World!\n";において<<はシフト演算子だが、出力ストリームと文字列やint/float/doubleなどが引数である場合には右の引数を文字列に変換して左の出力ストリームに流し、左の出力ストリームを返すのだという。“仮引数の型情報と実引数の型情報が一致する関数定義だけが、自動的に呼び出される”とのことだ。これをArgument Dependent Lookup(ADL)と呼ぶらしい。出力書式を指定する必要のあるprintfに比べれば随分柔軟になったように思う。

以下はusing namespace std;を前提として書くが、cout << "Hello World!" << endl;はHello World!を出力した段階でcout << endl;となり、ここでendlという関数ポインタが右の引数に来る。関数ポインタが右に来る場合は左の出力ストリームの内容を右の関数に渡し、左の出力ストリームを返す。その結果std::endlはcoutに\nを書き込んでflushする（バッファリングをやめてその段階でコンソールに出力する）という仕組みだ。

using namespace std;というのもひとまとまりではない。

using 名前空間::識別子;はPythonのfrom math import sqrtのようなもので、math.sqrt()ではなくsqrt()で直接呼べるようになる。その代償として同じ識別子のものがあると関数名が衝突する。

namespace 名前空間;は名前空間の定義であり、同名の名前空間はファイル間にまたがって一連のものとして扱われる。

namespace altName = std;とするとこれはちょうどimport numpy as npである。altName::coutはstd::coutになる。

そしてusing namespace 名前空間;はfrom math import *である。こうなると自分の与り知らぬ標準関数と名前が衝突し、エラーが起きてしまうことになる。

また#includeするヘッダとして、stdio.hのようなC言語標準ライブラリと、それをC++スタイル(std::で呼ぶ)で使えるようにするcstdio、iostreamのようにC++専用の(std::で呼ぶ)ものの3種類があると分かった。