Hatena::Grouptopcoder

hotpepsiの練習帳

2017-08-27

TCO17 Algorithm Round 1A

13:37

Easy (250) PingPongQueue

問題

  • 何人かで卓球をする
  • 一列に並び、2人ずつ対戦する
  • 各自の実力が配列skillsで与えられる
  • 実力が高い方が必ず勝つ
  • 負けるか、連続でN回勝ったら列の最後に並ぶ
  • Kゲーム目の対戦カードを求める

方針

  • シミュレーション
  • Passed System Test

https://github.com/firewood/topcoder/blob/master/tco_2017/PingPongQueue.cpp

Medium (500) CheeseSlicing

問題

  • A×B×Cの大きさのチーズを切る
  • どれかの面に平行に切る必要がある
  • 切断後の長さが整数の値であること
  • 3辺のうちいちばん小さい値を厚みとする
  • 残りの辺の積をチーズの面積とする
  • 厚みがS以上の塊に切るとき、面積の合計の最大値を求める

方針

  • 3辺それぞれの切り方をDFSで全部試す
  • メモ化
  • Passed System Test

https://github.com/firewood/topcoder/blob/master/tco_2017/CheeseSlicing.cpp

結果

216.52 + 311.48 = 528.00pt 233rd/886 1686 -> 1676 (-10)

easyは「連続で」が抜けてたり、意外とchallengeの余地あったらしい。


https://togetter.com/li/1096655

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

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