Hatena::Grouptopcoder

hotpepsiの練習帳

2018-03-20

Google Code Jam 2017 Qualification Round

00:31

https://code.google.com/codejam/contest/3264486/dashboard

Problem A. Oversized Pancake Flipper

問題

  • N個のパンケーキがある
  • パンケーキの表裏の向きが与えられる
  • 連続したK個を裏返せる
  • 裏返す総回数を求める

方針

Problem B. Tidy Numbers

問題

  • 数の各桁が非減少なものをtidy numberとする
  • 数Nまでの範囲の最後のtidy numberを求めよ

方針

Problem C. Bathroom Stalls

問題

  • N個のマス目があり、初期状態では全てのマス目が空いている
  • 最も連続で空いているマス目の中央を埋める
  • ひとつずつ、K個のマス目を埋める
  • 埋まっているマス目について、左側の連続する空きマスの個数の最小値と、右側の連続する空きマスの個数の最小値を求めよ

方針

Problem D. Fashion Show

要復習

結果

がんばって7言語で書いたが、よくわからないやつはC++で解いてから書き直しているので、効率が良くない。ちゃんとその言語にあった書き方ができるようにしたい。

Cはkmjpさんの読んで、mapでメモ化するのはわかりやすかった。しかしこういうのを関数型言語で書ける気がしない。

トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/firewood/20180320

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

トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/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

トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/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

トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/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

トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/firewood/20170402