Hatena::Grouptopcoder

hotpepsiの練習帳

2017-04-09

SRM 711

00:06

Div1 Easy (250) ConsecutiveOnes

問題

  • N以上で、2進数表記で1がK個連続する最小の数を求める

方針

  • 1がK個連続している数(1 <<K - 1)をXとする</li>
  • XとNの上から1ビットずつ見ていく
  • Nが1ならXにも1を立てる(=N以上にする)
  • Nが0でXが1なら、Xのほうが大きいので終了し、仮の答えとする
  • Xの初期値を1ビットずらして(2倍にして)全て試す
  • 仮の答えのうち最小のものが答え
  • Passed System Test
  • https://github.com/firewood/topcoder/blob/master/srm_7xx/srm_711/ConsecutiveOnes.cpp

結果

o-- +1 194.73 +50 = 244.73pt rating 1649 -> 1686 (+37)

とーらすさん記念の回。

方針が単純なのが良かった。無限ループする解を落として+1


https://togetter.com/li/1094091

トラックバック - http://topcoder.g.hatena.ne.jp/firewood/20170409

2017-04-06

SRM 710

23:51

Div1 Easy (300) ReverseMancala

問題

  • マンカラはコマを穴から穴へと動かして遊ぶゲームである。ここではコマを石、穴をスロットとする
  • N個のスロットがあり、円環状に並んでいる
  • ゲームは1ターンずつ進行する
  • 操作Aまたは操作Bのいずれかの操作が可能である
  • 操作Aは、まずひとつ以上の石が入ったスロットを選び、石を全て手に移す
  • 次に、時計回りで隣にあるスロットに、石をひとつずつ置いていく
  • 石がなくなったら終了
  • 操作Bは、まず石が一つ以上存在するスロットを選ぶ
  • 次に、反時計回りで、石をひとつずつ取っていく
  • スロットに石が入っていなかったら、そこに手持ちの石をすべて置いて終了
  • 状態startとtargetが与えられる
  • startからtargetにするための手順を求める

方針

  • 何となく均等にできそう
  • いろいろやってみるが終了
  • (終了後)
  • ある場所X以外からAの操作をひたすら実行すると、X一箇所に集めることができる
  • Bの操作はAの逆である
  • targetからXに集める操作を求めておいて、逆順にBを実行するとXからtargetにできる
  • startからXに集める操作とくっつけて完成
  • 逆順にするときはindexの値が最後に置いた場所になるので、そこを何とかする
  • https://github.com/firewood/topcoder/blob/master/srm_7xx/srm_710/ReverseMancala.cpp

結果

--- 0pt 42nd/226 rating 1683 -> 1649 (-34)

部屋で誰も提出できなかった珍しい回。連続プラス点が7回で終わってしまった。

マンカラは実在のゲームだったらしい。


https://togetter.com/li/1088982

トラックバック - http://topcoder.g.hatena.ne.jp/firewood/20170406

2017-04-02

SRM 709

00:36

Div1 Easy (250) Xscoregame

問題

  • 配列Aが与えられる
  • Aの各要素Yを任意の順番で選ぶ
  • Xの初期値を0としてX=(X+(X XOR Y))を計算する
  • Xの最大値を求める

方針

結果

x-- +3 150pt 102nd/339 rating 1637 -> 1683 (+46)

違いが出る部分だけでDPするのはなるほどという感じ。


https://togetter.com/li/1083628

トラックバック - http://topcoder.g.hatena.ne.jp/firewood/20170402

2017-03-08

Codeforces #398 (Div. 2)

00:13

A. Snacktower

問題

  • 1からNまでの大きさのN個のスナックが順不同で落ちてくる
  • 大きいものの上にそれより小さいものが置ける
  • 1つずつ落ちてきたものを手戻りしないように置くとき、どれを置くかを求める

方針

B. The Queue

問題

  • パスポートを発行してもらいに旅券課に行く
  • 受付には1人だけいて、真夜中からS分後から業務を開始し、F分間だけ窓口業務を行う
  • 一人あたりT分かかる
  • 終了までの残り時間がT分未満のときは受けつけない
  • 自分以外にN人が窓口に並ぶ
  • 各人の到着時刻が与えられ、時刻はすべて異なる
  • 自分と同時に到着したときは自分でない人の方が先になる
  • 必ず受け付けてもらい、かつ、待ち時間を最小にするために、何分後に並ぶ必要があるかを求める

方針

  • 仮の到着時刻をWとする
  • 次の人が受け付けてもらえる時刻をXとして、初期値をSとしてXを更新していく
  • N人を一人ずつ見ていく
  • 次の人Aが、Xよりもあとに来るならば、並ばなくて良いので、時刻Xが答え
  • そうでなければ、Aの直前に来るのが候補(ただし、Xが受け付けてもらえる時刻であること)
  • その場合、(X-(A-1))だけ待つことになる
  • Wよりも待たないのなら、Wを更新する
  • N人処理した結果、Xがまだ受け付けてもらえる時刻なら、Xが答え
  • https://github.com/firewood/topcoder/blob/master/codeforces_3xx/cf_398/b.cpp

結果

ox--- 278pt 2524th/7223 rating 1716 -> 1621 (-95)

最後の場合分けが足りていなくて死んだ。ABともそんなに簡単ではなかった。


https://togetter.com/li/1082440

トラックバック - http://topcoder.g.hatena.ne.jp/firewood/20170308

2017-02-14

SRM 708

23:30

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

Div1 Easy (250) BalancedStrings

問題

  • 文字列中の隣り合う2文字が異なる個数を、文字列のinstabilityとする
  • 文字列の配列のinstabilityは、各文字列のinstabilityの合計値とする
  • 二つの文字列s1,s2について、s1の各文字s1[i]とs2の各文字s2[j]が同じである個数を文字列のsimilarityとする
  • 文字列の配列のsimilarityは、配列の全ての2要素の組み合わせのsimilarityの合計値とする
  • 数Nが与えられる
  • instabilityとsimilarityが等しくなるよう、要素数がNの文字列の配列を構築せよ
  • ただし各文字列は100文字までとする

方針

結果

o-- +2 94.74+100=194.74pt 59th/331st rating 1536 -> 1637 (+101)

元embedded systems engineerなので埋め込んでもOKOK


https://togetter.com/li/1079618

トラックバック - http://topcoder.g.hatena.ne.jp/firewood/20170214