問題 N (< 50) 種類のお好み焼きがある. i 番目の大きさは配列 osize[i] (< 10000) で与えられる. このうち M (< N) 種類を選ぶときに, 最も小さいものと最も大きいものの差が K 以下となるような選び方は何通りあるか, 1,000,000,007 の剰余で求めよ. 方針 …

コーナーケースに気をつけて慎重に戦略を考える問題（もしくは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 番目のバスが発車してから戻ってくるまで…

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

本番では解けなかったけど, 綺麗な 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 の系列で…