0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

AtCoder ABC155 問題D Pairs 検討メモ1

Last updated at Posted at 2020-03-22

#概要

AtCoder ABC155 問題D Pairsに関してメモ。

#経緯

2020/02/16に開催されたAtCoder ABC155は仕事が忙しくて参加できなかったのだが、精進の為問題Dを見てみてみたところ解法思いつかず。解説記事をみて、二分法で数えて行けばよいのかと理解。自分なりにPythonでコーディングしてみたが茶色の自力ではTLEから抜け出せなった。

以前の比較からC++でやれば多分行けるんだろうなとは推測したが、

  • Pythonで通すことはできないか、
  • 通せるすると自分のコードのどこが甘いのか

などが気になったので調べてみた。

調査検討結果

Pythonで通すことはできないか?

結論:通せる(けどちょっと難しい?)

Python3でACとっている方を検索したところこんな結果に。
ABC155D-python-AC-01m.png
コンテスト時間内に通している片は僅か2名でmaspyさんは黄色、nohtarayさんは青でも黄色よりの方でした(色は2020年3月20日現在)。実行時間は1100msec程度。

時間内に2人しか通せてないこと、通しているお二人が黄色、青色の方であることを考えると私の実力で通すのは厳しかった問題と思われる。

あと以前の比較では著しい改善がみられた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しないコードが書けたのかとは気が向いたら調べて整理しようと思う。

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?