topcoder
問題 PikachuEasy やるだけ コード
問題 CasketOfStarEasy 長さ n の数列x[i]が与えられる(インデックスは0, ..., n-1とする)。 以下の手順を数列の長さが2になるまで繰り返す。 0 x[i]は消える この時、x[i-1] * x[i+1]が得点として加算される 最終的な得点が最大になる手順を探せ 方針 再帰…
方針 3つ全部が綺麗なものを全部並べる その左右に2個を繋げた時に価値が最大になるペアを全探索 本番は撃墜された。初被撃墜。 コード
方針 やるだけ ソース
答案 #include <sstream> #include <string> #include <vector> #include <map> #include <algorithm> #include <iostream> #include <utility> #include <set> #include <cctype> #include <queue> #include <stack> #include <cstdio> #include <cstdlib> #include <cmath> #include <iterator> using namespace std; bool …</iterator></cmath></cstdlib></cstdio></stack></queue></cctype></set></utility></iostream></algorithm></map></vector></string></sstream>
方針 ローマ数字の文字列 -> 整数 の変換が肝 'I'は基本的には1, 但し、次が'V'or'X'なら-1. 'X'も同様に基本的には10, 但し、次が'L'なら-10. 雑感 コードを提出した時、「このコードは、30%以上の無関係なコードを含んでいるから、Unused Code Ruleに抵触…
方針 やるだけ 回答
方針 DP。というかメモ化再帰。 f(x)を長さxの時に必要な最小手数とすると、 f(x) = min{min{f(x/p) + 1| p : xの素因数}, min(m-1, x-m+1)} が成り立つ。但し、m = M % x。 この漸化式の気持ちは、 長さNの時の最小手数は、 1回 Divide 操作をやってさらに …
方針 素直に調べる。 雑感 何で Round 1 なの？
問題 http://www.topcoder.com/stat?c=problem_statement&pm=11096&rd=14514 下1桁が 4 or 7 の正の自然数を lucky number と呼ぶ 正の自然数 n を lucky number の和で表したい。この時、なるべく summand の数を少なくしたい。いくつの数が必要か？ 方針 f…
問題 http://www.topcoder.com/stat?c=problem_statement&pm=11432&rd=14514
問題 http://www.topcoder.com/stat?c=problem_statement&pm=11279&rd=14435 (要ログイン) 方針 やるだけ。
問題 http://www.topcoder.com/stat?c=problem_statement&pm=11154&rd=14435 (要ログイン) 初期状態の都市のサイズが population[i] (i = 0, .., N-1) で与えられる。 任意の順番で、都市を2つづつ選び、それらを併合して1つの都市にする。最終的に1つだけが…
問題 http://www.topcoder.com/stat?c=problem_statement&pm=11399&rd=14434 (要ログイン) 全部小文字で書かれた英語の文章があるので、文の先頭を大文字に変えろ。 方針 問題の条件をよく読むと、「文の先頭 = 文章の先頭 or "."の2文字後」、なので、文の…
問題 http://www.topcoder.com/stat?c=problem_statement&pm=11397&rd=14434 (要ログイン) 数列 a[1], a[2], ..., a[n] が以下の2条件を満たす時、その数列は perfect であると言う。 a[1] + ... + a[n] = a[1] * ... * a[n] a[1] >= 0, ..., a[n] >= 0 適当…
問題 http://www.topcoder.com/stat?c=problem_statement&pm=11233&rd=14433 黒と白の玉が一列に並んでいる。 先頭から順番に取り出す。 取り出した玉が 白なら、残った玉の順番をひっくり返す 黒なら、玉の色を反転させる。 方針 基本的には、素直に調べる…
問題 http://www.topcoder.com/stat?c=problem_statement&pm=11350&rd=14433 (要ログイン) 方針 素直に調べる。
問題 http://www.topcoder.com/stat?c=problem_statement&pm=11284&rd=14430 (要ログイン) 何か、変なゲームの得点を最大にしろ。 持ち点0点からスタート 動作 A, B をそれぞれ nA, nB行う。 動作 A をすると、持ち点 += paramA / 1000 動作 B をすると、持…
問題 http://www.topcoder.com/stat?c=problem_statement&pm=11283&rd=14430 (要ログイン) 整数配列が与えられる。 それに一つ付け足して、等差数列 or 等比数列にしたい。 付け加える事のできる数字は何種類か 方針 素直に調べる。
問題と概要 http://www.topcoder.com/stat?c=problem_statement&pm=11341(note : topcoderのサイトにログインしてないと、見れないようです。) いくつかの数字が書かれたカードがあって、そこからカードを任意の順番で引き抜く。あるカードを抜く時、そのカ…
問題 http://www.topcoder.com/stat?c=problem_statement&pm=11331 方針 最大の得点を達成するカードの組み合わせの中には、与えられたカードの中で最大の得点を持つカードと、そのカードの文字列を逆にした文字列を持つカードの中で最大の得点を持つカード…
問題 http://www.topcoder.com/stat?c=problem_statement&pm=11327 方針 同じ色の兎は同じ答えを返す。 ある兎の答えが n の時、その色の兎は丁度 n + 1 匹町の中にいる。 という条件に気を付けて数える。 答案
srm 499 は、参加登録を逃してしまって、参加出来なかった。。。 問題 http://www.topcoder.com/stat?c=problem_statement&pm=10763 方針 全探索 答案
本番では、解き方が分からんかったんだけど、やっと分かったのでメモ。 このパズルでは、以下のように具体的な手順で、任意の状態から任意の状態に遷移出来ることを証明する。http://www.topcoder.com/stat?c=problem_statement&pm=11225&rd=14427にある図で…
端っこから順番に条件を満たすか調べていく。 本番ではシステムテストで落ちた。 seq2の最初の要素が正であるかのチェックを忘れていた。 #include <sstream> #include <string> #include <vector> #include <map> #include <algorithm> #include <iostream> #include <utility> #include <set> #include <cctype> #include <queue> #include <stack> </stack></queue></cctype></set></utility></iostream></algorithm></map></vector></string></sstream>…
topcoder初参戦。 以下の繰り返し。 一番大きい数字を選んでポイントに加算。 選んだ数字を非負の範囲で1減らす。 #include <sstream> #include <string> #include <vector> #include <map> #include <algorithm> #include <iostream> #include <utility> #include <set> #include <cctype> #include <queue> #include <stack> #include <cstdio> #include <cstdlib> #i</cstdlib></cstdio></stack></queue></cctype></set></utility></iostream></algorithm></map></vector></string></sstream>…
幅優先探索で、行ける所全部に最小到達歩数を記録。 到達不可能地点があるかチェック。あるなら、return -1。無い場合、最大の最小到達歩数を返す。 障害物で行けない地点は、走査時に除いて考える。 #include <sstream> #include <string> #include <vector> #include <map> #include <algorithm> #in</algorithm></map></vector></string></sstream>…
結構考えて、時間ぎりぎりで解答が分かった。 列の中で同じ色が続いている部分を「連」と呼ぶことにする。色が4色あるので、連の両サイドがどんな色だったかを気にせずに必ず「(連の長さ) / 2」ステップで連の内部及び連の両端で同じ色が連続しないように出…
基本的には、全ジョブの所要時間合計が少ないユーザのジョブから実行すれば良い。 但し、辞書式順で最小のものを返すために、次のようなソート処理を行った。 各ジョブ番号iに対して [user[i]の全ジョブの所要時間合計, user[i]が最初に出てくるジョブ番号, …
2分探索 コメントで消しているのは、n買い目の支払い後の残高を明示的に書いた公式。これだと、テストケース0で駄目だった。 #include <sstream> #include <string> #include <vector> #include <map> #include <algorithm> #include <iostream> #include <utility> #include <set> #include <cctype> #include <queue> #include <stack> #include <cstdio> #i</cstdio></stack></queue></cctype></set></utility></iostream></algorithm></map></vector></string></sstream>…
