Hatena::Grouptopcoder

hotpepsiの練習帳

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

2017-02-13

SRM 707

00:39

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

Div1 Easy (250) MazeConstruct

問題

  • N×Mマスの盤面がある
  • 左上から右下までの最短距離がちょうどKステップとなるように障害物を配置せよ

方針

結果

o-- +1 62th/236 75.00+50=125.00ps rating 1454 -> 1536 (+82)

#と.を逆にして提出するという間抜けなことをしてしまったが1challengeのおかげで助かった。

たぶんローグだと通路が#なので#で作ってしまった気がする。


https://togetter.com/li/1076293

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

2017-02-11

Facebook Hacker Cup 2017 Round 2

01:40

https://www.facebook.com/hackercup/round/742957399195355/

A. Subtle Sabotage (12pt)

問題

  • N×M個のマス目がある
  • 上下左右にだけ移動可能
  • 左上から右下に、最短距離で移動する
  • K×Kのお邪魔ブロックを置くことにより、最短距離をN+M-1以上にしたい
  • ただし到達可能であること
  • お邪魔ブロックの最小数を求める

方針

  • サンプルが割と親切
  • ただしKの大きさについての考察は必要
    • NとMの小さいほうをA,大きいほうをBとする
    • AがK以下だと完全にふさがれるので不可能
    • 始点と途中で曲がるところと終点の3つの経路が必要なので、Bが(K×2+3)より小さいと不可能
    • 最初に1つ並べてそれをよけさせて、下から縦にずらっと並べるパターン(サンプル2)
    • ベランダのようなでっぱりを作るパターン(サンプル3)
  • Passed System Test
  • https://github.com/firewood/topcoder/blob/master/fhc_2017/R2_A.cpp

-

結果

o--- 12pt 823th/1587

Tシャツ獲得ならず。


editorial:

https://www.facebook.com/notes/facebook-hacker-cup/hacker-cup-2017-round-2-solutions/1607098535972708


https://togetter.com/li/1073027

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

2017-02-05

SRM 706

12:56

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

Div1 Easy (250) MovingCandies

問題

  • 升目にいくつかキャンディーが置いてある
  • 左上から、キャンディーのあるところだけをたどって右下まで移動する
  • キャンディーを何個移動する必要があるかを求める

方針

  • 考察1
    • 変更量をコストとしてダイクストラ
    • サンプル1でコストが2と出てWA
    • キャンディーが足りないので、進む先にあるキャンディーも移動しているが、それを考慮していないため
  • 考察2
    • memo[もともとキャンディーだった場所を踏んだ数][y][x]=変更量でDFS
    • もともとキャンディーだった場所+変更量が、全体のキャンディーの数以下のところに行ける
  • Passed System Test
  • https://github.com/firewood/topcoder/blob/master/srm_7xx/srm_706/MovingCandies.cpp

結果

o-- 91.69pt 204th/384 rating 1434 -> 1454 (+20)

方針が間違っていて一時間以上かかった。再提出しないで通ったのは良かった。


https://togetter.com/li/1072968

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