TopCoder SRM

SRM580 Div1 Easy - EelAndRabbit

appletは相変わらず滅多に繋がらない上に最近たまにstatisticsの問題ページが消える 問題 川をn匹のうなぎが泳いでおり、i匹目の長さはa[i]で、時刻t[i]にうなぎの頭がx軸にぶつかる ある時刻に川に飛び込むと、その瞬間にx軸と交点を持つうなぎを全て捕まえ…

SRM579 Div1 Easy - UndoHistory

問題 長いから略 与えられるvectorの名前はsとする 解法 s[i]をタイプするとき L = max(s[i]とs[j とすると、2回のマウスクリックでL文字復元して、残りの |s[i]|-L 文字は手打ちする必要がある ただs[i]の先頭がs[j]に一致する場合のみ、前のバッファをその…

SRM578 Div1 Easy - GooseInZooDivOne

問題 h*wのグリッド上のいくつかのマスにガチョウとアヒルがいるが、見た目で区別はつかない ガチョウは以下の条件を満たす 1) ガチョウは2以上の偶数匹いる 2) あるガチョウからマンハッタン距離がd以内にいるような鳥は必ずガチョウである 鳥の部分集合の…

SRM576 Div1 Easy - ArcadeManao

問題 h*wのグリッドがあり、(sx,sy)からx座標がh-1の任意のマスに行きたい 床があるマスとないマスがあり、床があるマスにしか移動することはできない あるマス(x,y)からは、(x,y±1) には無条件で行ける (床さえあれば) 長さLのはしごを持っている場合は (x±…

SRM575 Div1 Easy - TheNumberGameDivOne

わかりませんでした ゲーム系のeasyにしてはむずくない? 問題 自然数nがある 2人が交互にnから「1とn以外のnの約数」を引き、操作を行えなくなった方が負ける どちらが勝つか判定せよ1 解法 nが奇数 or 2の奇数乗なら後手、それ以外は先手が勝つ このゲーム…

SRM574 Div1 Easy - TheNumberGame

問題 先手が数字a、後手がbを持っており、どちらも0の桁はない 各ターンで各プレイヤーは自分の数字を反転するか最後の桁を消すかを選ぶ 途中で両者の数字が一致したら先手の勝ちで、いつまでも一致しない場合は後手の勝ちになる 両者が最善を尽くすときどち…

SRM573 Div1 Easy - TeamContest

問題 大学に人が3n人いて、i人目の強さはa[i]である これらの3n人から3人チームをn組作る 3人チームの強さは3人の強さの最大値と最小値の和で決まる 0〜2人目が一緒にチームを組むことはもう決まっている 他の3n-3人のチーム分けを工夫すると、このチームよ…

SRM572 Div1 Easy - NewArenaPassword

問題 topcoderのパスワードをsにしていた ある日「パスワードの最初のk文字と最後のk文字は一致していないといけない」という新ルールが出来た 新ルールを守るようなパスワードに変更するとき、sから変更する文字数の最小値を求めよ1 1 解法 sの長さをnとす…

SRM571 Div1 Easy - FoxAndMp3

問題 mp3プレイヤーにn曲の曲が入っており、i曲目の名前は "i.mp3" である このプレイヤーは曲名を数字の昇順ではなく文字列の昇順にソートする このプレイヤーの表示順に、 1) n 2) そうでないときは最初の50曲の曲名 を書け1 解法 2桁以下は全部試す 3桁以…

SRM570 Div1 Easy - RobotHerb

問題 無限に広いグリッド上にロボットがいる 長さnのプログラムが組み込まれており、i番目は「正面にa[i]マス進んでからa[i]*90度右に回れ」という内容 このプログラムをt回実行した後に辿り着くマスと最初にいたマスのマンハッタン距離を求めよ1 1 1 解法 …

SRM569 Div1 Easy - TheDevice

ちょっと面白かった 問題 長さmのビット列がn個ある これらのうち2個を選んで機械に入れると、各ビットごとにそれらのor / and / xor和のどれかを計算して出してくれる この機械の各ビットがor / and / xor和のどれを出しているのか特定したい 今あるn個のビ…

SRM568 Div1 Easy - BallsSeparating

問題 n個の箱があり、i番目の箱には赤緑青のボールがそれぞれr,g,b[i]個入っている ある箱からある色のボールを取り出し違う箱に入れるにはコストが1かかる それぞれの箱に入っているボールの色の種類を1以下にするためにかかるコストの最小値を求めよ1 1 解…

SRM567 Div1 Easy - TheSquareRootDilemma

問題 整数n,mが与えられる a,bがn,m以下かつ (√a + √b)^2が整数になるような正整数のペア(a,b)の個数を求めよ1 解法 (√a + √b)^2 = a+b + 2√ab だからabが平方数ならokaを全部試す aを平方数で割れるだけ割った結果をa'とする するとこのaとペアにできるbの…

SRM566 Div1 Easy - PenguinSledding

問題 n頂点m辺の無向グラフが与えられる グラフがどんな形になっていても絶対に辺同士が交差しないように辺を削除するとき、最終的なグラフとしてあり得るものは何通りあるか2 1 解法 最終的なグラフは 1) 辺が1本もない 2) 辺が1本だけある 3) 辺が2本以上…

SRM565 Div1 Easy - MonstersValley

問題 マナオは一人で旅に出た 道中で出会うモンスターはn匹いて、i番目に出会うモンスターの怖さはd[i]で、仲間にするにはp[i]円かかる モンスターに出会ったとき、金を払って仲間にするという選択肢が常にある またはマナオのチームの怖さの合計がそのモン…

SRM564 Div1 Easy - KnightCircuit2

チェスサークルの力を発揮 問題 h*wのチェス盤がある 好きなマスにナイトを置いて好きなだけ動かすとき、ナイトが通れるマスの最大値を求めよ1 解法 h h=1: 一度も動けないから答えはスタート地点の1マスのみ h=2: ジグザグに動けばceil(w/2)マス通れる h=3…

SRM563 Div1 Easy - FoxAndHandle

問題 長さn(:偶数)の文字列sが与えられる sを2つの文字列x,yに分け、yがxのアナグラムになっているようにしたい xとしてあり得る文字列のうち辞書順最小のものを求めよ2 xとしてあり得る文字列が少なくとも1つは存在することが保証される 解法 1文字ずつ決め…

SRM562 Div1 Easy - PastingPaintingDivOne

問題 エディタで絵を書く 最初キャンバスは全てのマスが透明で、クリップボードにはh*wの長方形の絵sが入っている 絵の各マスの色は赤か緑か青か透明で、キャンバス上のある位置にこれを貼り付けると、絵の色付きのマスが乗るマスはその色で上書きされ、透明…

SRM561 Div1 Easy - ICPCBalloons

問題文が長い! 問題 ICPCの問題正解者に渡すための風船があり、色はn通りある 色iのものはc[i]個あり、それら全てのサイズはs[i]である ('M'edium or 'L'arge) 問題はm問あり、j番目の問題は最大でa[i]チームにしか解かれることはない それぞれの風船は金を…

SRM560 Div1 Easy - TomekPhone

問題 略 解法 keySizesの各要素s[i]について、ある文字を1〜s[i]回のストロークで入力できるように割り当てることができる 多い文字ほど少ないストロークで入力できるようにするのが明らかに最善だから、ソートして貪欲に割り当てればok class TomekPhone { …

SRM559 Div1 Easy - HyperKnight

問題 サイズh*wのボードがある 今いるマスから(±a, ±b) or (±b, ±a)に移動できるハイパーナイトというコマがある このコマのあるマスからの1手での移動先は最大8通りあり得るが、ボードからはみ出すような動きはできない このコマが1手でk通りのマスに移動で…

SRM558 Div1 Easy - Stamp

問題 長さnの無色のセルの列があり、左からi番目のセルはs[i]色で塗りたい 何色で塗ってもいいセルもある このために、まず好きなサイズのスタンプを1つ選ぶ サイズLのスタンプを使うにはst*Lだけコストがかかる またスタンプを押す度にpsだけコストがかかる…

SRM556 Div1 Easy - XorTravelingSalesman

問題 n個の町があり、i番目の町の価値はa[i]である 最初は町0にいてスコアはa[0] スコアがpの状態で町iに移動するとスコアはp xor a[i]に変化する 好きな町で終了できるときスコアの最大値を求めよ1 0 解法 d[i][j]: 町iにスコアjでたどり着けるかどうか と…

SRM603 Div1 Medium - PairsOfStrings

包除原理 問題 以下の条件を満たす文字列のペア(a,b)の個数を求めよ 1) aとbの長さはどっちもn 2) aもbもアルファベットの最初のk文字のみからなる 3) a+c = c+bとなるような文字列cが存在する1 1 解法 3つ目の条件は、 (aの先頭x文字) = (bの末尾x文字) か…

SRM613 Div1 Medium - RandomGCD

http://compro.tsutajiro.com/archive/181015_incexc.pdf (包除原理 解ける数え上げの範囲を広げよう - tsutaj) 今の俺が求めていたものはこれだった 包除原理を極め鯛 問題 L以上r以下の整数を重複を許してn個選んで数列を作る 全要素のgcdがkになるような…

SRM555 Div1 Easy - CuttingBitString

問題 長さnで '0' と '1' のみからなる文字列sが与えられる これを2進数として見るとき、全ての部分列がleading-zeroなしで5の冪乗になるようにいくつかの部分列に分けたい 最小でいくつの部分列に分ける必要があるか求めよ 不可能な場合は-11 解法 s[L,r]の…

SRM554 Div1 Easy - TheBrickTowerEasyDivOne

問題 高さrhの赤いブロックがrc個、高さbhの青いブロックがbc個ある これらのブロックを1個以上使い、同じ色のブロックが隣接しないように積み上げてタワーを作る タワーの高さとしてあり得るものの個数を求めよ1 解法 (rh=bhのとき) rc=bcのとき) 答えは明…

SRM553 Div1 Easy - Suminator

問題 suminatorという装置がある この装置には最初無限に0が詰まったスタックが入っており、長さnの非負整数のみからなる数列aを入れると、 1) 数列aの各要素を手前から1個ずつ見ていき、a[i]が0のときはスタックから2個取り出してそれらの和をスタックに入…

SRM552 Div1 Easy - FoxPaintingBalls

これはどういうことですかね 問題 1辺の長さがnである正三角形を成すようにボールが並べられている (合計n(n+1)/2個) このball triangleは無限にある ball triangleのボールを全て赤or緑or青で、隣り合う2つのボールは違う色であるように塗りたい 赤緑青で塗…

SRM551 Div1 Easy - ColorfulChocolates

問題 長さnの文字列sが与えられる sの隣り合う2文字をswapするという操作を最大k回まで行い、sで同じ文字が連続している部分の長さの最大値を最大化せよ 解法 s[i]を真ん中にして、s[i]と同じ文字をなるべく多く隣まで持ってくることを考えればいい 便宜上、…