Hatena::Grouptopcoder

hotpepsiの練習帳

2016-01-03

SRM 655

| 17:18

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

https://competitiveprogramming.info/topcoder/srm/round/16415/div/2

Div1 Easy (250)

問題

  • Wで塗りつぶされた升目がある
  • K×Kの大きさ単位でBまたはWで塗りつぶす
  • 最終状態が与えられる
  • 初期状態から最終状態にできるかどうかを求める

方針

結果

--- 0pts 248th/564 rating 1504 -> 1459 (-45)

「どちらでもよい状態」を思いつけなかった。


http://togetter.com/li/806333

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

2014-05-14

TCO 2014 Round 1A

| 00:42

Easy (250) EllysSortingTrimmer

問題

  • 文字列を変更する装置がある
  • 先頭のN文字をそのまま、途中のL文字をソートして、末尾を削除できる
  • 何回でも適用できる
  • 適用結果のうちの辞書順最小のものを求める

方針

Medium (500) EllysScrabble

問題

  • 文字列と、移動可能な距離Dが与えられる
  • 各文字は、左右どちらか距離Dまで移動可能
  • 移動結果のうち辞書順最小を求める

方針

Hard (1000) EllysLamps

問題

  • N個のランプとボタンがある
  • 各ボタンはトグル動作し、押すとランプがON/OFFする
  • ただし、両隣の片方または両方のランプも同時にON/OFFするようなボタンが存在する可能性がある
  • ボタンの挙動がワーストケースの場合に、OFFにできないランプの最小値を求める

方針

  • YNまたはNYの数を数える
  • とサンプル4が合わない
  • スイッチがN個連動するという前提でDP書いてみたりとか
  • (終了後)
  • YYYと並んでいるとき、一つ目と二つ目が連動していて、二つ目と三つ目が連動しているとき、NNNにできないので、+1カウントする、ということらしい
  • https://github.com/firewood/topcoder/blob/master/tco_2014/EllysLamps.cpp

結果

oo- 238.44 + 386.42 = 624.86pts 331st/2205 rating 1513 -> 1578 (+65)

毎年の祭りその2到来。

比較的早く解けた。highest更新。


http://togetter.com/li/651699

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

2014-04-11

SRM 605

| 02:36

Div1 Easy (250) AlienAndHamburgers

問題

  • エイリアンのFredは地球を滅ぼす前にハンバーガーを食べておくことにした
  • 種類とおいしさの配列が与えられる
  • 満足度は種類の数×おいしさの合計である
  • 満足度の最大値を求める

方針

  • 貪欲っぽい
  • (種類,おいしさの降順)でソート
  • ひとつずつ見ていき、同じ種類かつおいしさが正ならまとめる
  • まとめたあと、おいしさでソート
  • おいしさが正なら必ず増加する
  • おいしさが負で、総量が増加しないなら、次のを食べても増加することはない
  • おいしい順に食べて、食べても増えないならやめる
  • Passed System Test
  • https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_605/AlienAndHamburgers.cpp

結果

o-- 180.04pt 303rd/658 rating 1228 -> 1294 (+66)

ちゃんと解けた。


http://togetter.com/li/618981

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

2014-03-23

SRM 601

| 22:22

Div1 Easy (250) WinterAndPresents

問題

  • りんごとみかんが入っている袋がいくつかある
  • それぞれの袋からX個取り出す
  • りんごとみかんの数の組み合わせが何通り可能かを求める

方針

Div2 Easy (250) WinterAndMandarins

問題

  • みかんの入った袋がある
  • K袋選ぶ
  • みかんが入っている個数の差の最小値を求める

方針

Div2 Medium (500) WinterAndCandies

問題

  • 何種類かのキャンディーがある
  • キャンディーの種類は正の整数
  • K個取り出す
  • 1からKまでの種類が揃うのは何通りか求める

方針

  • 同じ種類で別のキャンディーは別物として数えるっぽい
  • 種類ごとに配列cにカウントしておく
  • 3種類の場合c[1]×c[2]×c[3]通り
  • 全体としてはc[1]+c[1]×c[2]+c[1]×c[2]×c[3]...となる
  • 歯抜けになる場合は、途中のカウントがゼロになるので問題ない
  • K=1から足してかけて...としていく
  • https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_601/WinterAndCandies.cpp

結果

o-- 118.42pt 513rd/767 rating 1297 -> 1298 (+1)

提出したときは、最初にXの最大値を求めた。条件を分離するのは悪くないけどタイプ数としては無駄だった。あとK=0から足してつじつまが合わなくなり最後に1ひいてださかった。

冬はこたつみかんですね。


http://togetter.com/li/605805

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

2014-03-16

SRM 600

| 01:10

Div1 Easy (250) ORSolitaire

問題

  • 数値の配列が与えられる
  • 初期値を0として、配列の要素をORしてgoalにする
  • 要素をいくつ削除したらgoalにできなくなるかを求める

方針

Div2 Easy (250) TheShuttles

問題

  • N箇所の拠点と、それぞれの社員数が与えられる
  • それぞれの拠点について、全員を運べる台数を用意する
  • 全てのシャトルの座席数は同じである
  • シャトル1台のコストはbaseCost+seatCost×座席数である
  • コストの最小値を求める

方針

結果

x-- 0pt 889th/1007 rating 1420 -> 1297 (-123)

ビットのループを、小ネタで

for (int b = 1; b > 0; b *= 2)

と書いたらTLEで死んだ。

Visual C++では停止するが、GCCだと条件が常に真と見なされて無限ループになっていた。

条件は色々あるようだ。

https://twitter.com/hirose_golf/status/435034777968603136

for(int i = 715827882; i >= 0; i *= 3)は無限ループするが

for(int i = 715827883; i >= 0; i *= 3)は無限ループしなかったり。

C言語むずかしい。


http://togetter.com/li/602581

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