コンテストで出来なかった問題を復習してみました。

もっとも参考にした解説

この問題は、はまやんさんの解説が一番わかりやすいと感じたので、これをメインの参考に。

実装方針としては、動的計画法で解く問題とのこと。
はまやんさんのC++のコードをPythonにコンバートして、実際の動きをデバッガで見ていく形で理解していくことに。

書いたPythonコード

いやはや、勉強になった。
Pythonのlistを二分探索する命令、bisect.bisect_leftって初めて使った。
こういうのあるのね。

このコードに書かれているdpを理解する上で、よくわからないと感じたのは
・高橋くんの行動回数+1した時、なんで青木くんの行動回数(dp内の値)を引き継いでよいのか？
ということ。

青木くんの行動回数がわかっている状態で、高橋くんの行動回数を1足したとき、草を何本かれるのか？
と考えるのが、わかりやすいのかも。

AtCoderにて実行した結果は、
PyPy3(7.3.0) AC
Python3.8.2 TLE