htkb-proconの日記

初心者がPythonで問題解いた記録

AtCoder Grand Contest 030

o--- 1600 -> 1607

A - Poisonous Cookies

AC: Submission #3892026 - AtCoder Grand Contest 030

やるだけなんだけど解毒クッキーより毒クッキーが多い場合毒クッキーを食べる数は解毒+1になるとか、タイムアタックやってると足引っ掛けそうでおっかない問題。WAせずに早解きできたことで一命をとりとめた。

B - Tree Burning

最初から部分点狙いで行ったが、結局かなりの時間考えがまとまらなかった。最初はグラフ問題かとか距離を負にしてダイクストラでもすんのかとかスットコドッコイなことばっかりずっと考えていて、DPに行き着いてもどう状態を管理するのかピンと来なかった。dp[左端][右端]ってやるにしても現在左端にいる状態と右端にいる状態って別だしなあ……などと時間を潰してタイムアップ。

結局部分点解法はdp[l][r][2]として今左にいるか右にいるかを別に取れば良いのだった。ただpythonだとリストの使い回しや変数にキャッシュして不必要にリストにアクセスしないなど定数倍改善をかなり頑張らないと辛かった(本番ならpypyで通すけど)。

部分点: Submission #3897596 - AtCoder Grand Contest 030

満点は最初にx個の木を直進しながら燃やしてその後はジグザグ、という動きをすべてのxについて試す。最初からジグザグに進むのが最適なら思いつけたかもしれないけど、この考えはサンプル1で否定されていたので早々に捨てていたし、最初にいくらか直進するって発想は思いつけそうにない。

AC: Submission #3900730 - AtCoder Grand Contest 030


青から落ちず今年を終われたのは良かったけど、最後の最後で周りがみんな通してる典型DPを取れなかったのは本当に反省。もともとDPに苦手意識はあったし解けるDP問題も今までこんな感じにDP組んだのでこんな風に遷移させるんだろう(適当)という感じのところが多々あったので、単に問題を多く解くだけでなく状態遷移をしっかり意識してDP書くのをとりあえずの目標にしたい。