そんなに難しくないが結構時間を食ってしまった。問題:http://community.topcoder.com/stat?c=problem_statement&pm=13669&rd=16314解法:まずpositionの順に文字をソートする。そして、確定した文字と文字の間に最適な文字の入れ方が何通りあるかを調べてい…

同じ回のdiv1medと同じ発想だったので早く解けてよかったのだが、mod 1000000009に惑わされて結構時間がかかった。問題:一部のセルが埋められたH*Wの２次元グリッドが与えられる。空白セルのうちK個を選択したとき、それらが隣接セル同士で連結しているよう…

問題:http://yukicoder.me/problems/296 解法:それぞれの点から点への距離をソートする。そして、距離が短いものから順につなげていき、グループを作る。そして、0とN-1が同じグループになった時のものさしの長さが求める答えとなる。これを実装するためにUn…

ただの引掛け問題なのでソースコード貼るだけ。 struct P{ int y; int x; P() {} P(int y, int x) : y(y), x(x) {} }; class RobotOnMoon { public: int longestSafeCommand(vector <string> board) { int n = board.size(), m = board[0].size(); P start; for (int</string>…

一つ一つのロジックは単純だけど、ぱっと見では全く方針が立たなかった。問題:abs(x), abs(y) 解法:全探索する。具体的には、 ①n匹の狐がどのような形をとることがあり得るかを調べる(createShapeのところ) ②それぞれの形について、狐の総移動量が最小になる…

よくこんなの思いつくなぁ。問題:http://community.topcoder.com/stat?c=problem_statement&pm=13596&rd=16316解法:まず直感的に思いつくのは、状態としてdp[n][k] = (頂点nにいて,Bobが残りk個のtokenを持っている時の解)を用意して、メモ化再帰的に解くと…

補集合を思いつくのに時間がかかった。問題:http://indeednow-qualb.contest.atcoder.jp/tasks/indeednow_2015_qualb_4解法:「その数を1つでも含む連続する部分列」ではなく、「その数をひとつも含まない連続する部分列」を考え、それを可能な部分列の合計か…

div2 medで簡単なバージョンの問題を解いていたので、かなり簡単に感じた。問題:http://community.topcoder.com/stat?c=problem_statement&pm=13229&rd=16316解法:結論から言うと、Bob側は1〜Nまでの任意の周期の順列を用意できるので、アリスがf(x) = 1と必…

TopCoderのDP難しい。問題:http://community.topcoder.com/stat?c=problem_statement&pm=13688解法:メモ化再帰を使う。メモしておく量は、dp[start][end] = (区間[start,end)だけで座ってる人の国の並び方を考えた時、並び方は何通りあるか)とする。 まず、e…

情弱故に敗北した。問題：http://codeforces.com/problemset/problem/527/C解法：最大の面積は(横の長さの最大長さ)×(縦の長さの最大長さ)に等しくなることに注目する。このことにより、横の長さの最大値と縦の長さの最大値をそれぞれ求めれば良いことになる…

どうも、mayokoです。 とりあえず目的としてはプロコンの解いた問題を載せていく目的で作りました。初めてのブログなのでどうなるかはよくわかりませんがよろしくお願いします。