読者です 読者をやめる 読者になる 読者になる

きままにものづくり

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

SRM581Div1Easy

問題 N個のコンテナとM個の監視カメラを考える。監視カメラは連続したL個のコンテナを監視できる。コンテナが空の場合は"-"となり、何か入っている場合は"X"となる。カメラの位置は分からないが、カメラが監視している空でないコンテナの数は与えられる。 こ…

SRM582Div1Easy

問題 N人の戦士が与えられ、それぞれの戦士の強さはs[i]である。また、M種類の強さes[j]を持つec[j]匹のモンスターも与えられる。戦士は自身より強さの小さいモンスターを討伐できる。戦士は一匹のモンスターを倒すと疲労度が1増える。すべてのモンスターを…

SRM583Div1Easy

問題 N個の街がひとつの輪となるようにつながっている。各街からは電車が出ており、それぞれの電車は最大range[i]個の街を移動できる。startからendまで行くのに必要な電車に乗る回数の最小値を求めよ。 解法 最短路問題に帰着できる。 ダイクストラで解いて…

SRM584Div1Easy

問題 ある国にはN人の国民がおり、それぞれ貯金を持っている。この国のルールとして貯金額の差がdより大きい人同士では友達になることはできない。 友人関係を示す情報とdが与えられた時、国民間での貯金額の最大値を求めよ。有限値でない場合は-1を返す。 …

SRM585Div1Easy

問題 高さNの二分木が与えられる。すべてのノードに車が通るようにするためには、最小でいくつの車が必要か求めよ。 ただし、車は他の車も含め一度通ったノードをもう一度通ることはできない。 解法 動的計画法で求まる。 一番外側のノードを一台の車に走ら…

SRM586Div1Easy

問題 サイズNの配列Yが与えられる。配列の要素は座標を示しておりインデックスをxとした時、(x, Y[x])となる。隣り合う点どうしを直線で結びグラフを作成する。 x軸と平行な線と作成したグラフとの交点の最大数を求めよ。 解法 yに小数点をとることも可能な…

SRM587Div1Easy

問題 十分に長い階段を考える。整数NとbadStepが与えられた時にN回の操作で、到達できる最大の高さを求めよ。 許される操作は、i回目の操作の時に、i個分の段差を飛び越えるかそのまま動かないかのどちらかである。ただし、badStepの高さに行くことはできな…

SRM588Div1Easy

問題 N個の曲と時間Tが与えられる。各曲にはdurationとtoneが与えられており、T秒間だけ曲を流すことができる。durationは曲の長さを秒で示す。現在の曲がtone[i]で次の曲がtone[j]だとすると、次の曲に移るのに|tone[i]-tone[j]|秒必要とする。 T秒間の間に…

SRM589Div1Easy

問題 サイズNの文字列が与えられる。与えられた文字列を回文にするのに最小な時間を求めよ。 許される操作は、以下である。 任意の2つの文字A,Bを選択し。すべての文字AをBに変更する。この時、ひとつの文字を変更するのに1秒かかる。 解法 同じ文字と反対側…

SRM590Div1Easy

問題 サイズNの配列beginとtargetが与えられる。要素は'.','L','R'のいずれかである。'.'は空を示し、'L'は左に移動できる駒、'R'は右に移動できる駒を示す。 beginの状態からtargetの状態に遷移可能か求めよ。 解法 各要素の位置情報を比較することで、答え…

SRM571Div1Easy

問題 N個の曲が与えられ、各曲の名前はN+".mp3"となっている。辞書順に並べ、はじめのmin(50, N)個の要素を求めよ。 解法 はじめに桁を上げていき、その後は数字を1ずつあげていく。 計算量 コード

SRM573Div1Easy

問題 サイズNの配列が与えられる。Nは3の倍数である。プログラミングコンテストを考える。各要素はプログラマの実力を示し、はじめの3要素X,Y,Zが自身のチームメンバーである。チームの能力はmax(X,Y,Z)+min(X,Y,Z)で求まる。この能力より真に大きいチームは…

SRM657Div1Easy

問題 SRMのようにEasy, Medium, Hardの3つでひとつである問題セットを考える。E,M,HはそれぞれEasy, Medium, Hardの問題であり、EMはEasyにもMediumなれる問題であり、MHはMediumにもHardにもなれる問題である。 E,M,H,EM,MHの数が与えられた時の問題セット…

SRM659Div1Easy

問題 N個のフルーツが並んでおり、それらはりんごかオレンジである。K個の連続するフルーツは最大でもK/2個のりんごしかない。 いくつかのりんごの位置の配列が与えられた時の最大のりんごの数を求めよ。 解法 左側の要素から探索していき、周囲K個のりんご…

SRM658Div1Easy

問題 サイズN*Nの配列xが与えられる。サイズNのツリーを考え、配列の各要素はx[i][j]はiからjまでの距離が偶数か奇数かを示している。与えられた配列の条件を満たすツリーを求めよ。 解法 TopCoder SRM 658 Div1 Easy OddEvenTree - kmjp's blogkmjp.hatenab…

SRM591Div1Easy

問題 ルートからの距離がxであるノードを個持つツリーを考える。この時のツリーの直径を求めよ。 解法 各ノードをルートとした時の子であるノードの中で深さが最大となる2つを選ぶ。これを全てのノードに対して行うことで答えが求まる。 最初に与えられたツ…

SRM592Div1Easy

問題 サイズNの文字列が与えられる。各要素はR,G,Bのどれかである。何もない文字列から始め、一文字ずつ文字を加え与えられた文字列にする時の最高のスコアを求めよ。 スコアは以下のように追加される。 初めの要素の場合は0ポイント 文字列の端に追加した場…

SRM593Div1Easy

問題 N*Nの配列が与られる。各マスは六面体となっており、要素はXか-である。Xの箇所を任意の色で塗りたい。ただし、隣り合うマスでは違う色とする。この時に必要な色の最小数を求めよ。 解法 3色あればどんな場合でも塗ることができる。なので、0、1、2のど…

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

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

コード

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 解法 目的地を固定し、ダイクストラで最短経路を計算する。カメの距離、ウサギの距離がとなる点の数を二分探索で計算する。 計算量…