hotpepsiの練習帳

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だったので、全く及ばなかった。また来年。