hotpepsiの練習帳

SRM 545

01:45

Div1 Easy (275) StrIIRec

問題

• 長さがNの文字列Sの各文字をS[x]で表す。
• 0 <= i < j < NにおいてS[i] > S[j]が成り立つ個数がスコアとなる。
• aから順にN個のアルファベットを使った文字列で、
• 与えられた文字列minStrよりも辞書順で小さくなく、
• スコアがminInv以上で、辞書順最小の文字列を求める。

方針

• アルファベットを逆に並べたものが最大のスコア N*(N-1)/2
• 全体としては、辞書順でminStr以上となる文字列を、手戻りが少ないように探す
• minStrをprefixとして、そのあとに辞書順最大の文字列を加えてみて、スコアを計算する
• もしminInv以上ならば、解が存在するということなので、prefixを固定して、残りの部分がminInv以上になるまで辞書順最小から探索する
• minInvを下回るのならば、そのprefixではだめなので、最後の文字を+1して、そのあとに辞書順最大の文字列を加える
• それでもだめならprefixを1文字減らして、最後の文字を+1する、という操作を繰り返す
• prefixがなくなったら、不可能なので終了
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_545/StrIIRec.cpp

結果

0pt 480th rating 1299 -> 1278

文字列の探索はけっこうしんどい。

証明してないが、スコアがminInvちょうどのときは、その文字列を返してしまってよさそう。

TCO12 Round 2C

23:30

Easy (300) GreedyTravelingSalesman

問題

• セールスマンがN個の都市を0から順番にまわる。
• 全ての都市は、片方向の道路が両方向で用意されており、どの都市からどの都市へも移動できる。
• セールスマンは、未訪問の都市のうち、コストが最小の道路を選んで移動する。
• 各道路のコストが与えられる。ただし道路の1つが工事中のため、1～9999の間で変化する可能性がある。
• 最悪のコストを求める。

方針

• 道路の変化は一度だけで、かつ、最初に起きるとしてよい (sampleより)
• 変化前の最短経路を求めておく
• 最短経路のうち、1箇所が変化する
• 単純に考えると、そのうちの1つが9999になる
• それだけでsampleのいくつかが通るが、合わない
• 全ての経路を1～9999に変化させる全試行でも求まるが、もちろん間に合わない
• 変化するパターンを列挙すると、(1)最短経路のコストが高くなり、別の経路にいく(2)最短経路のコストが高くなるが、同じ経路のまま(3)別の経路のコストが低くなり、別の経路にいく、の3通り
• (1)は最短経路のコストを9999にする
• (2)は最短経路のコストを、最低コスト近辺で試す (同じコストの場合indexが小さいほうが選ばれるため、それを考慮して1を調整する)
• (3)は別の経路のコストを最小値に変更する (マイナス1の調整は(2)と同じ)
• マイナス1調整した場合、最小のコストは1なのに注意する
• BFSでもっと単純に書ける
• https://github.com/firewood/topcoder/blob/master/tco_2012/GreedyTravelingSalesman.cpp

結果

0pt 539th rating 1302 -> 1299 (-3)

3回連続0点なので反省。

練習としては、sample7が通るように書いたらsystem testも通ったので、まあまあ。

SRM 544

03:05

Div1 Easy (275) ElectionFraudDiv1

問題

• 候補者がX人、投票者がY人いる。
• 候補者の得票率を丸めた数値の配列が与えられる。
• 投票者の総数の候補の最小値を求める。

方針

• 全探索
• challenge succeeded
• 書き直し
• 下限と上限を求めて、下限 <= 推定投票数 <= 上限になっていたらOK
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_544/ElectionFraudDiv1.cpp

Div1 Medium (500) FlipGame

問題

• 高橋君はH×Wの盤面にオセロの駒を並べた。
• 左上から右下へ向かう境界線を選び、左側を全てひっくり返す操作を行う。
• 盤面の状態が与えられる。全てを白にする最小の手数を求める。

方針

• 一番上の行から貪欲に
• 無駄にintrinsicを使う
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_544/FlipGame.cpp

結果

0pt 353rd rating 1333 -> 1302

Petrさんiwiwiさんというえらい部屋に割り当てられてしまった。

challenge phaseのログの流速がめっちゃ速くて面白かった。

mediumにきゅうりが出てきて涙目 (と書かなくてはいけない気がした

Google Code Jam 2012 Round 2

00:08

A. Swinging Wild (5 + 9 points)

問題

• 危険なジャングルの湿地帯にいる。
• 自分の小屋から、愛するハニーのいる小屋へ到達したい。
• 小屋と小屋の間には何本かの蔓（つる）がぶらさがっていて、蔓をターザンのようにスイングさせることにより、次の蔓をつかんで移動することができる。
• 愛するハニーのもとへ到達できるかどうかを求める。

方針

• 問題を何となく理解するのに30分かかり絶望
• 蔓Bが蔓Aの稼動範囲内にあれば、行くことができる
• 蔓Aから蔓Bへ移動してからスイングするまでには以下のお約束がある
• (1)スイングして蔓Bをつかむ(2)蔓Bの真上に上る(3)蔓Aの方向へ水平方向へ戻る(4)蔓Bでスイングする
• 蔓Aがぶらさがっている場所を越えて戻ることはできない（問題文の制約）
• 蔓Bの長さが蔓Aがぶらさがっている場所までの距離より短い場合、蔓Bの長さでスイングできる（sample 3）
• BFSで区間を更新するようにしたらlargeがTLEのため終了後解きなおし
• 整理すると、最初にスイングする長さを超えることは決してなく、また、最適なコースをスタートからゴールまで進んでいくのみ
• ある蔓の、つかむことができる最下点をメモしていく
• 前方だけ更新していけばよい
• https://github.com/firewood/topcoder/blob/master/gcj_2012/2_A.cpp

結果

5pt 2044th

A-smallしか解けなかったが、A(small+large)+B(small)を解いたとしてもTシャツに届かないという絶妙のゲームバランスだった。

positive scoreだったのはよかった。来年は2問解けるようにしたい。

SRM 543

22:13

Div1 Easy (250) EllysXors

問題

• LからRまでの全数のXORを求めよ

方針

• 2個単位でゼロになるのかな
• 合わない...
• (終了後)
• 紙に列挙してようやく理解
• ある偶数と次の奇数とのXORは2n^(2n+1)=1
• 1 XOR 1 = 0なので、ある偶数2nから連続する4数のXORはゼロ
• ループで計算する際、奇数まで計算した時点で、残りが4以上なら飛ばすことができる
• また0からxまでのXOR f(x)は、4n,1,4n+3,0の繰り返しとなるので、f(L-1)^f(R)でも求まる
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_543/EllysXors.cpp

Div2 Easy (250) EllysTSP

問題

• 町と村の数が与えられる
• 町と村を交互に移動する場合、最大何回移動できるかを求める

方針

• 読解問題
• 少ないほうをL、多いほうをMとする
• 整理すると、L+min(L+1,M)回
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_543/EllysTSP.cpp

結果

0pt 660th rating 1414 -> 1333

適正レートに落ちてしまった。

2個単位で1になるのは即気づくべき。なんとunsigned intだと40億回ループでも間に合うらしい。そこを突いてくるのはすばらしい。

div2 easyは差が2以上のときと同数のときのテストケースが通ればOK。