hotpepsiの練習帳

SRM 625

23:03

Div1 Easy (250) PalindromePermutations

問題

• 文字列が与えられる
• 文字列をランダムに並べ替えて、左右対称になる確率を求める

方針

• 文字列の長さLが偶数のとき、奇数個の文字があるなら確率ゼロ
• 文字列の長さLが奇数のとき、奇数個の文字がひとつでないなら確率ゼロ
• 対称になる並べ方は、半分の全部の並べ方なので、(L/2)!通り
• 全体はL!通りなので、確率は(L/2)!÷L!
• 同じ文字があるときは、S個あったらS!通りの並べ方が重複
• 分子を(S/2)!で、分母をS!で割っていく
• 誤差死対策として、乗数または除数をカウンタで持っておいて、ひとつずつ乗除算する
• Failed System Test
• 奇数のときの扱いが間違っていた
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_625/PalindromePermutations.cpp

結果

x-- +1 50pts 504th/717 rating 1573 -> 1522 (-51)

2項係数でやると死ぬのはわかっていたのだがチャレンジできず。

方針は合っていたが、サンプルが通る誤答を直すのは時間がかかる。

http://togetter.com/li/682240

SRM 624

20:15

Div1 Easy (250) BuildingHeights

問題

• 街にある建物の高さが配列で与えられる
• 建物を高くして高さを揃えたい
• M個の建物の高さを揃える最小コストをA[M]とする
• Mが1～Nまでの排他的論理和を求める

方針

• M=1のときはゼロ
• 最大4000個
• O(N^2)は間に合うが、単純ループのO(N^3)は間に合わない
• 高さに合わせるときは、既存のどれかの高さに合わせることになる
• ソートしておく
• 高さをk個揃えるコストから、k+1個揃えるコストが作れるので、O(N^2)で表が作れる
• Passed System Test
• 1次元の累積和だけあれば範囲の和はわかる
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_624/BuildingHeights.cpp

結果

o-- 200.75pts 423rd/794 rating 1571 -> 1573 (+2)

medium450点だけど難しかった。

http://togetter.com/li/679552

TCO 2014 Round 2B

21:59

Easy (350) SwitchingGame

問題

• M個のランプがあり初期状態は消灯している
• 何個かのランプをONにする、OFFにする、次のレベルに行くボタンを押す、のいずれかに1秒かかる
• 設定すべきランプの状態がONまたはOFFまたはどちらでもよい、で与えられる
• レベルを一つずつクリアしていくとき、最短秒数を求める

方針

• 1レベルずつこなさないといけない
• ONかOFFが指定してあるところはさぼれない
• ONかOFFが指定されていて、一つ前が?のときは、他の列にONかOFFがあるなら、そのときに一緒に変更できる可能性がある
• 一つ前の状態と、スイッチの履歴を覚えておけばよい
• Passed System Test
• ?が指定されたときに、状態がONで他の列でOFFを押した、または逆のときは、状態を?に変更することで、少しシンプルになる
• https://github.com/firewood/topcoder/blob/master/tco_2014/SwitchingGame.cpp

結果

o-- 265.24pts 321st/1205 rating 1478 -> 1571 (+93)

それなりに速く解けた。

mediumの題意はkmjpさんのところを読んだらやっとわかった。

http://togetter.com/li/677418

SRM 623

02:04

Div1 Easy (300) UniformBoard

問題

• N×Nの升目がある
• それぞれの升目は空きか、りんごか梨が入っている
• 1手で、任意の果物を別の空きに移動することができる
• 最大K手移動できるとき、りんごのみからなる長方形の最大の面積を求める

方針

• Nが20以下なので、位置と大きさについて全探索できそう
• 長方形が全てAで埋まっていればOK
• 埋まっていないときについて考えると、内側にも外側にも空きがなければ詰み
• 長方形の内側に空きがあるとき、外側には余分なAが必要で、1手かかる
• 長方形の外側だけに空きがあるとき、内側のPを出して外側のAを入れることができ、2手必要
• 内側に空きとPがあるケースは、外に2つ以上Aが必要で、まずAを内側に移動させて外側に空きを作るので、結局のところ、空きはコスト1、Pはコスト2で、空きの位置は気にしなくていい
• どこかに1つ以上の空きがあり、かつ、Aの総個数が長方形のぶんだけあり、かつ、移動コスト以下ならOK
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_623/UniformBoard.cpp

結果

o-- 160.95pts 286th/488 rating 1472 -> 1478 (+6)

判定条件を整理するのに時間がかかった。

最近ようやくdiv1easyの正解率が50%を超えてきた。

http://togetter.com/li/676233

Google Code Jam 2014 Round 2

00:56

Problem A. Data Packing (5pts/8pts)

問題

• 容量がX MBのCD-Rメディアがある
• 1つのファイルを分割せずに格納する
• 1枚に焼くのは2ファイルまで
• 必要なメディアの枚数を求める

方針

• SRM 598のBinPackingと同じ
• ソートして、大きいものから貪欲に詰める
• https://github.com/firewood/topcoder/blob/master/gcj_2014/R2_A.cpp

Problem B. Up and Down (7pts/11pts)

問題

• 数列が与えられる
• 隣り合う数値を交換して、昇順→降順に並べる
• 昇順のみ、または、降順のみでもOK
• 総交換回数の最小値を求める

方針

• まずソートのコストについて考える
• バブルソート
• 左から右へ昇順にソートするとして、自分より大きいものが左にある場合は自分を左に移動する必要がある
• 交換の手順数は、自分より大きいものの個数になる
• 降順にソートするときは、自分より大きいものが右にある場合は自分を右に移動する
• smallは最大値の位置をN箇所全部試せばいけそう
• その点より左にあるものを左に移動 + その点より右にあるものを右に移動
• 通らない
• 反対方向に置くほうがコストが短くなる場合がある
• (終了後)
• 左と右のどちらに移動しても、左側は昇順に、右側は降順になるので、結果的に山型になるので、小さいほうを選べばよい
• https://github.com/firewood/topcoder/blob/master/gcj_2014/R2_B.cpp

結果

ooo----- 5+8+7=20pts 1866th/2526

Tシャツラインは40ptsだったので、全く及ばなかった。また来年。