東京海上日動プログラミングコンテスト2020 参加記

東京海上日動プログラミングコンテスト2020に参加しました。

atcoder.jp

 

振り返れば、前回の企業主催コンテスト(NOMURAプログラミングコンテスト)では、3完達成。残り1分ギリギリでC問題ACという 、個人的にはアツい内容でしたw

devgenjin77.hatenablog.com

 

で、今回は、3完以上が目標かな、という心持ちで挑んでみることにしました。

 

今回の結果

で、終わってみれば今回は2完で終了。。

TokyoMarine2020結果

TokyoMarine2020結果

振り返り

TLEに泣く展開となりました。

TokyoMarine2020提出結果

TokyoMarine2020提出結果

A問題

A - Nickname

入力文字列の先頭3文字を返す問題。Javaなのでsubstringを使って速攻AC。

B問題

B - Tag

2点A、Bそれぞれの座標と速度、そして時間が入力される。AがBを鬼ごっこの要領で追いかける場合、時間内に捕まえることができるかという問題でした。

条件分岐で凡ミスをやらかしてしまい、2回WAを喰らうも、なんとかAC。

C問題

C - Lamps

目標の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)の勉強を少しづつでも進めるようにしようと思います。