n-knuu's logs

憧れ駆動。だいたい競プロ

topcoder

SRM696 div.1 300 Gperm

寝坊したので出れなかった。 問題 50個の頂点とM個の枝を持つグラフ(単純グラフとは限らない)が与えられる。初め、各頂点は全て塗りつぶされていないとする。毎回、どこか1つの頂点を塗りつぶした後に、枝の両端の頂点がともに塗りつぶされている枝の数だけ…

SRM552 div.1 250 FoxPaintingBalls

練習会で1完だった 問題 TopCoder Statistics - Problem Statement リンク先の図のように、ボールを並べてN段のtriangleにR,G,Bの3色で、ボールどうしで色が隣り合わないように色を塗る(図はN=3)とする。 R, G, Bで塗れる回数がそれぞれ決まっているときに、…

SRM551 div.1 250 ColorfulChocolates

練習会に出て1完。Medは解けそうでダメだった。 問題 数列が与えられる(長さ50以下)。隣どうしをswapして良い最大の回数が与えられるので、同じ数が連続する長さを最大にしたい。最大の長さを求めよ。 解法 一箇所を固定してシミュレーションすればよい。 具…

SRM543 div.1 250 EllysXors

練習会に参加して、easyを100点くらいで通した。 問題 L, Rが与えられるので、L^(L+1)^...^(R-1)^R を求めよ。 制約 1

SRM540 div.1 250 ImportantSequence

久しぶりに練習会に参加して、1完だった 問題 数列A = [a_1, a_2, ..., a_n]に対して、+と-のどちらかを間に挿入し、数列 B = [a_1 op_1 a_2, a_2 op_2 a_3, ..., a_(n-1) op_(n-1) a_n]とする。 (例) A = [1, 7, 5, 3]で、op = [-, +, +]とするとB = [-6, 1…

SRM687 div.1 250 AlmostFibonacciKnapsack

本番は参加できなかったので、ラボのプロコン*1で解いたけど、0完だった 問題 A[1]=2, A[2]=3, A[i+2]=A[i+1]+A[i]-1 となる数列を考える。このとき、あるxが数列Aの異なる要素の和で構成することができるか? できる場合は、使った要素のインデックスを答え…

SRM528 div.1 500 SPartition

問題 SRM528 div.1 500 SPartition 偶数長の文字列sが与えられる。ここからsの各文字を、前から順番にX,Yのどちらかに振り分けていったとき、XとYが一致するような振り分け方は何通りか? 制約

SRM659 div.1 250 ApplesAndOrangesEasy

問題 SRM659 div.1 250 ApplesAndOrangesEasy 各要素がリンゴかミカンである、要素数がNの列を考える。ここで、[i, i+K-1]の区間で列に含まれるリンゴの数を個以下に制限することとする。列において、要素が必ずリンゴであるインデックスの情報infoが与えら…

SRM663 div.1 300 ABBADiv1

問題 ABBADiv1 A, Bのみからなる文字列initialとtargetが与えられる。このとき、initialに以下の2種類の操作を繰り返し行って、targetに変換できるか? 文字列にAを付け加える 文字列にBを付け加えて、文字列をひっくり返す 制約

SRM643 div.2 500 / div.1 250 TheKingsFactorization

研究室の練習会に途中参加してdiv2 easyしか解けなかった 問題 TopCoder Statistics - Problem Statement N(10^18以下)と、Nを素因数分解したときの、全ての素因数を昇順に並べた列(a_1, a_2, ...)のうちprime = {a_i | iは奇数}となる列が与えられる。元の…

SRM671 div.1 300 BearCries

問題 TopCoder Statistics - Problem Statement

SRM672 div.1 250 Procrastination

問題 TopCoder Statistics - Problem Statement

SRM644 div.2 1000 TreeCutting

問題*1 V頂点の木が与えられる 各頂点vにはnum[v]が与えられる(正の数もしくは-1) いくつかの枝を切断して以下のような木のみが存在する森をつくることはできるか 正のnumをもつ頂点はただ1つのみ その正の数字は木の頂点数と一致する 作れる場合はPOSSIBLE…

SRM670 div.1 450 / div.2 1050 Treestrat

問題 TopCoder Statistics - Problem Statement

SRM509 div.2 1000 NumberLabyrinthDiv2

問題 TopCoder Statistics - Problem Statement 平面が与えられて、各格子には0〜9の数字もしくは空白(.)が与えられる。 数字の書いてある格子からは、4方向に数字の分だけジャンプして移動できる。0に来た場合はそれ以上移動できない。 スタート地点とゴー…

SRM509 div.2 500 LuckyRemainder

div.1 250と同じ問題。 問題 TopCoder Statistics - Problem Statement あるn桁の数字Xに対してsuper(X)を定義する。 super(X)=(Xからm桁(0 例:super(123) = 123 + 12 + 13 + 23 + 1 + 2 + 3 = 177 Xが与えられるので、super(X)を9で割った余りを求めよ。

SRM659 div.2 500 PublicTransit

問題 http://community.topcoder.com/stat?c=problem_statement&pm=13793&rd=16462 R行C列のグリッド上に都市があり、距離をマンハッタン距離で計算するとする。 グリッド上に2つteleporterを設置して、その2つを距離0で移動できるとき、全点対の最大距離を…