hotpepsiの練習帳

SRM 660

22:44

https://competitiveprogramming.info/topcoder/srm/round/16463/div/1

Div1 Easy (250) Coversta

問題

• N×Mのセルが与えられる
• 各セルはスコアを持つ
• 任意の2つのセルにステーションを建設する
• ステーションは、建設した位置を中心に、特定のパターンでセルを覆う
• 1つ以上のステーションで覆われたセルの合計スコアの最大値を求める

方針

• 全探索
• 死
• (終了後)
• 一つ目を全ての場所に置いてみる
• スコアの降順でソート
• 良いスコアの先頭100個と、ほかの全ての場所を試す(K^2程度しか重複しないので枝狩りして良いらしい)
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_660/Coversta.cpp

結果

x-- +1 208th/474 rating 1285 -> 1351 (+66)

xが上下方向なのがやや罠。良いものから順にやる、というのは思いつくべき。

重複して数えているのを落とすことができた。

http://togetter.com/li/830675

TCO15 Algorithm Round 2A

01:11

https://competitiveprogramming.info/topcoder/srm/round/16475/div/1

Easy (300) ModModMod

問題

• 配列mの各要素でmodを取る関数f(x)がある
• f(1)からf(R)までの合計を求める

方針

• 普通に再帰で書く
• 死
• (終了後)
• [1,R]の個数を配列cntで覚えておき、それぞれを1で初期化する
• MODの最大値Uを覚えておき、R+1で初期化
• mの各要素Mについて、順番にMODを取っていく
• MがU未満のとき、[M,U)の数値xについて、cnt[x % M]にcnt[x]を加える
• その結果、cnt[1]～cnt[M-1]までの部分に、総数が入る
• MがU以上のときは無視していい
• 最後に[1,U)のiについてi×cnt[i]の総和を求める
• https://github.com/firewood/topcoder/blob/master/tco_2015/ModModMod.cpp

結果

x-- 0pt 430th/902 rating 1303 -> 1287 (-16)

順番に計算するだけだけど全く思いつかなかった。

チャレンジのみ無効でrated

http://togetter.com/li/828905

Google Code Jam 2015 Round2

16:12

https://code.google.com/codejam/contest/8234486/dashboard

Problem A. Pegman

問題

• R行C列のマス目に、いくつかの矢印が置かれている
• 任意の場所にペグマンを置く
• 置いた場所に矢印があった場合、その方向に、矢印に当たるまで進む
• 矢印の方向は書き換えることができる
• どこにペグマンを置いてもマス目の外にでないようにするために必要な書き換え回数の最小値を求める

方針

• 矢印に置かれた時は、矢印にぶつかる必要がある
• 各矢印について、4方向のいずれかに矢印があればOK、なければ無理
• そのままだと矢印にぶつからないのなら方向を変える
• https://github.com/firewood/topcoder/blob/master/gcj_2015/R2_A.cpp

Problem B. Kiddie Pool

問題

• N種類の蛇口がある
• それぞれの蛇口iからは流量Ri、温度Ciの水が出る
• プールに温度X、容量Vだけ水をためるのに必要な最短秒数を求める

方針

• smallのみ
• Nは2以下
• N=1のときは温度が一致すれば割るだけ
• N=2のときは、片方または両方の温度がXと一致すればそれを使う
• そうでないとき、X度未満とX度を超える蛇口が必要
• 温度差の比でブレンドする
• 必要な水量を流量で割り、時間の長いほうが答え
• https://github.com/firewood/topcoder/blob/master/gcj_2015/R2_B.cpp

Problem C. Bilingual

問題

• N行の文が与えられる
• 1は空白区切りの単語からなる
• 1行目は英語、2行目はフランス語
• 3行以上ある場合は、いずれかの言語
• 英語とフランス語、両方に出てくる単語の総数の最小値を求める

方針

• smallのみ
• 各単語を数値化しておく
• どちらか不明なのは最大18行なので、全て試す
• https://github.com/firewood/topcoder/blob/master/gcj_2015/R2_C.cpp

結果

A small,large B small C small

28pt 582nd

5年目にしてようやくTシャツゲット。(GCJJではもらっていたが) 宝物が増えました。

http://togetter.com/li/828625

Google Code Jam 2015 Round1C

00:15

https://code.google.com/codejam/contest/4244486/dashboard

Problem A. Brattleship

問題

• 戦艦の位置あてゲーム
• R×Cマスに幅Wの戦艦を置く
• プレーヤーは戦艦の位置を知らない
• 1ターンずつどこかのマスを攻撃する
• 戦艦のどこかの部分に当たったら、当たったことがわかる
• 戦艦の全てのマスに確実に当てる手数の最小値を求める

方針

• R-1行については、Wマスおきに攻撃するのが最善なので(R-1)×(C÷W)回必要
• 最後の行については、W*2マス以上はWマス単位で攻撃していく
• 最後に残ったマスの範囲内に必ず戦艦がある
• 残りのマスがW個ならコストW、そうでなければ1回は外すのでW+1
• https://github.com/firewood/topcoder/blob/master/gcj_2015/R1C_A.cpp

Problem B. Typewriter Monkey

問題

• K個のキーのあるキーボードを猿がランダムに叩き、長さSの文字列を生成する
• 長さLのキーワードが与えられる
• 文字列Sに含まれるキーワードの個数ぶんのバナナを猿に与える
• 必要な最大数バナナを持っていて、猿に与えた後、残りのバナナの数の期待値を求める

方針

• キーボードの文字別の出現個数を数えておく
• L個入力してキーワードに一致する確率dは、(キーワードのi番目の文字の出現個数)÷KをL回かけたもの
• L文字以降の各位置についてキーワードに一致する可能性があり、それらは独立事象
• なので、バナナの期待値eは、d×(S - L + 1)
• 一方、必要なバナナの最大数は、キーワードを連続で入力できたとき
• キーワードの後半と、キーワードの前半が一致するときは、Lより短い周期になる
• 最大値 - 期待値が答え
• https://github.com/firewood/topcoder/blob/master/gcj_2015/R1C_B.cpp

Problem C. Less Money, More Problems

問題

• D種類の硬貨があり、1度の支払いには同時にC枚までしか使えない
• 1からVまで全ての金額に対応するために追加する必要がある硬貨の種類の数を求める

方針

• smallのみ、愚直に埋める
• 支払い可能なフラグの配列v[100]を用意しておく
• 価値dのコインを追加したらvを埋める関数fill (v[i-d]が支払えるならv[i]は支払える)
• 価格1から順番に、価格dが支払えなければ、価値dのコインが必要なので、追加する
• https://github.com/firewood/topcoder/blob/master/gcj_2015/R1C_C.cpp

結果

A small, large B small, large C small

77pt 316th

提出したのが全部通るのはとても良い。

http://togetter.com/li/819466

SRM 659

21:31

https://competitiveprogramming.info/topcoder/srm/round/16462/div/1

Div1 Easy (250) ApplesAndOrangesEasy

問題

• N個のりんごまたはみかんがあり、1つずつ順番に全て食べる
• 連続してK個食べたうちの、りんごはK/2個以下である
• りんごを食べた情報である配列infoが与えられる
• info[i]番目に食べたのはりんごである
• りんごを食べられる最大数を求める

方針

• 適当な貪欲
• Failed System Test
• 位置iのK個の和を求めておく
• 位置iについて、i-K+1からiまで全ての場所のK個の和がK/2個未満なら、位置iをりんごにすることができる
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_659/ApplesAndOrangesEasy.cpp

結果

x-- 0pt 199th/293 rating 1350 -> 1303 (-47)

単純に最後のK個の範囲内にN/2個未満なら置く、にしてしまった。

http://togetter.com/li/820832