読者です 読者をやめる 読者になる 読者になる

JOI2011本戦 番外編「ナップサック問題」

JOI

JOI本戦恒例の真のラスボス。 id:qnighyさんに 「最後にナップサック問題をもってくるあたり、さすがJOIだな」 的な事を言われたけど、一瞬何のことか分からなくて、ちょっとして分かったんだけど、そのときにはもうすでに遅かったっていう。 本戦競技で疲れ…

JOI2011本戦 第五問「微生物実験」

JOI

JOI本戦のラスボス。 セグメント木を出してくるとは、さすがJOI。 (qnighyさんはpriority queue+しゃくとり法みたいな感じで解いたそうな) まずはセグメント木で実装し、次にBITでやってみます。 う〜ん、今回はソースコード見て理解して欲しいかも。 考…

JOI2011本戦 第四問「歩くサンタクロース」

JOI

今回から「負け惜しみの解説講座」みたいになるんじゃないかとヒヤヒヤしてたんですが、大丈夫でした(汗 問1 (20点) 内訳 ○○○○○○○○○○ 問2 (20点) 内訳 ○○○○○○○○○○ 問3 (14点) 内訳 ○○○○××○○×○ 問4 (0点) 内訳 ×××××××××××××××××××× 問5 (4点) 内訳 ○○×××××××…

JOI2011本戦 第三問「JOI国の買い物事情」

JOI

本戦では迷走してしまった問題orz 町 or 道路上 にある家から一番近いショッピングモールまでの距離の最大値を求めろ、 って問題。 町 まずは各町からショッピングモールまでの最短距離をそれぞれ求めよう。 ○が町で、中に書いてある数字は町の番号。 数字が…

JOI2011本戦 第二問「古本屋」

JOI

はい、今日もちょびちょび書いていきますよ〜 絶対DPは出るだろうと思ってたら案の定、出たっていう話ですね。 ただ、DPに至るまでにワンステップありましたね。 最初は、naiさんがおまけとして説明してた貪欲法かな〜、と思ったんですが割とすぐダメだと気…

JOI2011本戦 第一問「惑星探索」

JOI

JOIの本戦が終了した。 フィードバックたんは「4問正解だよ〜」って言ってるけど、正直5番はO(n^2)だから甘く見積もっても20点だし、3番はpriority_queue使うべきところで単なるqueue使っちゃったから分からん。 上位陣との差を改めて痛感した。 せっかく…