きままにものづくり

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

2015-04-01から1ヶ月間の記事一覧

SRM594Div1Easy

問題 N個の惑星の相対サイズAとM個の惑星の相対サイズBが与えられる。各要素は中心からの距離が近い順に並べられている。相対サイズとはある基準に対して何倍であるかを示す値である。AとBそれぞれの中では基準は同一であるが、AとBで同じ基準であるとは限ら…

SRM595Div1Easy

問題 サイズMの配列が与えられる。各要素は白か黒である。その配列に対してロボットがある操作を行う。ロボットはサイズNの配列L,Rを持っている。その配列に従い、L[i]~R[i]までを白か黒で塗りつぶす。ロボットの作業が終わったあとの配列の状態の総数を求め…

SRM557Div1Easy

問題 隣り合う要素の差分が1である長さnの数列を考える。はじめの要素h0と最後の要素hnが与えられる。差分を示す文字列historyが与えられた時、そのhistoryを実現できるかを判定せよ。historyの要素はUかDのどちらかで、Uはh[i+1]-h[i]=1、Dはh[i+1]-h[i]=-1…

SRM645Div1Medium

問題 二次元平面上にN個の点が(x1,y1)と(x2,y2)が与えられる。平面上には3つの塔があり、ひとつの塔を指定し魔法を唱えると、その塔を中心に点対象に点を移動できる。(x1,y1)の点を(x2,y2)に移動できるかを判別せよ。 解法 TopCoder SRM 645 Div1 Medium Arm…

SRM643Div1Medium

問題 2行N列の行列が与えられる。各要素はHかSである。以下の3つの操作を行い、すべての要素をHにするための最小の操作回数を求めよ。 どれか一つの要素を選びXとし、それと隣り合っている要素を一つ選びYとする。Xの要素をYの要素に書き換える。 連続する列…

SRM642Div1Medium

問題 H個の木がある。各木のはじめの高さはで与えられ、の高さだけ毎日成長する。木を切るためのデバイスがD個与えられる。これは、高さが以上の木を高さに切ることができる。その日の最後にデバイスを使用することができる。各デバイスは1日に一度しか使え…

SRM656Div1Easy

問題 サイズNの配列が与えられる。i番目の要素はパンケーキの美味しさを示し、サイズはi+1とする。 以下の操作を行ったあとの美味しさの総和の期待値を求めよ。 選択されていないパンケーキを一様ランダムに選ぶ 選んだパンケーキのサイズがスタックの上にあ…

SRM655Div1Easy

問題 サイズX、Yの二次元配列が与えられる。各要素はWかBである。同じサイズの全ての要素がWの二次元配列から以下の操作を行い、与えられた配列にすることができるかを判定せよ。 操作は二次元配列と共に与えられるkを用いて行う。サイズkの正方形を二次元配…

SRM654Div1Easy

問題 サイズNの配列が与えられる。各要素は小文字のアルファベット(a-z)か?である。?は小文字のアルファベットに変更することができ、各アルファベットへの変換確率はpで与えられる。 全ての要素が同じ部分配列の数がその配列のスコアとする。与えられた配列…

SRM653Div1Easy

問題 様々な国から来たN人が一列に並んでいる。その内の何人かにどこの国から来たのかを聞いた。同じ国から来た人は隣合っている。 現状の調査結果を表す配列Aが与えられる。この結果から、全ての解答を一意に予測できるか求めよ。 解法 Coding is fun: SRM …

SRM641Div1Medium

問題 サイズ2Nの配列が与えられる。サイズ2Nの昇順にソートされている配列から、与えれた配列に変更するための最小な操作数を求めよ。以下の操作を1とする。 先頭のN個と次のN個に分け、前者を集合A、後者を集合Bとする。 Aの要素とBの要素を交互に繰り返し…

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を選…

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

コード