hotpepsiの練習帳

TCO 2013 Round 1B

23:06

Easy (250) EllysPairs

問題

• 生徒を2人ずつペアでプロジェクトに当たらせる
• 生徒のパフォーマンスが与えられる
• 生徒のパフォーマンスの合計がプロジェクトの成果となる
• 最低と最高の成果が最も小さくなるときの最小値を求める

方針

• ソートして、最小と最大を組み合わせる
• 先頭と中央のペアの差を返す
• 提出
• Challenge Succeeded
• サンプルは先頭と末尾のペアが最大だが、どのペアも最小または最大になりうる
• 例えば{1,2,4,5,6,9}で落ちる
• 全ペアの最大と最小を取る
• 書き直し
• https://github.com/firewood/topcoder/blob/master/tco_2013/EllysPairs.cpp

Medium (500) EllysFigurines

問題

• グリッド上のボードにいくつかの人形が置かれている
• 一回の操作で、連続するR行またはC列の人形を取り除くことができる
• 最小の操作回数を求める

方針

• 制約が小さい
• 全探索できるかも
• 行か列をビットマスクでループさせれば良さそう
• 列のビットマスクでやってみる
• あるビットマスクBを決めて、最初に見つかったビットから連続するCビットを1とカウントする
• 列については、ビットマスクBの反転と論理積を取って、残っていれば列消去する必要があるので、そこからR列をまとめて1カウントとする
• 提出
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/tco_2013/EllysFigurines.cpp

Hard (1000) EllysReversals

問題

• いくつかの英数字からなる単語のリストがある
• 任意の単語Sと、Sの長さを超えない偶数kを選ぶ
• Sの1番目からk番目までの文字列を反転する
• その結果ほかの単語と一致した場合は、その単語をリストから取り除く
• 最終的に残る単語の数を求める

方針

• 色々試してみる
• 文字列の長さが奇数の場合、最後の文字だけは移動できない
• そのほかの文字は、どこへでも行ける
• ただし、移動は2個がペアになっていて、ペアは解消されない
• ペアのリストをソートしたものに末尾を加えたもので比較すればよい
• 最終的に重複したものを消す
• 提出
• Failed System Test
• 同じものが奇数のときは1つ残る
• 書き直し
• https://github.com/firewood/topcoder/blob/master/tco_2013/EllysReversals.cpp

結果

xox 388.90pt 503rd/1820 rating 1383 -> 1401 (+18)

easyは、サンプルにはソートした最小と最大のペアが最大値のケースしかなかったので、逆のケースを考えてabsを足しておいたが、全く不十分だった。弱い。

mediumは、このタイプのビットマスクで全列挙は何回かやったことがあったので、迷わず書けた。

hardは勢いで書いた割にはおしいところまで行った。

3つ提出できたのでなかなか楽しめた。R2はプラス点を目指したい。