hotpepsiの練習帳

SRM 703

22:04

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

Div1 Easy (250) DAGConstruction

問題

• N個の頂点と、それぞれの頂点が持つ値xが与えられる
• 以下の条件を満たす有向グラフを構築せよ
  • 閉路は存在しない
  • 任意の2頂点間の辺は高々1つ
  • 頂点iから到達可能な頂点の数はx[i]個

方針

• 葉は1
• x[i]==2は、葉につなげばよい
• x[i]==3だったら、2のものにつなぐか、2つの葉につなぐ
• 4だったら、それまでに出現した3つの頂点につなぐ
• x[i]が小さい頂点から処理していき、それまでに出現した頂点につなぐだけでよさそう
• それまでに出現した全ての頂点につないでも数が足りないときは不可能
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/srm_7xx/srm_703/DAGConstruction.cpp

結果

o-- 120.72pt 122nd/209 rating 1348 -> 1370 (+22)

大きな頂点につないだ結果、オーバーするかどうかの判定を入れて再提出したのだが、不要だった。

最初に出現したものからひとつずつつないでいくが、子の頂点を持つ頂点を追加する場合も、それらの子の頂点はすでに追加済で、ひとつずつしか増えないので、オーバーしない。

https://togetter.com/li/1059299

SRM 702

17:32

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

Div1 Easy (300) GridSortMax

問題

• N行M列の升目がある
• 1行目の1列目に1,2,3,...、2行目にM+1,M+2,M+3,...と番号をつける
• N行M列に並んだ数値が与えられる
• 各升目の数値と番号が一致するときを1、そうでないときを0とする
• それら一致したかどうかの値をすべて結合したものを類似性文字列とする
• 任意の行または任意の列が交換できるとき、辞書順最大の類似性文字列を求める

方針

• 左上から貪欲にソートして確定していけばいい
• Challenge Succeeded
• https://github.com/firewood/topcoder/blob/master/srm_7xx/srm_702/GridSortMax.cpp

結果

x-- 0pt 138th/206 rating 1416 -> 1348 (-68)

固定バッファのサイズが小さいという間抜けなバグで死んでしまった。

実装が少し面倒だけど、300点にしては方針に悩む部分がなかった。

https://togetter.com/li/1048713

SRM 701

21:41

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

Div1 Easy (300) PartisanGame

問題

• N個の石の山から、二人のプレーヤーが交互に石を取っていくゲーム
• 各プレーヤーには、取ることができる石の個数の配列が与えられる
• 1ターンにおいて、プレーヤーは、許可された個数だけ石を取ることができる
• 石を取れない場合は負け
• 勝つのが先手か後手かを求める

方針

• 法則が謎なので、とりあえず全探索して試す
• どうも周期性があるっぽい
• 残り0～1000個のときの結果を求めておく
• あるTについて、2周目(T+1～T×2)と3周目(T×2+1～T×3)の結果が同じなら、周期はTターン
• Nが大きいときは、N <- (N % T) + Tとする
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/srm_7xx/srm_701/PartisanGame.cpp

結果

o-- 136.90pt 119th/360 rating 1317 -> 1416 (+99)

周期性の理由はわからなかったけど結果オーライ

https://togetter.com/li/1041241

SRM 700

22:04

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

Div1 Easy (300) FindingFriend

問題

• 友人がプログラミングコンテストに参加している
• 部屋がroomCount個あり、各部屋にはそれぞれroomSize人が割り当てられる
• 各部屋の一位の順位leadersと、友人の順位friendPlaceが与えられる
• 友人が割り当てられた可能性のある部屋の総数を求める

方針

• leadersのどれかに含まれていれば1で終了
• ある部屋Tに配置できる可能性があるかどうかを求める。
• 順位の高い(小さい)順にroomSize人ずつ詰めていく
• friendPlace人まで詰めたが、まだTでない場合、友人を飛ばして、次の人を詰める
• 最後まで詰めることができればOK
• 全ての部屋について調べる
• Failed System Test
• Ekaingさんの解説を読む
• friendPlaceより前の部分がきっちり詰まっているときは、そこには詰められない
• 余裕がある部屋の数をansとして数えていく
• 順位の高い(小さい)順にroomSize人ずつ詰める
• きっちり詰まっている場合、余裕がないとしてansをリセットする
• friendPlaceまで来たらansが答え
• https://github.com/firewood/topcoder/blob/master/srm_7xx/srm_700/FindingFriend.cpp

結果

x-- -1 -25pt 239th/255 rating 1474 -> 1317 (-157)

友人を飛ばす・飛ばさないで場合分けしたりして複雑になってしまった。

https://togetter.com/li/1032595

2017年 競技プログラミングの目標

12:34

今年の目標

• SRM皆勤賞、rate 2000
• GCJ Tシャツ
• 蟻本の復習

去年

• SRM皆勤賞
  • 達成。去年はSRMが27回しかなくてあまり盛り上がってないが、何とか続いてほしい。
• 去年の分も復習エントリを埋める
  • だいたい達成。最近のSRMは難しいので時間がかかっている。
• GCJ Tシャツ (失敗)
  • 実力不足。多言語やってる場合ではなかった。
• マラソンに3回以上参加する (失敗、1回だけ参加)
  • ISUCONとピアノに時間を割いていたらマラソンまで手が回らなかった(言い訳)
• 蟻本の復習
  • 全く進まなかった。

今年は蟻本を復習して基礎力を上げようと思います。