hotpepsiの練習帳

SRM 569

14:31

Div1 Easy (250) TheDevice

問題

• Mビットのデータが書かれたプレートがN枚ある。
• 各ビットの処理がORかANDかXORのMビットのデバイスをプレートで調べる。
• デバイスの全入力を機能を調べるのに必要な追加のプレートの枚数を求める。

方針

• 真理値表とサンプルを読む
• 0と1だけだとORとXORが区別できない
• というように見ていくと、各ビットについて、少なくとも1個のゼロと2個の1が必要
• プレートは何回使ってもいいので、ビット毎の必要枚数の最大値が答え
• ビット毎にループ
• 0があったら...と場合わけ
• 提出
• Passed System Test
• (書き直し)
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_569/TheDevice.cpp

Div1 Medium (500) TheJediTest

問題

• 何階建てかの建物に、ジェダイの素質を持った子供がいる。
• ジェダイの騎士は最大K人まで面倒を見ることができる。
• 子供は上下に1階だけ移動できる。
• 必要なジェダイの騎士の数を求める。

方針

• 剰余について考えればよい
• DPかな
• しかし何人移動すればよいかわからない
• 最上階または一番下の階について考える
• 余りが生じても、ひとつ上にしかいけないので、ひとつ上の階で何とかするしかない
• つまり選択肢はないので、greedyに決められるっぽい
• 書くけど合わない
• (終了後)
• N階に注目する
• N-1階に余りがいれば、N階に移動させて、N階で面倒を見る
• 合計がK人に満たなければ、N+1階からも移動させて面倒を見る
• N+1階で場合わけしないように、ダミーを挿入
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_569/TheJediTest.cpp

結果

o-- 185.10pt 305th/567 rating 1322 -> 1364 (+42)

easyはサンプルに2がないので、かなり慎重に解いたがまあまあの時間だった。

mediumは合わないなあと思っていたら、最初に剰余を取ると移動できなくなるので増えてしまうのだった。すごくSRMらしくていい問題。

Facebook Hacker Cup 2013 R1

23:39

A. Card Game (20)

問題

• 数値が書かれたN枚のカードがある
• K枚配り、最大の数が手の強さとなる
• 平均の手の強さを求めるため、手の強さの合計値を求める

方針

• 最大値が含まれている場合=nCk回は最大値になる
• 最大値を含まない場合について考える
• 2番目に大きい数になるのは、N-1枚の中からK枚選んだとき=n-1Ck
• そうでない場合は3番目、4番目...となるが、残りがK枚未満になったら終了
• すなわち、x>=Kについて、xCk回ずつ出現する
• 提出
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/fhc_2013/A_CardGame.cpp

B. Security (35)

問題

• 文字列の一部を?で置き換える関数fと、文字列をシャッフルする関数gがある
• 文字列keyは、l文字毎に区切られている
• k1=f(key)、k2=f(g(key))が与えられる
• kとして可能性のある文字列のうち辞書順最小のものを求める

方針

• k2をシャッフルしたものがk1と対応すればよい
• これはいわゆる2部マッチングでは...
• l文字ごとに辺をつないでマッチング
• 文字を決めたい
• ?の文字を1文字ずつaから順番に代入して、マッチするなら固定する
• 提出
• Failed System Test
• (修正)
• https://github.com/firewood/topcoder/blob/master/fhc_2013/B_Security.cpp

C. Dead Pixels (45)

問題

• W×Hの画素の液晶ディスプレイがある
• 不良な画素を求める式が与えられる
• P×Qの範囲で不良な画素を含まない領域の総数を求める

方針

• 区間クエリな気がするが...
• 点の総数が少ないのでsetでいけそう
• set<int>を40000用意して、y座標に対応するsetに点を投入
• 縦幅Qの長さについて処理
• 横幅がP以上ある範囲を進めていく
• 提出
• Failed System Test
• (修正)
• https://github.com/firewood/topcoder/blob/master/fhc_2013/C_DeadPixels.cpp

結果

oxx 20pt 1237th/3617

Bはぼんやりしていて無用なソートを入れてしまった。ソートを消したら通った。

Cは終端の扱いがバグっていた。

だいたい方針が立ったのは良かった。

SRM 568

03:25

Div1 Easy (250) BallsSeparating

問題

• N個の箱がある。
• それぞれの箱には3色のボールがそれぞれ1個以上入っている。
• ボールを1個ずつ移動して、それぞれの箱のボールを1色以下にしたい。
• 最小の操作回数を求める。

方針

• 色の数よりも箱の数の方が少ない場合、不可能
• なので最初に色の数を数える(が、これは無駄だった。制約より、箱が3未満なら不能)
• 1色以下にすればよいが、0色にするのは無駄
• 数が一番多い色を残して全て移動すればよい
• とりあえず単純にやる
• sample3で死
• 同じ色に偏るとだめ
• 少なくとも1色について1つの置き場所は必要
• 3色の置き場所の組み合わせを全部試せばよさそう
• 書いた
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_568/BallsSeparating.cpp

結果

o-- 127.53pt 474th/723 rating 1309 -> 1322

mediumが難しくてeasy早解きな回。微増。

途中の無駄が多くて遅かった。

Codeforces 164

01:32

A. Games

問題

• ユニホームにはホームとゲストの2色ある
• 同色の場合はホーム側がゲストの色でプレーする
• その場合はいくつあるか求める

方針

• 2重ループで求める
• チームAがホストでチームBがゲストの場合とチームAがゲストでチームBがホームの場合は別

B. Buttons

問題

• N個のボタンがある
• 正しい順番に押すとへこんでいく
• 間違えると全部戻る
• 最悪何回試行すればよいか求める

方針

• 残り2候補となって、一方が違う場合、その一方が正解
• N個あるとき、1×N-1回押す→2×N-2回押す...

C. Beautiful Sets of Points

問題

• (0,0)から(n,m)までの整数の点がある
• 任意の2点のユークリッド距離が整数でない点の最大集合を求める

方針

• xかyが同じ点は整数になる
• xもyも共有しない点...直線x=y
• Wrong answer on pretest1
• ださすぎる
• x=-yに直す
• Passed System Test

結果

ooo-- 2718pt 179th/1882 rating 1666 -> 1687 (+11)

A,B,Cはそこそこいい時間で提出。

D,Eは難しくて提出できず。

Facebook Hacker Cup 2013 QR

02:07

A. Beautiful strings (20)

問題

• 文字列の美しさを評価する
• アルファベットに1～26の価値を設定する
• 文字列の最大の価値を求める

方針

• 文字毎の価値を自由に決めていいということらしい
• 文字の出現数を配列にカウント
• 昇順にソートして(index+1)をかける
• accepted

B. Balanced Smileys

問題

• 文字列がbalancedかどうかの判定条件ある
• 顔文字や括弧を含む文字列が与えられる
• balancedかどうかを求める

方針

• 少なくとも1通り、balancedとして解釈可能かどうかを判定すればよい
• DFS
• [start,end)の範囲がbalancedかどうか判定する関数を用意
• [start,start)はbalanced
• [start,end)が顔文字に一致していればbalanced
• [start,x)と[x,end)がbalancedなら全体がbalanced
• startとend-1が()ならば、[start+1,end-1)がbalancedかどうかに従う
• accepted

C. Find the Min

問題

• 配列はハッカーの愉しみである(知らなかった...)
• n個の数値からなる配列の最後の要素を求める
• 最初のk個は、生成するパラメータが与えられる
• 最初のk個以降の要素は、それよりk個前の要素に含まれない0以上の整数

方針

• 直前のk個をsetに突っ込んで生成
• TLE
• (終了後)
• 最初のk個には同じ数も含まれている
• 乗算のオーバーフローを考慮
• k個のうちに含まれているかどうかは、0からkまでの範囲を知っていればOK
• 配列で持っておき、いちいち調べても制限時間には十分間に合う

結果

oox 55pt (通過)

一発提出なのに適当すぎて反省。