hotpepsiの練習帳

SRM 581

23:05

Div1 Easy (250) SurveillanceSystem

問題

• N個の区画に分割された倉庫があり、そこからコンテナを盗み出したい
• 何台かの監視カメラが設置されている
• コンテナがある位置と、監視カメラが監視しているコンテナの数が与えられる
• カメラの位置は全て異なる
• 各区画の監視状態を求める

方針

• 位置毎に試す
• だめぽ
• (終了後)
• kojingharangさんのを読む
• 置かれる可能性のある場所について+1していく
• A台監視するカメラがB台あり、その場所の候補の個数をCとする
• 置かれる可能性のある場所の個数が全部でC個しかない場合は全て確定(監視されている)
• B-1台のカメラが設置済だとして、残りの候補地は(C-(B-1))通りある
• このとき、C-B+1通り以上設置される可能性のある場所は確定
• そのほか、1回でも置かれる可能性のある場所は?に設定
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_581/SurveillanceSystem.cpp

結果

--- 0pt 1299 -> 1265 (-34)

難しかった。この問題は何系なのだろう。判定系?

Codeforces Round #185

23:52

Div1 A. The Closest Pair

問題

• i,jで二重ループするプログラムが与えられる
• Kよりも多くループを実行するための入力を与える

方針

• xの差分が距離が距離を越えないようにする
• x=0、yが単調増加を与えれば、xの差分がずっとゼロなので継続する
• ループの最大回数はL=N*(N-1))/2
• KがL以上なら無理
• そうでなければ出力
• Passed System Test

結果

Bが難しくて解けなかった。

pretestで落ちるはずのが落ちていなかったらしくノーコン。

SRM 580

01:37

Div1 Easy (250) EelAndRabbit

問題

• 地点Xにうさぎがいる
• N匹のうなぎがいる
• それぞれの長さはLで、時間Tに地点Xに頭が到達する
• うさぎは、2回までうなぎをつかみどりできる
• うなぎを取れる最大数を求める

方針

• うなぎの頭としっぽの座標の合計2N個の座標で全探索
• ある座標のときに捕獲できるうなぎをbitでリストXに保持しておく
• リストXの任意の2つの組み合わせのbitの論理和で、ビットが立っている最大数が答え
• 提出
• Passed System Test
• (終了後)
• 単純にforループでまわすだけでよかった
• かつ、頭だけ調べればよい
• というのは、同時に捕獲できる場合、その範囲内には必ずどれかの頭がかかっているから
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_580/EelAndRabbit.cpp

結果

o-- 171.88pt 483rd/796 rating 1266 -> 1300

うなぎの問題が通ると嬉しい!

SRM 579

02:11

Div1 Easy (250) UndoHistory

問題

• historyバッファを持つエディタがある
• 現在行の状態は常にhistoryバッファに履歴として残る
• 任意のhistoryバッファから2クリックで現在行にコピーすることができる
• enterキーで出力行に入る
• enterを入力しても現在行の内容はそのまま残る
• 入力すべき出力行の配列が与えられる
• キーストロークまたはクリックの合計の最小値を求める

方針

• 現在行が出力行の一部になっていれば、そのまま入力してもよい
• そうでない場合は、履歴から持ってくる必要がある
• そのまま入力するコストと、履歴から持ってきたコストの小さいほうの合計
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_579/UndoHistory.cpp

Div1 Medium (450) TravellingPurchasingMan

問題

• 店がN個、興味のある店がM個ある
• それぞれの店の開店時間、閉店時間、買い物にかかる時間が与えられる
• 店Aと店Bが道路で結ばれている場合、移動にかかる時間が与えられる
• 同じ店では1度しか買い物できない
• 閉店時間ちょうどに入店してもよい
• 店(N-1)からスタートして、買い物ができる最大数を求める

方針

• 行けるか行けないかはWarshall-Floydで求めておく
• 距離を求めた後は、最初の移動以外は、M個の店の間だけを移動したと思えばいいので、Mを超える店は忘れてよい
• priority queueで開始時間の早いやつから処理していく
• (TLE)
• (終了後)
• 店の数は16以下なのでbitDPで全て列挙できる
• dp[行った事のある店の集合(bit)][最後に買い物した店]＝最早時刻
• 初期化として、最初にM個それぞれの店から立ち寄った場合の時刻を求めておく
• あとはbitマスクを全て列挙する
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_579/TravellingPurchasingMan.cpp

結果

x-- 0pt 563rd/803 rating 1311 -> 1266 (-45)

easyは打ち直さない判定を、1文字だけ打ち直す場合だけにしてしまい撃沈。

mediumはbitDPの練習になった。

Google Code Jam 2013 Round 1C

22:35

A. Consonants

問題

• 連続する子音が多いほうが偉い村がある
• 名前が与えられる
• 連続する子音がL以上の部分文字列がいくつあるか答える

方針 (small,large)

• smallのみは時間がもったいないので、O(N)解法だけ書いた
• 準備として、子音の開始位置posと、連続する長さclengthを求めておく
• ただし長さがL未満なら無視する
• 現在位置iについて処理する
• iからはじまる部分文字列がいくつあるか求めて、iを1つずつ進めていく
• iからL文字以上子音が連続しているなら、L文字以上の任意の文字列が該当する
• そうでなければ、iよりあとの子音の位置からL文字以上の地点からはじまる
• 整理すると、着目するpos[x]の終点が、現在位置iから長さLの地点よりあとならば、max(pos[x],i)からL文字から先は全て条件を満たす
• そうでなければ、pos[x]は現在位置には無縁なので、xを進める
• https://github.com/firewood/topcoder/blob/master/gcj_2013/R1C_A.cpp

B. Pogo

問題

• NEWSいずれかの方向へジャンプできる
• ジャンプする距離は1ずつ増える
• 座標(X,Y)に到達するためのジャンプ手順を求める

方針 (small)

• メモ化した
• バグっているけど通った
• (書き直したもの)
• https://github.com/firewood/topcoder/blob/master/gcj_2013/R1C_B_s.cpp
• 横横縦縦のように交互に移動すると＋1が実現できるので、それでやればよかったらしい。頭いいな...

方針 (large)

• autumn festで類題が出題されていたらしい
• http://www.slideshare.net/tomerun/together-14867665
• 1～tまでの合計と偶奇が必要条件らしいことは理解
• 書いてみた
• https://github.com/firewood/topcoder/blob/master/gcj_2013/R1C_B_l.cpp

結果

A small+large, B small = 38pt 1181th/4467

round1で戦いが終わってしまった。

Aについてはwrong answerを2回出してしまい、それだったらsmallのみ解法で提出しつつ、それをlargeのテスターに使うようにすればよかった。

Bはメモ化テーブルの作り方を間違って1回wrong answerになった。バグっぽい解を提出した。

出来は去年と大差ないけど、復習の速度はだいぶ速くなっているので、全体的には前より解けるようになっているんじゃないかなという気はする。

来年はもう少し予習して臨みたい。