NPCA Contest

どうもきゃたぱです。きゃっとあっぱーです。
NPCA Programming Contest Alphaがありましたね。この記事ではそれの解説をうpしたいとおもいます。
元々は部員のJOI対策のために部内向けに考えていたコンテストなのですが、様々な理由でDiv1とDiv2にわけて校外にも公開して開催しました。
Div1の解説はsnukeさんがブログにあげていますのでそちらをご参照ください。
この記事ではDiv2の解説のスライドを掲載していきます。

Div2はJOI予選4完レベルを意識して作ったためDiv1に対してDiv5くらいの簡単な難易度になっています。
ほとんどやるだけなので、slideshareへのリンクと一言解説を付けるだけにしたいと思います。あしからず。

黒い板


最小値を求めるだけです。

スペルチェック


文字列を比較するだけです。比較にはstd:stringやstrcmpを使えばよいでしょう。

鉛筆狩


百姓を中心に考えれば、ただ最適な役人を選ぶだけになります。

世界史ネットワーキングサービス


ある要素が含まれている区間の個数を数えるだけです。

プール掃除


ソートして2つづつ区切る貪欲法です。

宿題


シミュレートするだけなのですが、残り時間が思い出すのに必要な時間より短い場合は、やらずに、次の休み時間が始まってから始めたほうが速いです。それを把握してシミュレートしないといけません。

約数スマッシュ


数学ゲーかと思いきや、与えられる数が小さいので全探索で十分間に合います。N以上M以下の整数について約数の個数を数えるだけです。

昼ごはん


典型的なナップサック問題です。動的計画法で解けます。この問題がJOI予選4番を意識した問題です。