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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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