Lyft Level 5 Challenge 2018 Final Round Div2 E - Optimal Polygon Perimeter

各点間のマンハッタン距離の和 = 長方形の周長ってのが完全に抜けてた なんで解けなかったんだマジで そういう問題最近SRMでやったし 問題 n頂点の凸多角形が与えられ、時計回りでi番目の頂点の座標は(x[i],y[i])である このn個からk個の頂点v1, v2, ..., vk…

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の奇数乗なら後手、それ以外は先手が勝つ このゲーム…

第3回ドワンゴからの挑戦状 本戦 A - 計算ドリル

俺のrated500埋めの最後の問題がこれ atcoderでこういう実装ゲーはかなり珍しい 問題 '0'〜'9'、'+'、'-' のみからなる文字列sが与えられる これをk文字まで書き換えて得られる、逆ポーランド記法で計算できる正しい文字列のうち、計算結果の最大値を求めよ1…

ARC087 F - Squirrel Migration

これ800点ってマジ?ムズすぎてハゲた 問題 n頂点の木があり、全ての頂点にリスがいる 長さnの順列pを決め、頂点iのリスを頂点p[i]に移動させる 各リスの移動距離の総和が最大になるようなpは何通りあるか2 解法 x-yを繋ぐ辺を通るリスの数の最大値は、xyそ…

Codechef - Chef and K Segments [CHEFKO]

問題 n個の区間があり、i個目区間の左端はL[i]、右端はr[i]である これらから好きな区間をk個選び、それら全ての共通区間の長さをスコアとする スコアの最大値を求めよ1 1 解法 スコアを二分探索すれば解ける スコアをdにすることが出来るかの判定方法を考え…

CF519 F - Make It One

良問だった 問題 n個の整数aが与えられる aの部分集合のうち全要素のgcdが1になるようなもののサイズの最小値を求めよ (存在しない場合は-1)1 1 解法 2*3*5*7*11*13 より答えはたかだか7であることがまずわかる dp[i][j]: i個の要素を含み、それらのgcdがjに…

CF519 D - Mysterious Crime

超凡ミスで2問落としてまた1893まで落ちちゃった マジで深夜はパフォーマンス落ちる 問題 長さnの順列がm個与えられる それぞれの順列の先頭と末尾からいくつかの数字を消し、全ての順列を一致させたい 数字の消し方は何通りあるか1 1 解法 1個目の順列が 1,…

Tenka1 Programmer Contest 2018 E - Equilateral

はてなブログたまに写真表示されなくならないか? 問題 h*wのグリッドがあり、いくつかのマスにはコインが置かれている 相異なるコイン3つの組のうち、どの2つのコイン同士のマンハッタン距離も同じであるようなものは何個あるか1 解法 マンハッタン距離って…

Codechef - Country Tour [CTOUR]

Encoderっていうコンテストの最後の問題 何気なく参加してみたけどこの問題は個人的に面白かった 問題 n頂点の木が与えられ、根は頂点1である 辺iは頂点a[i]とb[i]を繋ぎ、通る時c[i]円貰える (c[i]が負のこともあり、そういうときは逆に-c[i]円払わないとい…

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とす…

ARC081 F - Flip and Rectangles

問題 h*wのマス目があり、各マスの色は黒か白である 「ある行[列]を選び、その行[列]の全てのマスの色を反転する」という操作を任意の回数行える 黒いマスのみを内側に含む長方形の面積の最大値を求めよ2 解法 タテかヨコの長さが1の長方形は明らかに自由に…

EducationalCF53 E - Segment Sum

かなり残念な落とし方をした 4完でもhighest更新したからこれも通ってれば・・ 問題 L以上r以下の整数のうち、各桁の数字の種類がk以下であるものの和を求めよ1 1 解法 とりあえず求めるものは (r以下の条件を満たす数字の和) - (L-1以下の〜) としてok 1桁…

CF518 Div2 D - Array Without Local Maximums

これ割とあからさまなdpじゃない? 問題 いくつかの要素が-1になっている長さnの数列が与えられる ↓の条件を満たすように-1を1〜200に変えるとき、何通りの数列が作れるか 1) a[1] 2) a[n-1] >= a[n] 3) a[i] 2 解法 dp[i][j][k]: i-1番目まで埋め終わってて…

CF518 Div2 C - Colored Rooks

こんなしょうもない構築が解けなくてまたdiv1に戻れなかった もう深夜のコンテストはレート落ちるの覚悟で出るべきかな・・ 問題 色がn個あり、m個のペア(a[i],b[i])も与えられる 10^9 * 10^9のチェス盤があり、好きな位置にルークを最大5000個置くことがで…

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が入っている 絵の各マスの色は赤か緑か青か透明で、キャンバス上のある位置にこれを貼り付けると、絵の色付きのマスが乗るマスはその色で上書きされ、透明…