概要
AtCoder ABC155 問題D Pairsに関してメモ。
経緯
2020/02/16に開催されたAtCoder ABC155は仕事が忙しくて参加できなかったのだが、精進の為問題Dを見てみてみたところ解法思いつかず。解説記事をみて、二分法で数えて行けばよいのかと理解。自分なりにPythonでコーディングしてみたが茶色の自力ではTLEから抜け出せなった。
以前の比較からC++でやれば多分行けるんだろうなとは推測したが、
- Pythonで通すことはできないか、
- 通せるすると自分のコードのどこが甘いのか
などが気になったので調べてみた。
調査検討結果
Pythonで通すことはできないか？
結論：通せる（けどちょっと難しい？）
Python3でACとっている方を検索したところこんな結果に。
コンテスト時間内に通している片は僅か2名でmaspyさんは黄色、nohtarayさんは青でも黄色よりの方でした（色は2020年3月20日現在）。実行時間は1100msec程度。
時間内に２人しか通せてないこと、通しているお二人が黄色、青色の方であることを考えると私の実力で通すのは厳しかった問題と思われる。
あと以前の比較では著しい改善がみられたPyPyでも試してみた（提出#10928876）が今回はあまり効果がなくTLEは解消できなかった。
通せるすると自分のコードのどこが甘いのか?
実行速度比較
まず実行時間を比較してみた。
maspyさんの提出#10152895
nohtarayさんの提出#10155744
を自分のサーバにダウンロードしてきて、自分で書いた
プログラム提出#11068460
と併せて、それぞれのプログラムをテストケース4つに対して実行させたときの実行時間を比較した。
以下結果（経過時間をtimeコマンド計測。単位は秒）。実行結果自体は一致しているのでプログラム自体は正しく動いている様子。
| プログラム | test01 | test02 | test03 | test04 |
|---|---|---|---|---|
| 自分のプログラム[提出#11068460] | 0.045 | 0.039 | 9.576 | 9.576 |
| nohtarayさんの[提出#10155744] | 0.303 | 0.288 | 1.140 | 1.119 |
| maspyさんの[提出#10152895] | 0.275 | 0.312 | 1.097 | 1.045 |
テストケースはのサイズ以下の通り。Aiは乱数で発生させた。
| プログラム | test01 | test02 | test03 | test04 |
|---|---|---|---|---|
| N | 20 | 20 | 200000 | 200000 |
| 正の数の数 | 10 | 10 | 100000 | 10000 |
| 零の数 | 1 | 1 | 1 | 1 |
| 負の数の数 | 9 | 9 | 99999 | 99999 |
| K | 150 | 50 | 1500000000 | 500000000 |
結果からわかるのはNが小さいときは私のプログラムのほうが速いがNが大きくなってくると
maspyさん、nohtarayさんのプログラムの方が10倍程度早い。。。
コード比較
ではなにが違うのか。。。を探るためにmaspyさん、nohtarayさんのプログラムをのぞいていみる。
お二人のコードに共通してnumpyのsearchsorted という機能を使用されていることが判明。第二引数にも配列使っている。これが多分私の手ぐみの関数などよりずっと速いのだと予想された。こんな関数があるのか。。。。これ使っているおかげもありコードも短い。
最後に
numpyのsearchsortedの利用が「味噌」と分かったところまででメモ1はおしまいにする。
Pythonで競プロするにはnumpyとかいろいろ知識が足りないのだなという事は分かった。numpy searchsortedについてとか、C++ならもっと簡単にTLEしないコードが書けたのかとは気が向いたら調べて整理しようと思う。