hotpepsiの練習帳

SRM 699

13:59

https://competitiveprogramming.info/topcoder/srm/round/16803/div/1

Div1 Easy (250) OthersXor

問題

• N匹の狼がいる
• それぞれの狼は0から2^30-1までの任意の数値を選ぶ
• それぞれの狼は、情報を開示しないか、あるいは、自分以外の全ての狼の数値のXORを開示する
• 開示された情報が正しい場合、狼の数値の合計の最小値を求める
• 開示された情報に一貫性がない場合は-1とする

方針

• (終了後)
• いろいろな方々の解説を読む
• ビット毎に独立して考えていい
• 非開示のものは任意として扱えるので除外して考える
• 元の値をW[i]、XORの値をX[i]、W[i]の全てのXORの値をSとする
• X[i]==0の個数をC0、X[i]==1の個数をC1とする
• Xの全てのXORは、全ての値をN-1回XORした値と等しいので、Sになる
• W[i]^X[i]==Sなので、W[i]==W[j]ならX[i]==X[j]
• つまりW[i]==0の個数はC0かC1、W[i]==1の個数はC1かC0 (Wの全ビットを反転すると個数が逆転する)
• Sが0になるときと1になるときで場合分け
• Sが0のとき
  • Wについて、0の個数は何個でもいいが、1の個数は偶数であること
  • W[i]==1のX[i]は、自分以外の1は奇数なので、1になる
  • C1が偶数になり、これが必要条件
• Sが1のとき
  • Wについて、0の個数は何個でもいいが、1の個数が奇数であること
  • W[i]==1のX[i]は0になる
  • C0が奇数になり、これが必要条件
• C1が偶数のとき
  • C1を1の個数と仮定できる
• C1が奇数で、非開示が1個以上あるとき
  • C1+1を1の個数と仮定できる
• C0が奇数のとき
  • C0を1の個数と仮定できる
• C0が偶数で、非開示が1個以上あるとき
  • C0+1を1の個数と仮定できる
• 1の個数の条件を満たさなければ一貫性がない
• 1の個数は複数の可能性があるが、最小のものを採用する
• 1の個数×ビットマスクの値が、そのビットの合計の最小値
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_699/OthersXor.cpp

結果

--- 0pt

全体が満たすべき性質を考える必要があった。

https://togetter.com/li/1029558

SRM 698

00:01

https://competitiveprogramming.info/topcoder/srm/round/16802/div/1

Div1 Easy (250) RepeatString

問題

• 文字列が二つの文字列の繰り返しになっているとき、平方文字列と呼ぶ
• 1ターンで、1文字挿入、1文字変更、1文字削除、のいずれかの操作を行う
• 文字列sを平方文字列にするための最小ターン数を求める

方針

• 左側と右側にわけてDP (左側の長さを全て試す)
• Failed System Test
• 編集距離のライブラリを貼ればいいらしい
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_698/RepeatString.cpp

結果

x-- +1 50pt 280th/431 rating 1582 -> 1533 (-49)

DP力が少し足りなかった。

https://togetter.com/li/1025727

SRM 697

23:20

https://competitiveprogramming.info/topcoder/srm/round/16776/div/1

Div1 Easy (300) DivisibleSetDiv1

問題

• N個の正の整数からなる配列bが与えられる
• 以下の条件を全て満たす配列aが存在するかどうかを求める
• aの要素a[0],a[1],...a[N-1]は全て異なる
• 各要素は1以上の整数
• a[i]^b[i]は、a[i]以外の全てのaの要素の積で割り切れる

方針

• ぜんぜんわからず
• (終了後)
• hamayanhamayanさんの解説を読む
• 2の累乗だけで考える
• 2^(a[i] * b[i])が2^p[i]で割り切れることが必要
• a[i] * b[i]がp[i]以上であること
• 両辺にa[i]を足してみる
• a[i] * (b[i] + 1)がaの総和以上なら条件を満たす
• 各a[i]について、aの総和未満なら1を足してみる
• aを1〜Nに仮設定して、条件を満たすまで100万回くらい試せばわかる
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_697/DivisibleSetDiv1.cpp

結果

--- +1 50pt 80th/319 rating 1523 -> 1582 (+59)

復習したらなるほどという感じだった。

https://togetter.com/li/1013630

SRM 696

09:51

https://competitiveprogramming.info/topcoder/srm/round/16775/div/1

Div1 Easy (300) Gperm

問題

• 50個の頂点がある
• 1ターンに1つずつ塗っていく
• 20本以内でM本の辺が与えられる
• 辺の両辺が塗られているとき、1ターンごとにコストが1発生する
• コストの総量の最小値を求める

方針

• わからないので適当に貪欲で書く
• Failed System Test
• (終了後)
• kmjpさんの解説を読む
• 辺が全て張ってある状態から、取り除いていく
• 各頂点に含まれる辺をbitで持っておく
• 片方の頂点が取り除かれればその辺のスコアが加算されなくなる
• 取り除かれていない=0、取り除かれた=1として0から(1<<M)-1までbitDP</li>
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_696/Gperm.cpp

結果

x-- 0pt 64th/241 rating 1548 -> 1523 (-25)

最終形から取り除いていくのは典型っぽいが手が出なかった。

https://togetter.com/li/1010695

SRM 695

19:39

https://competitiveprogramming.info/topcoder/srm/round/16767/div/1

Div1 Easy (300) BearPasswordLexic

問題

• 文字aまたはbだけからなるN文字のパスワードSを作る
• Sの同じ文字が連続する部分(aが連続、またはbが連続)を取り出したものを部分文字列とする
• 異なる位置からはじまる部分文字列は異なるものとする
• 長さがi+1の部分文字列の個数が配列x[i]として与えられる
• 条件を満たす文字列のうち辞書順最小のものを求める

方針

• まず構築できるかどうかについて考える
• 長さXの部分文字列が1つあると、その部分には長さX-1の部分文字列が2つある
• 一番長いものから調べていき、短い部分文字列から、長いものによる個数を減らしていき、ちょうどその長さのものがいくつあるか求める
• 途中で個数が負になったりしたら構築不能
• 長さの合計がNにならなかったら構築不能
• 長さの配列が求まったら、構築していく
• aが連続＋bが連続＋aが連続...という形をしている
• 辞書順最小にするには、最初のaをなるべく長く、次のbをなるべく短く、というように構築する
• 残り個数が0になるまでaとbを交互に追加していく
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_695/BearPasswordLexic.cpp

o-- 138.96pt 138th/379 rating 1500 -> 1548 (+48)

300が普通に解けてなかなか良い感じだった。

http://togetter.com/li/1002027