TopCoder SRM587
250
「なにもしないか、X 段階段を昇る」を X=1,2,...,N まで繰り返す。ただし 1 段立ち止まってはいけない段がある。最もたくさん昇るときどこまでいけるか。
「毎回昇って大丈夫」か判定
500
三角形いくつかを XOR した気分の図形の面積を求めよ。
何箇所かに区切ってがんばって計算
1000
H*W のグリッドの各マスに対角線を書く。書き終わった後に各頂点に赤青緑のどれかの色をつけて、線で結ばれている頂点同士が異なる色になるようにしないといけない。最初いくつかのマスに対角線が書かれている。可能な対角線の書き方のうち辞書順最小 (N, Z でコード化する) のものを求めよ。
ある 2 つの行/列を比較したときに、片方がもう片方と一致しているか完全に反対になっているかしないといけない。Union Find みたいなことをすると、? 入りの状態でも可能パターンか判定できる。
TopCoder SRM586
250
1 次関数をいくつかくっつけた形をした関数 f(x) がある。y = f(x) の解の個数の最大値を求めよ。無限にある場合は -1 を返せ。
500
いくつかの国があり、それぞれ異なる暦を使っている（互いにちょうど整数年ずれている）。各国での各王の在位期間も与えられる。「ある国のある王の時期と、他のある国のある王の時期が重なっている」という情報がいくつか与えられる。さらにこの形のクエリがいくつか与えられるので、クエリが与えられた情報に矛盾しないか判定せよ。
適当に暦の基準をおいてそこからの各暦のずれを考えると、各情報は差がある範囲内にないことを示している。これは最短路問題に帰着でき、クエリごとにそのクエリを情報にくっつけて、最短路問題を解き、負閉路がないか判定する。
1000
文字列の重さを「各文字について、文字列中のその文字の現れの最も右の位置 - 最も左の位置を考え、その和」とする。使える文字は [A-Z] である。文字列が light であるとは、同じ長さの文字列の中で最も重さが小さいことを言う。
今、i = 0, 1, ... に対して長さ L[i] の light な文字列を作り、それを順につなげたものを考える。つなげてできる文字列の重さの最小値を求めよ。
文字列が light である条件は、「min(26, L[i]) 種類使っている」かつ「同じ文字は連続している」である。つなげた文字列を考えるときは、実は前者だけ考えればよい（後者に反したところで足を引っ張るだけなのでうれしくない）。
ここで各文字ごとに [位置][使用中の文字数][使用して前の文字列までで捨てた文字数][使用して今の文字列で捨てた文字数] をキーに DP する。（一番左の文字が出てきたら使用を開始し、使用の終了は一番右の文字を出すことに相当する）次の文字に移るときには、使用中の文字数だけのコストがかかる。次の文字列に移る時、「使用中の文字数」「使用して今の文字列で捨てた文字数」を足して min(26, L[i]) になればよい。
結果
いつも通り「あたしのいくじなし〜＞＜」
easy 落ちた＞＜
xoo 799.08 (5 位)
rating: 2973 -> 3027 target!!!
TopCoder SRM580
▂▅▇█▓▒░(’ω’)░▒▓█▇▅▂
TCO2013 Round2C
250
きつねたちの間でダンスパーティが開かれている。A, B が友人もしくは、ある C が存在して A, C、B, C がいずれも友人であるときに A, B はダンスをすることができる。後者の場合ダンスの後 A, B は友人になる。1 回の曲の間に、各きつねは高々 1 人とダンスをすることができる。きつね 0, 1 が友人になるのに必要な曲の個数を求めよ。
Warshall-Floyd を実施して、きつね 0, 1 の間の距離 - 1 を返した人がたくさんいますが、複数のきつねの組が同時にダンスを実施することができるのでちがいます。
距離を d として、d == 1 となるまで d -= (d+1)/3 を行った時の処理回数を返すとよい
dist - 1 をやる人が出そうだとなぜか気づいたので 2 個落としておいた
TCO でこんな（気づく人は気づいて大虐殺が発生する）challenge ゲー出すのどんびきだなあ
500
200*200 くらいの盤面があって、あるマスが頂点である。各マスに正の整数を書き込むが、頂点に向かっていく列は strictly increasing でないといけない。いくつかのマスには最初から数字が書かれていて変更できない。マスの数字の和を最小化せよ。
各マスの数字を最小化すればいい。頂点の左上、右上、左下、右下は頂点の位置によらず一意に最小なものを決定できる。頂点を動かして、頂点の上下左右のマスたちを適当に決定すると O(N*M*(N+M)) くらい。
TopCoder SRM578
250
盤面上にいくつか鳥がいて、そのうち何羽かは goose である。goose は 1 羽以上存在し、偶数羽存在する。goose から Manhattan 距離 D 以下の鳥は goose である。goose の場所のパターンは何通りあるか。
距離 D 以下の鳥の属性(goose or not) は同じでないといけないことが示せる。
Union Find したあと DP した
500
直線状のマス目の上に何頭か wolf がいる。1 マスに wolf は高々 1 頭いる。いくつかの、「この範囲には wolf は高々 2 頭しかいない」情報が与えられる。wolf の場所は何通り考えられるか。
[位置][最後の wolf の位置][その前の wolf の位置] で DP
1000
わからない
challenge phase
あたしのいくじなし〜＞＜
結果
oox 633.67 (14 位)
rating: 2783 -> 2824
TopCoder SRM577
250
人々と自分の rating 一覧が与えられる。単純な規則に従ってランダムに SRM? の部屋割りを決める。自分の部屋の rating の平均値の期待値を求めよ。
自分の rating がすごい低い（最後に部屋に割り振られる）かそうでないか（そこでさらに自分の部屋の人数）で場合分け。面倒だった＞＜
500
8*8 の盤面に、いくつか小石を置く。小石を置くときには次で定めるコストがかかる：「新しく小石を置く位置から、すでに小石が置かれている位置までの Manhattan 距離の最大値」コストの和を最小化するときのコストを求めよ。
Manhattan 距離は扱いにくいが、よく知られているように (x, y) -> (x+y, x-y) の座標変換を実施すると 2 点の距離が「x, y 座標の差の絶対値のうち大きい方」で求められるようになる。
ここで、座標変換後に「すべての長方形領域の内部の小石たち」について最小コストを求める DP をすると、なぜか答えが出る（コストを求めるのに必要なのは、今まで置いた小石の x, y 座標の最小、最大値だけであり、さらにその間にある小石たちは後に置くよりも領域が小さい頃に置いたほうが明らかにコストが少ないから）。盤面がすごい小さいので多項式なら計算量ほとんど気にしなくてよい。
1000
盤面のいくつかのマスを黒く塗る。ただし、一度に黒く塗れるのは「縦または横に連続した白マスたち」だけである。目的の状態にするには最低何回塗る必要があるか。
50*50 とあるしどうせフローに極っているだろうと思って考えたが解けなかった＞＜フローの使い方がよくなかったらしい
結果
oox 597.14(7 位)
rating: 2697 -> 2783
TopCoder SRM573
配点をみて驚愕
250
ソートして、自分のチームの順位を下げる方向に貪欲。
残っているものから順に、「max を選ぶ」「できる限り低く min を選ぶ」「できる限り低く mid を選ぶ」を行う。
450
(位置, 高さ) で Dijkstra。高さはどこかの位置の高さになっているものだけ考えればよい。
850
まず 45°回転する。すると、ある点から他の点までの行き方がよい性質を満たすので、それを使うと解けそう。100000! の逆元を求めるのが大変（コンピュータに力ずくで計算させた）
でも systest で落ちた＞＜
結果
oox 635.02(11 位)
rating: 2607 -> 2680
