TopCoder
なんで DP 2 個なんだろう 250 ハンバーガーがたくさんあり，それぞれ type と taste が決まっている． このうちの 0 個以上を食べる．このときのうれしさは，(type の種類数) * (taste の和) である．最大値を求めよ．type ごとに，使った時の得られる tast…
250 文字列 A に対して，「1 文字選んで先頭に持ってくる」操作を行うことができる．A を別の文字列 B に変えるために必要な操作の回数は？A の部分文字列で，B の後ろのほうに一致しているものの最長の長さを求める． 600 凸多角形が与えられるので，その内…
writer でした。今回は Magical Girl がどこにも登場しませんでした D2Easy - KeyDungeonDiv2 各ドアに対して独立に考えてよく、赤鍵と緑鍵だけで開けようとして、足りない分を白鍵で補って開けられればよいです。 D2Mid / D1Easy - GUMIAndSongsDiv[1|2] ど…
250 「なにもしないか、X 段階段を昇る」を X=1,2,...,N まで繰り返す。ただし 1 段立ち止まってはいけない段がある。最もたくさん昇るときどこまでいけるか。「毎回昇って大丈夫」か判定 500 三角形いくつかを XOR した気分の図形の面積を求めよ。何箇所か…
250 1 次関数をいくつかくっつけた形をした関数 f(x) がある。y = f(x) の解の個数の最大値を求めよ。無限にある場合は -1 を返せ。各点と、±εの点を y として試す。vector を vector に移すというアホなミスで落とした＞＜ 500 いくつかの国があり、それぞ…
▂▅▇█▓▒░(’ω’)░▒▓█▇▅▂
250 きつねたちの間でダンスパーティが開かれている。A, B が友人もしくは、ある C が存在して A, C、B, C がいずれも友人であるときに A, B はダンスをすることができる。後者の場合ダンスの後 A, B は友人になる。1 回の曲の間に、各きつねは高々 1 人とダ…
250 盤面上にいくつか鳥がいて、そのうち何羽かは goose である。goose は 1 羽以上存在し、偶数羽存在する。goose から Manhattan 距離 D 以下の鳥は goose である。goose の場所のパターンは何通りあるか。距離 D 以下の鳥の属性(goose or not) は同じでな…
250 人々と自分の rating 一覧が与えられる。単純な規則に従ってランダムに SRM? の部屋割りを決める。自分の部屋の rating の平均値の期待値を求めよ。自分の rating がすごい低い（最後に部屋に割り振られる）かそうでないか（そこでさらに自分の部屋の人…
配点をみて驚愕 250 ソートして、自分のチームの順位を下げる方向に貪欲。 残っているものから順に、「max を選ぶ」「できる限り低く min を選ぶ」「できる限り低く mid を選ぶ」を行う。 450 (位置, 高さ) で Dijkstra。高さはどこかの位置の高さになってい…
問題 うさぎがプログラミングコンテストに参加した。コンテストはいくつかの問題からなり、そのうちいくつかは採点され全うさぎについての正誤が判明しているが、それ以外の問題についてはまだどのうさぎの正誤も判明していない。 このコンテストの上位 qual…
250 パスワードの先頭 K 文字と末尾 K 文字が一致するように、パスワードの文字を変える。できるだけ変える文字数を少なくするときその数を求めよ。union find を使うとどことどこが等しいかわかるのでやるだけ 500 hit and blow の hit だけバージョン。質…
div1 なのにやたら自明だった 250 自明 500 やるだけ 1000 長さが奇数だったら最後の文字は決して動かない。 あとは 2 文字ずつ動く（2 文字内の順番はどうでもいい）。 それぞれ可能な辞書順最小文字列に変換してからソートする。 結果 16 分で終わって眠く…
ひさしぶりに SRM した 250 一瞬「えっ＞＜」ってなるもちょっと書きだしてみたら（根拠もなしに）N≡0,2 mod 3 のときは全色同じずつ、N≡1 のときは 1 色だけ多くなるだろーって思って二分探索した 500 長方形 2 個選ぶ典型問題。 長方形 O(N^4) 通り全部調…
writer やってました。 Div2 Easy(250) AkariDaisukiDiv2 f(X) = Waai + X + Akari + X + Daisuki なる string -> string の関数を考える時、S = f(X) なる (Waai, Akari, Daisuki, X) の組の数を求めよ。問題名とかいろいろおかしいですが(ivan さんに「"Wa…
問題 係数が mod 2 の世界で、N (高々 49)次の多項式の M (高々 1016) 乗の K 乗の係数を求めよ。 解法 まず、多項式の M 乗は結構大変なことになりうるので、大変なことにならない状態を考える。 多項式の 2 乗を考えると、mod 2 の世界では各項の指数が 2 …
300 N曲あって、P曲分の長さのプレイリストを作る。プレイリストには各曲1回以上含まれねばならず、また同じ曲を流す場合は間にM曲以上他の曲がないといけない。何通りのプレイリストが存在するかmodで計算せよ。見た瞬間「うげっ」ってなったが「各曲1回以…
250 なにかがN個あり、1〜Nの番号がついている。「平方数番目のものをすべて取り除き、元の番号順に1から順に番号を付け直す」行為を1個になるまで行う。最後に残ったものは最初何番目だったか。よくわからないので再帰を使って解いたらNが1,000,000,000のと…
問題 ある国のコインは、次のような単純な規則に従っている。 それぞれのコインは、正の整数の価値を持つ。 価値1のコインが存在する。 任意のコインの価値は、それより価値の低いコインの価値の整数倍である。 ある金額を払う時、これらのコインを使って何…
問題 魔法少女回。魔法少女が呪文を唱える。呪文は0,1からなる文字列である。最初のK個の呪文(A[0]..A[K-1])は決まっている。i>=Kのとき、A[i] = A[i-1] + A[i-K-1] + A[i-2K-1] + …（i-nK-1>=0の限り繰り返し）である。呪文Sを、A[N]の[lo, hi]の部分とする…
300 グリッド上に石が何個か乗っかっている。今、方向を選んで、その方向にすべての石を1マス動かすという操作ができる。落っこちた石は棄てる。残りの石をちょうどK個にするために必要な操作の回数の最小値を求めよ。残りの石は長方形状の場所に収まること…
問題 高々21*21の盤面が与えられる。各マスは'.'か、アルファベットが書かれている。アルファベットは21種類のうちどれかである。今、この盤面上で「パス」を考える。パスは、iマス目がi+1マス目に隣接している(1 解法 まず、パスの定義に「互いに異なる」と…
問題 平面上にいくつかの点があり、いくつかの点の間は道で結ばれている。道同士は端点以外で交差しない（しても接続しない）。2点間の最短距離は、道の上のみを通り、接続点のみで道を変えたときの最短距離である。道の上から2点選ぶとき、最短距離の最大値…
問題 何種類かの硬貨がたくさんあり、それぞれ額面が決まっている。常に1単位硬貨が存在する。 ある両替機は、いくらかのお金(2単位以上)を受け付けて、次の規則で両替する。 「2枚以上の硬貨に両替する。但し、枚数は可能な限り少なくする。枚数が同じとき…
問題 グリッド状の土地があり、金鉱、銀鉱、ワークスペースがある。それ以外のマスには芝生か岩である。 何人かの労働者を雇って、金銀の採掘をさせたい。各労働者には1つずつの金鉱、銀鉱、ワークスペースが与えられる。これらは複数人の労働者で共有しては…
問題 N*Nのボードがあり、色の異なるチェッカーがある。色iのチェッカーはcheckers[i]個ある。回転させて重なる配置を同じ配置と考えるとき、何通りの異なる配置があるか。 解法 90°回転で重なるものがA通り、180°回転で重なる(かつ90°回転で重ならないもの)…
250 二進法ほげほげ。落ちた 600 6個ぐらいの文字列（a-zから構成される）がある。長さLの文字列で、それらのうちちょうどC個を含むような文字列は何個あるかをmodで答えよ。Aho-CorasickしてビットDPするだけに見えて、実際それで通る。Aho-CorasickはPKUの…
問題 真っ白な長方形のグリッドに対して次の操作ができる。「ある行か列を選んで、好きな色で全部塗りつぶす」白く塗ることはできない。すでに塗ってあるところの色は変わる。目標の状態にするには最低何回操作する必要があるか？ 解法 ある行や列に対して、…
512記念回 256 めんどう 512 「ふぃぼる」 おちた 1024 がんばれば解けそうだけど512のせいで時間なかった 結果 135位（下から数えたほうが早い） Rating: 2532 -> 0訂正2505
死亡 250 全部足して何か掛けて%9するだけ。辛うじて通った 500 謎 1000 意味不明 結果 不参加(177位) rating:2582->2532
