問題 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 …

問題 http://community.topcoder.com/stat?c=problem_statement&pm=13490&rd=16082 Alice, Kirito 2人がゲームをする. ゲームはターン1から始まり有限ターンからなる. 各ターンでそれぞれ勝者が決まり, i ターン目で勝利すると2*i-1ポイントもらえる. long l…

最近、Project Euler の問題をぽちぽち解いていってます。どうせやるなら慣れていない言語でやろう！ということで Python とか Haskell を触ってるのですが、イミュータブルなデータ構造が基本の Haskell でアレコレやるのは本当に難しい。 例えば Problem 1…

本番では解けなかったけど, 綺麗な DP 問題だった. 問題 http://community.topcoder.com/stat?c=problem_statement&pm=13295 廊下に N (<= 50) 匹の狼が配置されている. 各狼のサイズは vector<int> size で与えられている. 二匹の狼がすれ違えるのは, サイズの合</int>…

問題 http://community.topcoder.com/stat?c=problem_statement&pm=13355&rd=16081 N*N*N (N <= 10) の空間に 1*1*1 のキューブをいくつか配置する. XY・YZ・ZX平面の投影図がそれぞれ与えられる. 配置したキューブは全て隣接し得るかどうか答えよ. 方針 座…

問題 http://community.topcoder.com/stat?c=problem_statement&pm=13234&rd=16076 int x, vector<int> jumpLengths が与えられる. 二次元平面上の原点 (0, 0) からスタートして, 点 (x, 0) に到達したい. 平面上を jumpLengths で与えられた距離だけ順に移動する</int>…

問題 a[0], ..., a[N-1] の N 個の非負整数がある. ただし, a は与えられない. 代わりに, 2進数表現での trailing zero の数 d[0], ..., d[N-1] が与えられる. a[0], ..., a[N-1] について, 1 ずつ増加する部分列の個数の最大値を求めよ. 1 <= N <= 50 0 <= …

問題 http://community.topcoder.com/stat?c=problem_statement&pm=13377&rd=16061 ある文字列に対する接尾辞配列 SA が与えられている. 元の文字列は何種類のアルファベットで構成されているか. 最も少ない場合の種類数を求めよ. 接尾辞配列 - Wikipedia 文…

問題 http://community.topcoder.com/stat?c=problem_statement&pm=13284&rd=16061 頂点数 n, 辺数 n-1 の木が与えられる. 各辺には距離が設定されている. k 個の頂点を選び, 頂点間の距離が全て等しくなるようにしたい. k の最大値を求めよ. 頂点数は 1 以…

問題 http://community.topcoder.com/stat?c=problem_statement&pm=13241&rd=16009 は x の 1 以上 x 以下の約数の個数を表す. とする. 与えられた整数 について, を満たす最小の x を求めよ. 存在しない場合は -1 を返す. 解法 より, の値は最大でも60であ…

問題 http://community.topcoder.com/stat?c=problem_statement&pm=13274 [a-z] のみからなる文字列 L (1 <= |L| <= 50) が与えられる. 一度の操作で, 文字列中の任意の異なる文字ペアを消去する (例えば "aabbc" -> "aab"). この操作を繰り返して, 最後に残…

問題 http://community.topcoder.com/stat?c=problem_statement&pm=13275 N 頂点, N 辺 (3 <= N <= 1000) の連結な無向グラフが与えられる. 各頂点は属性として値 v_i (1 <= v_i <= 1000) を持つ. 長さ K 以上の全ての単純路について, それぞれ v_i の系列で…

概要 整数列 に対して, 以下のクエリを O(log(n)) で実現するデータ構造. : を求める : に を加える 特徴 Segment Tree の機能縮小版で, 実装がむちゃくちゃ簡単. 構造 深さ log(n) の二分木であり, 各ノードは以下の法則で値を保持する. 葉: 葉の親: 葉の親…

問題 http://www.codechef.com/LTIME13/problems/COPRIME3 整数 N (0 < N < 105) と, N 個の整数 a_0, a_1, ..., a_[n-1] (0 < a_i < 106) が与えられる. 0 < i < j < k <= N として, a_i, a_j, a_k が互いに素となるような (i, j, k) の個数を出力せよ. (制…