きままにものづくり

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

SRM641Div1Medium

問題

サイズ2Nの配列が与えられる。サイズ2Nの昇順にソートされている配列から、与えれた配列に変更するための最小な操作数を求めよ。以下の操作を1とする。

  • 先頭のN個と次のN個に分け、前者を集合A、後者を集合Bとする。
  • Aの要素とBの要素を交互に繰り返し、2Nの配列を作成する。

解法

与えられた配列の奇数要素と偶数要素を調べることで、以前の集合Aと集合Bが求まる。その集合を得るための操作回数を調べることで、答えが求まる。Nが奇数の場合は、ソートされている配列のBの要素を全てAの集合に移すのに2回の操作が必要になるが、Nが偶数の場合は、一回の操作で十分である。

計算量

O(N)
ソート: O(N log N)
ソートをしなくても、解ける。

コード

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を求めよ。

解法

Bobは、 1 \leq f(x) \leq Nとなる順列を選ぶことができる。よって、Bobがどんな順列を選んできてもf(x)=1となるxは、1~Nの最小公倍数と等しくなる。そのまま、計算すると大きい値になってしまうので因数の数を保持することで最小公倍数を求める。

計算量

O(N \sqrt{N})

コード

SRM651Div1Easy

問題

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

  • 移動した先が空白だった場合は、そのマスに移動する
  • 移動した先が障害物だった場合は、移動しない
  • 移動した先が境界の外だった場合は、壊れてしまう

ロボットが壊れないコマンドの最長の長さを求めよ。
長さが固定されない場合は-1を返す。

解法

ロボットの上下左右の直線上に障害物がある場合は-1を返す。
それ以外の場合は、ロボットの上下左右のマージンを全て足し合わせると答えになる。

計算量

O(WH)
W:平面の幅
H:平面の高さ

コード

SRM650Div1Easy

問題

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

解法

与えれた文字とその間の文字数で答えが求まる。
以下のような例を考える。
A**B
この場合は、
ABAB
と一意に決まる。
一方、
A**Aの場合は、
ABAA
ABAA
ABBA
の3つになる。
A****Aの場合は、
AB**BA
ABABAA
AABABA
となる。
このように、再帰でパターン数が求められる。
より注目していくと、常に*の数+1となる。

すべての間隔に対して上のパターンを求め、かけることで答えが求まる。

計算量

O(M log M)

コード

SRM649Div1Easy

問題

サイズNの文字列が与えられる。その中からK個の文字を消した際に、消した文字とその場所が特定できるか判別せよ。

解法

K個の文字を消した後に得られる文字列が重複している場合、特定が不可能になる。ある要素からK個以内の範囲に同じ文字が存在すれば、同じ文字列が得られるので特定が不可能になる。

計算量

O(N)

コード

SRM648Div1Easy

問題

以下の性質を満たす文字列Sを求めよ。

  • 要素はAかB
  • サイズはN個
  • S[i]=A, S[j]=B ( 0 \leq i < j < N) となるペアがK個

解法

Aの数をa、Bの数をBとし、a*b+c=Kとなるようにa,b,cを求める。c(=K-a*b)はAを左から詰めた時に、一番右のAをどれだけ右にずらすかを示す値である。

計算量

O(N)

コード

SRM640Div1Medium

問題

サイズがN1とN2の二部グラフが与えられる。グラフが以下の条件を満たす時のエッジの最大値を求めよ。

  • マッチングの値がc
  • 各頂点の次数がd以上

解法

問題の条件を満たす時のエッジの数を方程式で表現し、それの最大値を計算することで答えが求まる。
N1とN2で大きい方の値をa、小さい方の値をbとする。
a = max(N1,N2)
b = min(N1,N2)

エッジの数をf(v)で表現する。
まず、bのグラフの中からv個の頂点を選び、aの全ての頂点にエッジを張る。
次に、選ばなかった(b-v)個の頂点から、aの中のc-v個の頂点にエッジを張る。
この時のエッジの数は以下の式で表される。また、この時のマッチングはcとなる。
f(v) = av + (b-v)*(c-v)
この式を展開する。
f(v) = v^2 + (a-b-c)v + bc
式の形より、下に凸な2次関数であることがわかる。
よって、エッジの最大値はvの最大値もしくは、最小値の時のf(v)となる。
vの最小値は0である。
vの最大値を考える。
問題の条件により、各頂点の字数はd以上でなければならない。よって、(c-v)はd以上となる。
c-v \leq d
この不等式により、vの最大値はc-dとなる。
f(0)とf(c-d)を計算し、大きい方が答えとなる。

計算量

O(1)

コード