解いた問題のソースコードと解説など。


SRM

SRM 348 Div1 Medium RailwayTickets

問題 (意訳)数直線上に線分が幾つか与えられる。任意の地点で重複する線分はseats以下にしたい。取り除かねばならない線分の最小の数を求めよ。ただし線分の端点は重複と数えない。 問題 線分の右端でソートして貪欲。 ソートした上で数直線上を最初から見…

SRM 349 Div1 Medium DiceGames

問題 目の数が異なるサイコロが複数与えられる。各サイコロの目の数はsides[]である。サイコロを一斉に降った時に、サイコロを区別しないとして出る目のパターン数を求めよ。 やりかた サイコロを目の数でソートしてDP。 dp[i][j]:=(サイコロを目の数の小さ…

SRM 344 Div1 Medium QuantumAlchemy

問題 'A'から'Z'までの26種類の物質が存在しており、あなたが持っている物質は文字列initialで表されている。また、いくつかの物質を1つずつ組合わせて別の物質を1つ錬金することができ、これらの組合せがreactionsに記述されている。持ち合わせている物質か…

SRM 340 Div1 Medium CsCourses

問題 CSの授業がいくつか用意されており、i番目の授業にはtheoreticalValue[i]とpracticalValue[i]とexpire[i]という3つの数値が与えられている。各授業の履修期間は一ヶ月で、あなたはひと月に授業を一つだけ取ることができる。そしてあなたは理論スキルと…

SRM 338 Div1 Medium RandomSwaps

問題 長さarrayLengthの配列がある。ここから無作為に2つの要素を取り出し、交換する動作をswapCount回行う。この後に当初a番目にあった要素がb番目に移動している確率を求めよ。 やりかた 典型的なDP。 dp[0][i]:=(i回スワップした後にbに移動している確率…

SRM 331 Div1 Medium Shopping

問題 コインが複数種類あり、それらの金額が与えられる。各金額のコインは無尽蔵にあるとする。1~Xまでのすべての金額を支払えるようにコインを選ぶとき、このコインの枚数を最小化せよ。 やりかた 公式解説を参考にしました。 ある時点で選んだコインの総…

SRM 328 Div1 Medium BlockEnemy

問題 都市がいくつかあり、都市間の道の情報とその道を壊すコストが与えられる。任意の都市間で往来ができるように道路が敷かれており、そのパスは必ず1つだけである(要は閉路がない)。敵に征圧された街の番号が与えられるので、道路をいくつか壊して、征…

SRM 325 Div1 Medium TournamentPlan

SRM

問題 グリッド上の町にN人の競技者がいて、i番目の競技者が(street[i], avenue[i])にいる。競技者は道路の交差した位置で出会うと競技を行って勝敗を決める。この競技で総当り戦を行うとき、全競技者の総移動量を最小化せよ。 やりかた どこかの交差点に全員…

SRM 322 Div1 Medium ExtendedDominoes

問題 2x1セルのドミノが複数あり、各セルには0~9の数字が書かれている。ドミノの右側の数字とその隣のドミノの左側の数字が同じになるようにドミノをつなげていき、ドミノがループをなるようにする(最左のドミノの左セルと最右のドミノの右セルの数字がおな…

SRM 320 Div1 Medium ContestSchedule

問題 プログラミングコンテストがいくつか開かれ、それらの開始時間、終了時間、勝率が空白で区切られた1つの文字列"s t p"の形式で与えられる。あるコンテストに出場している間は他のコンテストには出場できない。最適な出場の仕方をした時に、勝てるコン…

SRM 316 Div1 Medium PlacingPieces

問題 直線の棒がいくつか与えられ、それらの長さはpieces[]である。この棒からいくつか選んで長さL上の板の上に、はみ出ないように、かつ区間が互いに重ならないように置いていく。棒を置いていない区間に残りの棒が1つも置けないようになったら終了とする…

SRM 315 Div1 Medium SillySudoku

問題 4x4の数独があり、ところどころは数字で埋められている。この状態での正解パターン数を求めよ。 やりかた 深さ優先探索で通る。1~4の順列を生成して各行を試していき、マスが全部埋まったところで正解かどうか調べればいい。マスが小さいので枝刈りは…

SRM 314 Div1 Medium GrasslandFencer

問題 フェンスが複数あり、それらの長さが与えられる。フェンスを使って三角形をいくつか作るとき、できた三角形の面積の総和を最大化せよ。ただし、複数のフェンスを使って1辺とすることや、1つのフェンスを複数に分割することはできない。 やりかた bitDP…

SRM 301 Div1 Medium EscapingJail

問題 各ノード間の距離が与えられる。任意の2点間の最短距離を求めた時、それらのなかで最長距離を求めよ。 やりかた Warshall-Floydして、最長のものを求める。 class EscapingJail { public: int p(char c){ if('0' <= c && c <= '9') return c - '0'; if(…

SRM 607 Div1 Easy PalindromicSubstringsDiv1

問題 文字列がいくつか与えられる。これらをすべて連結してできた文字列のうち、'?'をランダムに置き換える。その文字列の部分文字列のうち回文の個数の期待値を求めよ。文字列長 やりかた 文字を一つ選び、それを中心に文字列を左右に広げていき、それが回…

SRM 320 Div1 Easy ExtraordinarilyLarge

問題 数字xとyがあたえられる。数字には0個以上の!がついており、これは階乗演算を表す。x,yの大小比較をせよ。 やりかた たとえば100!!!と1000!!を比較するとき、!の多いほうが、少ない方と同じになるまで階乗計算を行えばあとは数字の部分を比較するだけで…

SRM Div1 Easy 100問終了

Div1 Easyの556~615、315~354の計100問を2周した(2周目はできなかったもののみ)。ほぼ予定通り。これで315~615のEasyは埋めることができた。 引き続き、要復習のものに絞って3週目を行う予定。ほとんどブログを更新できなかったのがちょっと残念だった。

SRM 587 Div1 Easy JumpFurther

問題 無限に続く階段があり、あなたはその0段目にいる。あなたはN回行動を起こし、i回目(1-indexed)の行動では+i段上に進むか動かないかを選べる。しかしbadStep段目が壊れていて、この段に立つことはできない。到達できる最上段を求めよ。 やりかた 毎回上…

SRM 583 Div1 Easy TravelOnMars

問題 Nの都市が円状に存在している。i番目の都市は前後range[i]個の都市との間に一方向の道路が敷設されている。startCityからEndCityに訪れるために必要な最小の通過道路数を返せ。 やりかた N - 1と0番目の都市が隣り合っていることに注意しつつ、ただのグ…

SRM 580 Div1 Easy EelAndRabbit

問題 うなぎが複数匹おり、i番目のうなぎは狐の眼前をt[i]秒からt[i] + l[i]秒にかけて通過していく。狐は2回うなぎを獲ろうとし、1回の試行で眼前を通過しているうなぎを好きなだけ獲得できる。最大獲得数を求めよ。 やりかた 調べるべきポイントは各うなぎ…

SRM 578 Div1 Easy GooseInZooDivOne

問題 2次元グリッドが与えられる。'v'で与えられるセルにはガチョウかアヒルがいる。これらの鳥の配置には以下のようなルールがある。 少なくとも1羽は必ずガチョウであり、必ず偶数羽いる 互いにマンハッタン距離でdist以内にいる鳥はガチョウである ガチョ…

SRM 576 Div1 Easy ArcadeManao

問題 2Dゲームの画面が与えられる。'X'で表されるセルが足場を示しており、最下段は全て足場になっている。垂直に位置する2つの足場は、その2つの間の距離以上の長さを持つはしごを使って行き来することができる。最下段から目的地(coinsColumn, coinsRow)ま…

SRM 574 Div1 Easy TheNumberGame

問題 プレーヤーが二人いて各々が数字をひとつ持っている。この数字は10進数表記で0を含んでいない。1ターンごとに交互の順番で以下の2つの操作のうち好きな方を選んで行う。 数字を逆順にする 数字を10で割る 先方のプレーヤーが1000ターン以内に後方の持つ…

SRM 573 Div1 Easy TeamContest

問題 3*Nの要素を持つ配列strengthが与えられる。この要素を3つずつN個のグループに分ける。最初の3つの要素をまとめたものがあなたの所属するグループである。グループの強さはグループのstrengthがx,y,zだとすると max(x,y,z) + min(x,y,z) で決まる。残り…

SRM 568 Div1 Easy BallsSeparating

問題 箱がN個あり、i番目の箱には赤色のボールがred[i]個、緑色のボールがgreen[i]個、青色のボールがblue[i]個入っている。すべての箱に対して、それぞれの箱に入っているボールの色数が必ず1色以下になるようにボールを他の箱に移動したい。動かす最小の…

SRM 570 Div1 Easy RobotHerb

SRM

問題 ロボットが2次元座標上に位置している。ロボットの一連の動作が数列aで与えられており、これによるとロボットのi番目の動作は a[i]前進し、a[i]回右に90度回転する である。 この一連の動作をT回行った後の到達点と出発点の間のマンハッタン距離を求め…

SRM 569 Div1 Easy TheDevice

SRM

問題 長さの同じN個の文字列がある。文字列は0か1で構成されている。ある機械があり、これはN個の文字列のうちの2枚を入力とし、各桁に対してANDかORかXORを行った(桁ごとにAND, OR, XORのどれを行うかは異なる。)結果を出力する機械である。各桁が行う処…

Div2 Hard 455~554 までの100問の2周目が終了

http://area.hateblo.jp/entry/2013/12/31/015531できなかったもののみやりなおした。といってもほとんどだけど。 そのおかげかも知れないが、Div2 Hardは本番でも解けるということが何回かでてきた。それでもDiv1Easyを落っことすのですぐDiv2に落ちてくる…

SRM 531 Div2 Hard KingdomReorganization

http://community.topcoder.com/stat?c=problem_statement&pm=11282 問題 王国にはNの街があり、街と街の間がつながっているかがkingdom[i][j]で与えられる。また、街と街の間に新たに道路を作る費用がbuild[i][j]で、道路を壊す費用がdestroy[i][j]で与えら…

SRM 520 Div2 Hard SRMSystemTestPhase

問題 SRMというオンラインプログラミングコンテストがあり、コンテストでは3問出題される。複数人のコンテスタントの結果が与えられる。この結果は成績上位から順に並べられたものであるものの、その表記が曖昧で、各人がどの問題を提出したかの情報しか与え…

しょげないでよBaby 眠れば治る