ニコ生オープン 第3回

結果

Hardが運良く(1.994sかかるケースがあった)通って3完。

以下時系列順。

Easy

• 問題読む。
• わからん。
• 一筆書きできると嬉しいね。
• あれ、全部の頂点の次数明らかに偶数じゃん。
• ということは連結ならOK。
• DFS書くだけ。Submit。

Medium

• 問題読む。
• わからん。
• えーと繰り上がりが……。
• めんどくさい。
• totally oddな数ってどれぐらいあるの。
• 5+5^2+5^3+...+5^8 <= 500,000
• 凄く少なかった。
• じゃあtotally oddな数を全部生成して、片方を固定して二分探索でいいよね。
• 書く。実装軽い。Submit。

Hard

• 問題読む。
• まず座標圧縮。
• あとはDPで終わりじゃないのか。
• あれ、そうすると状態 80^4 と時間 80^5 で死ぬのでは……。
• いやでも実際の状態数はそこまで多くなかったりするんじゃないか。
• とりあえずメモ化再帰書く。とうぜん間に合わない。
• 仕方ないのでループのDPに直す。間に合わない。
• おいどうすんだ。
• 添字の順番を変えるなどちまちま高速化。
• 最大ケース1.8sec……。通るかな……。
• 別のケースも1.8secぐらい……、出してしまおう。Submit。
• 残り5分ぐらい。とりあえずテストしまくる。
• あれ、答おかしい……。死ぬ……。
• えーDP間違ってないよねー。
• 添字の間違いとかないよねー。
• あ、座標圧縮のコード間違えてた……。
• 急いで直してResubmit。残り1分ぐらい。