きままにものづくり

日々の気付いたことなんかを書いてます。

SRM652Div1Easy

問題 2人で行う順列ゲームを考える。Aliceはxをはじめに選び、BobはサイズNの順列を選ぶ。 AliceはBobの選んだ順列を用いてf(x)を計算する。f(x)はf(1) = p[1]、f(m) = p[f(m-1)]で計算される。 Bobがどんな順列を選んできてもf(x)=1となる最小のxを求めよ。…

SRM651Div1Easy

問題 二次元平面を考える。この平面上にはロボットSと障害物#と空白.がある。 操作者はロボットに対して上下左右の四方向に移動するコマンドを送信できる。移動しようとする先のマスにより、実際の移動が変更される。 移動した先が空白だった場合は、そのマ…

SRM650Div1Easy

問題 サイズNの文字列を考える。この文字列はAとBのみで構築されている。M個のポジションとその文字が与えられ、隣り合う文字が同じとなる箇所の個数が最小となるパターンの総数を求めよ。 解法 与えれた文字とその間の文字数で答えが求まる。 以下のような…

SRM649Div1Easy

問題 サイズNの文字列が与えられる。その中からK個の文字を消した際に、消した文字とその場所が特定できるか判別せよ。 解法 K個の文字を消した後に得られる文字列が重複している場合、特定が不可能になる。ある要素からK個以内の範囲に同じ文字が存在すれば…

SRM648Div1Easy

問題 以下の性質を満たす文字列Sを求めよ。 要素はAかB サイズはN個 S[i]=A, S[j]=B () となるペアがK個 解法 Aの数をa、Bの数をBとし、a*b+c=Kとなるようにa,b,cを求める。c(=K-a*b)はAを左から詰めた時に、一番右のAをどれだけ右にずらすかを示す値である…

SRM640Div1Medium

問題 サイズがN1とN2の二部グラフが与えられる。グラフが以下の条件を満たす時のエッジの最大値を求めよ。 マッチングの値がc 各頂点の次数がd以上 解法 問題の条件を満たす時のエッジの数を方程式で表現し、それの最大値を計算することで答えが求まる。 N1…

SRM639Div1Medium

問題 N*Mの二次元配列が与えられる。各要素は0か1である。任意の境界を選択し、そこを基準に左右の二次配列が等しい時、サイズの小さい配列を削除することができる。 以上の操作をした際に得られる、配列の種類の総数を求めよ。 解法 縦方向に折りたたむ場合…

SRM638Div1Medium

問題 サイズNの配列が与えられる。配列内の要素aとbの和がmaxSize以下である場合は、その二つの要素を交換することができる。この時の配列のパターンの総数を求めよ。 解法 動的計画法で答えは求まる。 配列のパターンの総数を計算する関数をfとする。 配列…

SRM596Div1Easy

問題 サイズNの配列が与えられる。同じサイズですべての要素が0である配列から始め、与えられた配列と同じにするのに必要な最小操作回数を求めよ。 許される操作は以下の2つである。 ある要素を選び1を足す すべての要素に2をかける 解法 2進数で表記した際…

SRM645Div1Easy

問題 一年の間にN人の客がある宿に泊まりに来る。N人の滞在期間を表すarrivalsとdeparturesの二つの配列 が与えられる。宿主は特別なプロモーションを特定の人にかけることで、その人からよい評価をえることができる。また、プロモーションをかけられた人の…

SRM644Div1Easy

問題 N種類のお好み焼きとそのサイズの配列osizeが与えられる。M個のお好み焼きを選び、その中の最大サイズと最小サイズの差がK以下となるにする。この時のM個のお好み焼きの組み合わせを求めよ。 解法 与えられるサイズをソートする。 小さい方から、iを選…

組み合わせ組み合わせ剰余

コード

SRM647Div1Easy

問題 http://community.topcoder.com/stat?c=problem_statement&pm=13634N個のビルを建設したい。与えられる制限は以下の4つ。 高さは非負整数 一つ目のビルの高さは0 隣り合うビルとの高さの差分は最大で1 番目のビルの高さは、以下 ここで、はビルの番号を…

ARC016 C問題

問題 C: ソーシャルゲーム - AtCoder Regular Contest #016 | AtCoderarc016.contest.atcoder.jp 解法 N=10と十分小さいのでbitDPをする。 まだ持っていないカードを当てる時のくじを引く回数の期待値はとなる。wはカードを当てる確率である。これに、その時…

ARC017 C問題

問題 C: 無駄なものが嫌いな人 - AtCoder Regular Contest #017 | AtCoder C: 無駄なものが嫌いな人 - AtCoder Regular Contest #017 | AtCoder 解法 Nを分割し、それぞれに対して全探索を行う。探索結果をmapに保存しておき、ちょうどXとなる数を数えること…

ARC018 C問題

問題 C: 席替え - AtCoder Regular Contest #018 | AtCoder C: 席替え - AtCoder Regular Contest #018 | AtCoder 解法 pは常に素数であり、N*M以上なのでa mod pが0でない限り、全ての値が異なるものになる。a mod pが0である場合は、x0が他の値と同じなら0…

ARC019 C問題

問題 C: 最後の森 - AtCoder Regular Contest #019 | AtCoder C: 最後の森 - AtCoder Regular Contest #019 | AtCoder 解法 スタート地点からほこらまでの最短距離、ほこらからゴール地点までの最短距離を求めることで答えが求まる。 途中の敵の数を減らすた…

ARC022 C問題

問題 C: ロミオとジュリエット - AtCoder Regular Contest 022 | AtCoder C: ロミオとジュリエット - AtCoder Regular Contest 022 | AtCoder 解法 DFSをしながら、最大の距離とその頂点を記録しておく。 計算量 コード

ARC023 C問題

問題 C: タコヤ木 - AtCoder Regular Contest 023 | AtCoder C: タコヤ木 - AtCoder Regular Contest 023 | AtCoder 解法 −1の連続する区間を取り出す。例として2 -1 -1 9を取り上げる。この時の組み合わせは、3回の足し算で2を9にするための組み合わせとな…

arc024 C問題

問題 C: だれじゃ - AtCoder Regular Contest 024 | AtCoder C: だれじゃ - AtCoder Regular Contest 024 | AtCoder 解法 文字の出現回数を数える。数えた結果を集合に保存しておく。重なる箇所があるとアナグラムとならないので、そこはqueueを使う。 計算量…

ARC025 C問題

問題 C: ウサギとカメ - AtCoder Regular Contest 025 | AtCoder C: ウサギとカメ - AtCoder Regular Contest 025 | AtCoder 解法 目的地を固定し、ダイクストラで最短経路を計算する。カメの距離、ウサギの距離がとなる点の数を二分探索で計算する。 計算量…

ARC026 C問題

問題 C: 蛍光灯 - AtCoder Regular Contest 026 | AtCoder C: 蛍光灯 - AtCoder Regular Contest 026 | AtCoder 解法 愚直なdpを考える。テーブルは dp[廊下の位置]:=最小コスト とする。これだととなりTLEする。 区間lとrの中で最小の値を見つけるのにの時…

ARC027 C問題

問題 C: 最高のトッピングにしような - AtCoder Regular Contest 027 | AtCoder C: 最高のトッピングにしような - AtCoder Regular Contest 027 | AtCoder 解法 dp[カードの枚数][スペシャルカードの枚数]で動的計画法を行う。 計算量 コード

ARC028 C問題

問題 C: 高橋王国の分割統治 - AtCoder Regular Contest 028 | AtCoder C: 高橋王国の分割統治 - AtCoder Regular Contest 028 | AtCoder 解法 ツリー構造になっているので、子となる頂点をルートとした際のサブツリーの要素数をDFSで求めていく。バランス値…

ARC029 B問題

問題 B: 高橋君と禁断の書 - AtCoder Regular Contest 029 | AtCoder B: 高橋君と禁断の書 - AtCoder Regular Contest 029 | AtCoder 解法 角度に対して二分探索を行う。二分探索では0度の時(縦横が同じ状態)を見逃してしまうので、その点に注意する。 計算…

ARC030 C問題

問題 C: 有向グラフ - AtCoder Regular Contest 030 | AtCoder C: 有向グラフ - AtCoder Regular Contest 030 | AtCoder 解法 強連結成分を取り除けば、有向非巡回グラフ(DAG)になる。得られたDAGをトポロジカルソートすることで、dp[頂点番号][文字番号]で…

SRM637Div1Medium

問題 高さ2、幅Wのボードが与えられる。各マスは黒か白である。ひとつの白いマスを選択し、それを黒に変える。ただし、左側から右側に白いマスだけで行けるルートは残さないといけない。この操作を2人で交互に行う。操作ができなくなった方を負けとする時、…

SRM636Div1Medium

問題 高さH、幅Wのボードが与えられる。各要素は、'.'、'#'のどちらかである。r個のうさぎが与えられ、一様ランダムに'.'となっている要素にうさぎを配置する。 うさぎを頂点とし、Xとf(X)をエッジでつなぐ。Xはうさぎの番号を示し、f(X)はXから最も近いうさ…

ARC033 C問題

問題 C: 仕事計画 - AtCoder Regular Contest 032 | AtCoder C: 仕事計画 - AtCoder Regular Contest 032 | AtCoder 解法 辞書順の制限が無いの場合は、終了時間が早い順に選んでいく貪欲法で解くことができる。 辞書順の制限がある場合は動的計画法を用いる…

SRM441Div1Medium

問題 N個の頂点と、そろぞれの頂点同士の接続関係が与えられる。全ての頂点がつながっている状態にするのに必要な操作の最小回数を求めよ。できない場合は-1を返す。 許される操作は以下である。 4つの頂点A,B,C,Dを選ぶ。AとB、CとDは接続されてる。 AとBの…