2017-03-08
Codeforces #398 (Div. 2)
A. Snacktower
問題
- 1からNまでの大きさのN個のスナックが順不同で落ちてくる
- 大きいものの上にそれより小さいものが置ける
- 1つずつ落ちてきたものを手戻りしないように置くとき、どれを置くかを求める
方針
- いちばん大きくてまだ置いていないものを覚えておき、そこに降ってきたら連続しているものを埋める
- https://github.com/firewood/topcoder/blob/master/codeforces_3xx/cf_398/a.cpp
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://topcoder-g-hatena-ne-jp.jag-icpc.org/firewood/20170308
2017-02-14
SRM 708
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文字までとする
方針
- similarityは増えやすい
- なのでababab...みたいなのでinstabilityを稼ぎ、残りをe,f,g,h,...のように1文字だけで埋める
- 適当に作って減らすようにしたら効率的に作れなかったので、1から100まで全部力技で作り、埋め込み
- Passed System Test
- https://github.com/firewood/topcoder/blob/master/srm_7xx/srm_708/BalancedStrings.cpp
結果
o-- +2 94.74+100=194.74pt 59th/331st rating 1536 -> 1637 (+101)
元embedded systems engineerなので埋め込んでもOKOK
トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/firewood/20170214
2017-02-13
SRM 707
https://competitiveprogramming.info/topcoder/srm/round/16851/div/1
Div1 Easy (250) MazeConstruct
問題
- N×Mマスの盤面がある
- 左上から右下までの最短距離がちょうどKステップとなるように障害物を配置せよ
方針
- ジグザグに降りてくればよさそう
- 最初に右端に行くのを1つずつ削ることで、2歩単位で減らすことができる
- 最後に1段追加することで1歩増やすことができる
- 調整する数が少なくなるようなW,Hを見つける
- Passed System Test
- https://github.com/firewood/topcoder/blob/master/srm_7xx/srm_707/MazeConstruct.cpp
結果
o-- +1 62th/236 75.00+50=125.00ps rating 1454 -> 1536 (+82)
#と.を逆にして提出するという間抜けなことをしてしまったが1challengeのおかげで助かった。
たぶんローグだと通路が#なので#で作ってしまった気がする。
トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/firewood/20170213
2017-02-11
Facebook Hacker Cup 2017 Round 2
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://topcoder-g-hatena-ne-jp.jag-icpc.org/firewood/20170211
2017-02-05
SRM 706
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://topcoder-g-hatena-ne-jp.jag-icpc.org/firewood/20170205