Hatena::Grouptopcoder

hotpepsiの練習帳

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

2017-01-18

Facebook Hacker Cup 2017 Round 1

23:23

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

A. Pie Progress (10pt)

問題

  • パイを売る店がある
  • 一日にM個のパイが売りに出される
  • それぞれの価格が与えられる
  • 毎日パイを1つずつ食べられるように買う
  • まとめ買いしてもよいが、一日にX個買うと、X^2の金額が税として足される
  • コストの最小値を求める

方針

C. Manic Moving (25pt)

  • Wilsonは引っ越し屋をしている
  • N個の街があり、M本の道路で結ばれている
  • Aiと町Biに移動するのにガソリンをGi消費する
  • Kの家族が街Siから町Diへ引っ越しをする
  • トラックには2家族ぶんまで荷物が積める
  • 順番が先の家族の荷物を先に積み込む必要がある
  • 順番が先の家族の荷物を先に届ける必要がある
  • ガソリンの消費量の最小値を求める

方針

  • 考察
    • まず最短経路を求めておく(全頂点についてダイクストラ)
    • DP
    • 状態として、(A)何も積み込んでいない状態、(B)家族kの荷物を積み込んで、家族kの出発地にいる状態、(C)家族kと家族k+1の荷物を積み込んだ状態がある
    • (A)から(B)へ、(B)からは(A)か(C)へ遷移できる
    • (C)のときは、先に積み込んだ家族の目的地へ行く必要があり、分岐はないので、(B')家族kの荷物を積み込んで、家族kの目的地にいる状態、まで遷移させて考えてよい
  • 解法
    • あるターンの処理は次の通り
    • 前のターンの(B)か(B')の状態から、(C)を経て(B')に遷移できる
    • (A)にいれば(B)に遷移できる
    • (B)か(B')から次のターンの(A)に遷移できる
  • Passed System Test
  • https://github.com/firewood/topcoder/blob/master/fhc_2017/R1_C.cpp

D. Beach Umbrellas (40pt)

問題

  • ビーチにN本のパラソルを広げる
  • パラソルを固定する穴が等間隔にM個空いている
  • 各パラソルの半径はRiである
  • パラソルがぶつからないように配置するとき、配置の仕方が何通りあるか求める

方針

  • 考察
    • 端のことを考えると、端に置くものによって、端以外の余白が変わる
    • 端を固定して、余白が何通りかを求めて、全ての端のパターンを列挙すればできそう
    • 端以外に使える長さCは、(M-1-端に置くものの半径)
    • Riの合計の2倍が、C以下なら配置できる
    • 余白を配置する場合の数は、重複組合せ
    • Cに配置するのは(N-2)!通り
  • 提出
  • Time Expired
  • nCrを毎回計算するのが遅すぎた
  • rは小さいのでメモ化すればよい
  • https://github.com/firewood/topcoder/blob/master/fhc_2017/R1_D.cpp

結果

o-o- 35pt

なんとか通過した。

pie chartの次はパイ屋さんときた。予選の問題のアップグレードになっていて、今年は問題文が面白い。

CはN=5000のワーシャルフロイドは間に合わなさそうだと思ったらN<=100だった...

editorial:

https://www.facebook.com/notes/facebook-hacker-cup/hacker-cup-2017-round-1-solutions/1599716033377625


https://togetter.com/li/1070628

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

2017-01-14

SRM 705

21:37

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

Div1 Easy (225) AlphabetOrderDiv1

問題

  • aからzまで26種類の文字を使う言語がある
  • 便宜的にaからzで表すが、各文字の序列は不明である
  • ある単語の文字が、文字の序列順になっているものを、良い単語とする
  • N個の単語が与えられる
  • 全ての単語が良い単語になるような文字セットが存在するかどうかを求める

方針

  • 各文字の大小関係を記録していき、矛盾が生じたらImpossibleとする
  • 文字pが文字qより前にあり、文字qが文字rより前にあるとき、文字pは文字rより前になければならない、という判定をがんばる
  • Challenge Succeeded
  • 同じ文字が連続するときの判定が抜けていた
  • (解き直し)
  • 考察
    • hama_duさんに聞く
    • グラフで
    • 文字p、文字qの順に出現したとき、文字pからqへ辺を張る
    • ただし同じ文字が連続するときは無視する
    • あとで全部たどるので、辺を張るのは前後の文字だけでよい
    • 辺をたどって、ループしているときはImpossible
    • ループするときには同じ文字に到達する
  • 解法
    • 一つ前の文字に(片方向の)辺を張る
    • Warshall-Floydをかけて、自分自身に戻ってくる文字があるかどうかを判定
  • https://github.com/firewood/topcoder/blob/master/srm_7xx/srm_705/AlphabetOrderDiv1.cpp
  • 別解として、トポロジカルソートして、ループが残るかどうかで判定してもよい

Div1 Medium (450) MovingTokens

問題

  • N個の容器があり、それぞれに駒が入っている
  • 駒の行先を示す表M[i][j]がある
  • 各ターンにiをひとつ選ぶ
  • 容器jに駒が入っていれば、それをM[i][j]に移動する
  • 移動は同時に行う
  • 駒が入っている容器の数を最小化するとき、10^100ターン後の容器の数を求める

方針

  • 合流と移動がある
  • 合流はunion findで同じと見なす
  • 合流しているもののどちらかに移動するものがあれば、それも合流と見なす
  • サンプル通ったので提出
  • Challenge Succeeded
  • (解き直し)
  • Codeforcesのフォーラムを読む
  • 2つの容器が合流するかどうかをDFSで見つけて、合流するときは、その手順を覚えておく
  • 容器の初期状態を1として、任意の2つの容器のうち、合流するものがなくなるまでループする
  • https://github.com/firewood/topcoder/blob/master/srm_7xx/srm_705/MovingTokens.cpp

結果

xx- +1 50pt 141st/262 rating 1414 -> 1434 (+20)

clock()で1.7秒までがんばるコードが落とされていた。アリーナではclock()やtimes()は常に0を返すようだ。sleepもsleepせずにすぐに戻ってくる。

gettimeofday()またはRDTSC(インラインアセンブラ)は使えた。

mediumは、交換か減るかしかないので、貪欲的にやってよい模様。


https://togetter.com/li/1069702

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