問題 http://codeforces.com/contest/500/problem/C 本が N (< 500) 冊ある. それぞれの本には重さがある. 本は全て重ねて積んだ状態である. 上から I 番目の本を読む場合には, I 番目の本を取り出して山の一番上に移動させる. この時, あなたには 1~I-1 番…

方針を考えるのが楽しい問題だった. 問題 http://codeforces.com/contest/500/problem/D ノード数 N (< 100000) の木が与えられる. 各辺は長さを持つ. 1 年に一回, ある辺の長さが更新される. 3 頂点 a, b, c を一様ランダムに選んだ時の, D = distance(a, b…

特に引っ掛けは無いので, 方針だけ思いつけば簡単な問題. 問題 http://community.topcoder.com/stat?c=problem_statement&pm=13551&rd=16083 N (<50) 個の星と M (<200) 個のリボンがある. 星はそれぞれ色があり, i 番目の星の色は col[i] で与えられる. リ…

コーナーケースに気をつけて慎重に戦略を考える問題（もしくはDP解法）. 本番では題意を微妙に取り違えていて, なぜか pretest 通ってしまい, 呆気無く撃墜された. 問題 http://community.topcoder.com/stat?c=problem_statement&pm=13526&rd=16086 2N 人の…

本番は素数リスト作ったけどその必要も無かった. 問題 http://community.topcoder.com/stat?c=problem_statement&pm=13594&rd=16086 1018 以下の整数 N が与えられる. N を素因数分解せよ. ただしヒントとして, 昇順 0, 2, 4, 6, ... 番目の素因数が与えられ…

問題 http://community.topcoder.com/stat?c=problem_statement&pm=13309&rd=16084 2 次元平面上の点が N (< 2500) 個与えられる. これらの点が構成する三角形のうち, 内側に原点を含むものの個数を求めよ. 方針 偏角でソートし, 全ての点 i, j (i < j) につ…

Med は難しい... 問題 http://community.topcoder.com/stat?c=problem_statement&pm=13319&rd=16085 木が N 本ある. n 番目の木は高さ height[n] であり, 1 日に add[n] だけ伸びる. また, カッターが M 個ある. m 番目のカッターをある木に対して使うと, 木…

DP の練習に良い問題だとおもった 問題 http://community.topcoder.com/stat?c=problem_statement&pm=13540&rd=16085 同じ停留所に発着するバスが N (< 100) 台あり, 0 から N-1 までの番号が割り当てられている. i 番目のバスが発車してから戻ってくるまで…

この記事は Competitive Programming Advent Calendar Div2014 12 日目です。 競技プログラミングを始めて 1 年がたちました。この一年をざっと振り返ってみたいと思います。 【1 月】PrintScreen / Aizu Online Judge 新卒 SIer 1 年目だった僕は、一日 8 …