エンジニアの競馬情報収集ブログ

最近は5割が競馬の話、3割がLoL/LJLの話、2割が技術的な話な感じ。たまにその他の話。

AtCoder Regular Contest #042 参加記

結果

  • 75位
    • 250 (3) 103:11
  • Rating: 2級 -> 2級
    • 級のRatingってどう付けられてるのかわからないけど、内部的には上がってるのかしら…
    • というかこの級ってシステム必要なのかしら…

f:id:yoshiki_utakata:20150726131906p:plain

A - 掲示板

双方向リストと、スレッドにO(1)でアクセスできるポインタを持つことで O(m) で解答。 Javaで何も考えず入出力を適当に書いたら1977msecとかになって冷や汗でた。

出力部分を最適化したら1100msecくらいだった。

書き込みログを後ろから見ていくことで、リストとか実装しなくて済むということには気づかなかった。

B - アリの高橋くん

点と各辺の距離をもとめて最も小さいものを答えとして出力するだけ。

C - おやつ

合計金額 - 最も安いおやつの値段 <= P となればいいので、それを元に雑なDPをして、終了1分前くらいに部分点を獲得。

これは、最も安いおやつの値段を固定すると普通のDPになるので、それでうまい具合にDPするとO(NP)で解けるらしい。けっこうギリギリだなぁ。

おまけ

解説生放送がめっちゃトラブってて面白かったですw 突然謎のノイズが流れだしたり、声がめっちゃハウったり。 一人で腹抱えて笑ってました。 特にこのアンケートは草

f:id:yoshiki_utakata:20150726134907p:plain

f:id:yoshiki_utakata:20150726134912p:plain