そんなものこの世にない 250 整数を2で割って（小数点以下切り捨て）、素数じゃなくなるまで続ける。素数がK個以上できるような整数で、N以下で最大のものを求めよ。Nは1000万以下。 問題文の理解に時間を食う。エラトステネス＋DP。Nが大きいのでやたらとメ…

APIO（アジア太平洋情報オリンピック）を受けてきました。 問題概要は公式サイトにあるので省略。難易度的には、「ぱない」としか形容のしようがありません。 1. Commando 50点まではO(n^2)のDPで取れる（取れた）。そこから先がわからない。 2. Patrol 非常…

死にました。 250 すごく広い映画館に、２人が隣りあって座る。いくつかの椅子は埋まってる。座る位置は何通りあるか答えよ。喩えて言うなら、教室に入ろうとしたら黒板消し(long long)が挟まってて、それは避けたけど油断してたら地面に張ってあった黒板消…

「やるだけ」な問題ばっかり。 2559 Largest Rectangle in a Histogram 前回O(n log n)のコードを書いていたので解き直し。 左から見ていって、高さが常に広義単調増加になるようにスタックに積んでいく。 もし、前の高さより低くなったら、広義単調増加にな…