2016-05-06
SRM 672
https://competitiveprogramming.info/topcoder/srm/round/16552/div/1
Div1 Easy (250) Procrastination
問題
- Hugeソフトウェアには無限の従業員がいる
- 従業員には2から連番の従業員番号がついている
- 最初、従業員xにはタスクxが割り当てられる
- 時間tに、2以上の整数Kについて、従業員K×tと従業員K×t+1がタスクを交換する
- 最終的にタスクNが割り当てられる従業員を求める
方針
- (終了後)
- 色々な解き方ができるっぽい
- sqrt(N)までは普通にシミュレーションして交換する
- sqrt(N)からは数が大きくなるので、y=sqrt(N)として、yを1ずつ減らしながら、N÷yをチェックしていく
- https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_672/Procrastination.cpp
結果
--- 0pt 168th/332 rating 1274 -> 1270 (-4)
従業員Xが最終的に割り当てられるタスクをYとすると、従業員YのタスクはXになるようだ。
なので、問題は「タスクNが割り当てられる従業員」だが、「従業員Nが最後に割り当てられるタスク」でも答えが同じになる。
(例: 従業員8はタスク11が割り当てられ、従業員11はタスク8が割り当てられる。)
2016-05-03
SRM 671
https://competitiveprogramming.info/topcoder/srm/round/16551/div/1
Div1 Easy (300) BearCries
問題
- 1個以上の泣きの顔文字;_;をネットワーク上に送信する
- アンダースコアは1つ以上なら何個でもよい
- 複数の顔文字が混ざって1つの文字列として送信される
- 1つの顔文字内の文字の順番は入れ替わらない
- 最終的に送信されるmessageが何通りに復元できるかを求める
方針
- (終了後)
- kojingharangさんのを写経
- dp[N文字目][開始;の個数][;_の個数]
- 1文字ずつ見ていき、;だったら開始;にするか;_を閉じる。閉じる場合、;_の個数だけ開始位置が存在する
- _だったら既存の;_につなげるか、開始;を;_にする。つなげる場合、どこにつなげるか個数分存在する。開始する場合も、どの;から開始するか個数分存在する。
- https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_671/BearCries.cpp
結果
--- 0pt 300th/556 rating 1295 -> 1274 (-21)
面白い問題。半年後には解き方忘れてそう。
2016-05-02
SRM 670
https://competitiveprogramming.info/topcoder/srm/round/16550/div/1
Div1 Easy (250) Bracket107
問題
- '('と')'だけからなる文字列がある
- それらのうち閉じ括弧が正しく対応している文字列Sがある
- 文字列Tが次の条件を満たすとき、Tの個数を求める
- Sと同じ長さ
- 閉じ括弧が正しく対応している
- Sとは異なる
- SとTの部分文字列の共通部分の長さが最大
方針
- (終了後)
- 全ての場所について、1文字を別の場所に移動して、括弧の対応が正しいものを数える
- S自身も含まれるので、-1したものが答え
- https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_670/Bracket107.cpp
結果
x-- 0pt 327th/589 rating 1322 -> 1295 (-27)
面白ツイートの回。めでたい。
agwさんがcompetitiveprogramming.infoにリンクしてくれるようになった。
2016-04-29
SRM 669
https://competitiveprogramming.info/topcoder/srm/round/16549/div/1
Div1 Easy (250) SubdividedSlimes
問題
- 大きさSのスライムがある
- 1ターンで任意のスライムを選び、大きさxとyの二つに分割する
- その際スコアx×yが得られる
- 合計スコアがKとなる最小のターン数を求める
方針
- 死
- (終了後)
- ターン数Tとするとき、T等分するのが最適らしい
- Tを小さい方から全部試して、条件を満たしたものが答え
- 分割後は、どの順番に合体させてもスコアは同じらしい(Div2 Medium)
- https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_669/SubdividedSlimes.cpp
結果
x-- 0pt 199th/463 rating 1330 -> 1322 (-8)
スコアは異なるのペアの積の和になり、積は差が小さい方が大きくなるので等分するのがベストということみたい。
2016-04-19
SRM 668
https://competitiveprogramming.info/topcoder/srm/round/16548/div/1
Div1 Easy (250) PaintTheRoom
問題
- R×Cの升目がある
- 1升ずつ移動して、全ての升目をちょうどK回通ることができるかどうかを求める
方針
- K=1なら行ける
- 偶数のときも行ける
- RかCが1のときはダメっぽい?
- 死
- (終了後)
- K=1かR×Cの偶奇だけでOK
- https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_668/PaintTheRoom.cpp
結果
xx- -1 -25pt 278th/338 rating 1429 -> 1330 (-99)
R=1のときの行きかたを思いつかなくて死んだ。手作業でDFSすればよかった?