東京海上日動プログラミングコンテスト2020に参加しました。
振り返れば、前回の企業主催コンテスト(NOMURAプログラミングコンテスト)では、3完達成。残り1分ギリギリでC問題ACという 、個人的にはアツい内容でしたw
で、今回は、3完以上が目標かな、という心持ちで挑んでみることにしました。
参加します。今回は3完以上が目標かな。
— devgenjin77 (@devgenjin77) 2020年6月13日
東京海上日動 プログラミングコンテスト2020 - AtCoder https://t.co/XIOgw1Aw0l
今回の結果
で、終わってみれば今回は2完で終了。。
振り返り
TLEに泣く展開となりました。
A問題
入力文字列の先頭3文字を返す問題。Javaなのでsubstringを使って速攻AC。
B問題
2点A、Bそれぞれの座標と速度、そして時間が入力される。AがBを鬼ごっこの要領で追いかける場合、時間内に捕まえることができるかという問題でした。
条件分岐で凡ミスをやらかしてしまい、2回WAを喰らうも、なんとかAC。
C問題
目標の3完を目指して挑むC問題。
問題文を読んで、なんとか意味は理解したが上手い実装方法が思いつかない。
数十分悩んだ挙句、各電球の各操作について毎回再計算する原始的な方法で実装し、サンプルケースまで通してみたが、提出したらあえなくTLE。
結局、改善策も思いつかず、一度諦めることにしました。
解説を読んでみれば、累積和のテクニックが必要だったとのこと。
全然知らないテクニックだったので、この機会に覚えることにします。
D問題
D - Knapsack Queries on a tree
いったんC問題を諦めて挑むD問題。
ナップサック問題と二分木の合わせ技みたいな問題です。
ナップサックと言えばDPということで、DPの実装とアイテムを二分木から取得するとこだけとりあえず実装。これがサンプルケースはあっけなく通ってくれました。
まあ、C問題のこともあるんでTLEにならないといいなー、という淡い期待を込めて提出してみましたが、ま、これもあっけなくTLEを食らいました。。
改善方法も思いつかず。時間も来たので、今回はここでギブアップです。
E、F問題
コンテスト中は目を通せず。後日ちゃんと復習しよう。
今回の実績
2完だったけどなんとかレート上昇。灰色卒業まであともう少しとなりました。
総括
今回は、C、D問題でTLEを喰らってしまい、無念の2完終了でした。
アルゴリズムの知識が足りないようなので、蟻本(結構前に買ったけど、あまり読んでないw)の勉強を少しづつでも進めるようにしようと思います。