2013-01-26
Codeforces 163
Div2 A. Stones on the Table
問題
- RGB3色の石が並んでいる
- 隣り合う石が全て異なるようにするために一つずつ取り除く
- 取り除く総数を求める
方針
- 連続してたら+1する
Div2 B. Queue at the School
問題
- 男子女子が一列に並んでいる
- 1ターン毎に条件を満たしたら1移動する
- 男子の直後が女子の場合、次のターンに位置をゆずる
- tターン後の状態を求める
方針
- シミュレーション
- 1番目から見ていき、女子の直前が男子なら交換
Div2 C. Below the Diagonal
問題
- n×nの行列が与えられる
- n-1個は1、その他はゼロである
- 行または列の交換が可能
- 1の位置が与えられる
- 全ての1を対角線よりも下に移動するための手順を求める
方針
- 行または列を共有する1があった場合、それらは交換しても共有したまま
- 行または列を共有する1がないと仮定して解いてみる
- サンプル通らず
- (終了)
結果
oo-- 974pt 225th/1958 rating 1673 -> 1666 (-7)
C以降はかなり難しかった。
Cはデータの持たせ方もいまいちだった。
2013-01-22
SRM 567
Div1 Easy (250) TheSquareRootDilemma
問題
- 整数AとBが与えられる
- (sqrt(A)+sqrt(B))^2が整数になる組み合わせの総数を求める
方針
- AとBをループさせて全探索すれば一応求まる
- AとBをGCD(A,B)で割った商がともにn^2ならOK
- 処理時間は間に合わなさそう
- n^2だけ試せばよいっぽい
- 提出
- Challenge Succeeded
- (修正)
- https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_567/TheSquareRootDilemma.cpp
Div1 Medium (500) StringGame
問題
- 文字列の集合Sが与えられる
- 最初のプレイヤーがSから文字列をひとつ選び、並び替えてXとする
- 最初のプレイヤーがアルファベットの並び順を選ぶ
- XとS内の全ての文字列を並べ替えた文字列のうち、Xが単独の辞書順最小にできるかどうかを求める
方針
- 使用された文字数をカウントしておく
- 他の文字列より文字数が多い場合は、必ず答えに加える
- 同数のときは、引き続きマッチング
- サンプル合ったので提出
- Challenge Succeeded
- (解き直し)
- 辞書順で大きいものは除外していく
- 評価する文字を決める
- 除外していない全ての文字列のうちで、最大か同数であるとき、最大より文字数が少ないものを除外する
- 全ての文字列が除外できた場合は答えに加える
- https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_567/StringGame.cpp
結果
xx- 0pt 488th/654 rating 1373 -> 1309 (-64)
easyは77777を7777にして落とした。たぶん部屋が寒かったせい。定数はコピペすべき。
Aでループを回して、Bに関しては答えにsqrt(M/x)を足せばよいという綺麗な問題だった。
mediumは26回ループみたいな感じで書いたらOKだった。シンプルに書けた。
2013-01-21
Codeforces 162
Div2 A. Colorful Stones
問題
- RGB3色の石が並んでいる
- 色の指示が与えられる
- 指示と同色なら次の石に移動する
- 最後にいる場所を答える
方針
- 一つずつ処理する
Div2 B. Roadside Trees
問題
- 高さのばらばらの木がある
- 頂上にクルミがある
- 移動するか食べるのに時間が1かかる
- 高さが同じなら木から木へ飛び移れる
- 全てのクルミを食べるまでの時間を求める
方針
- 結局のところabsで足す
Div2 C. Escape from Stones
問題
- 岩が自分めがけて落ちてくる
- 逃げると、新しい自分の位置に向かって落ちてくる
- 逃げた方向が与えられる
- 岩が落ちた位置の順番を求める
方針
- rだったら左端、lだったら右端に置いて範囲を狭めていく
Div2 D. Good Sequences
問題
- 連続する2数が互いに素ではない数列を、良い数列とする
- 与えられた数列の部分数列のうち良い数列の最大長を求める
方針
- ある数Xに着目する
- Xより前の数それぞれと素かどうか比べる...のは時間がかかりすぎて無理
- 素でないというのはすなわち素因数が共通
- 素因数ごとに、最後に使われた場所だけ覚えておけばよさそう
- 素因数分解して、最後の素因数の場所の長さ+1の最大値を記録していく
- 提出
Div2 E. Choosing Balls
問題
- 何色かのボールがあり、それぞれのボールに値が設定されている
- ボールを順番に取り出すか使わないかを選ぶ
- 取り出したボールのスコアは、直前のと同じ色ならa倍、そうでなければb倍した値とする
- スコアの最大値を求める
方針
結果
ooxo- 2874pt 173rd/1525 1674 -> 1673 (-1)
Dが解けたのはなかなか会心。ただCが落ちたためratingほぼ変わらず。
CがTLEした。MSVCの100万回endl出力はGCCのより遅く、GCCだと1secだったがMSVCだと全く間に合っていなかった。endlはバッファをフラッシュするので遅いということだが、GCCも仕様は同じだと思うので優秀である。遅いらしいというのは知っていたが全く気にしていなかった。
改行でなくスペースで区切ってもOKだったっぽい。
2013-01-17
Codeforces 161
Div2 A. Beautiful Matrix
問題
- 中央に1を移動させる
方針
- abs取るだけ
Div2 B. Squares
問題
- 異なる大きさの正方形を重ねる
- ちょうどk枚重なる点をどれでも良いので答える
方針
- 辺の上の座標がn～1になる
- kが1～nなら辺上の座標で答える
Div2 C. Circle of Numbers
問題
- 1～nのN個の数値を円状に並べる(5<=N<=10000)
- 隣と一つ飛びの隣をペアとする
- 2N個のペアが与えられる
- 元の数値の並びを答える
方針
- 紙に書いてみる
- XYZABCDEFGと並んでいたとき、Aの隣の候補について考える
- set<int>を10000個用意してペアを突っ込む
- AにはYZBCがペアとして入る
- BのペアはZACD
- AとBの共通のペアはZとCで、一つ飛びだと共通のペアは1つ
- つまり共通のペアが2つなら隣
- ただしN=5のときは、ペアが4つ、すなわち自分以外全部ペアなので、任意の並び順で良い
- N=6のとき、ABCDEFはACBDFEと答えてもよい。反対側の数値だけがペアではないので、それだけ場合わけするとうまくいく
- N>=7は場合わけ不要
- 1から順番に1つずつ決めていく
結果
ooo-- 492+464+1500=2456pt 83rd/1591 rating 1534 -> 1674 (+130)
Cが通ったので満足。
2013-01-14
Codeforces 160
Div2 A. Roma and Lucky Numbers
問題
- 4と7がラッキーナンバー
- 4と7がk個までの数の個数を求める
方針
- 数えるだけ
- intではなくstringで入力する
Div2 B. Roma and Changing Signs
問題
- 非減少の数列が与えられる
- ちょうどk回符号を反転する
- 和の最大値を求める
方針
- 最後の負の数までは、小さいほう(絶対値の大きいほう)から反転していく
- 最後の負の数については、正の数を反転したほうが良いケースがある
- 場合わけ...
- (終了後)
- 絶対値でソートして持っておくのもあり
Div2 C. Maxim and Discounts
問題
- スーパーで買い物をする
- Mパターンの割引がある
- まとめて買うと割引される
- 割引するためにはq個買う
- q個の中の最低金額を上回らない品物が最大2個無料になる
方針
結果
ooo-- 00:05+0,00:45+2,01:29+2 2076pt 444/1424 rating 1581 -> 1534
Bはとりあえず負の数は全部反転させて、そのあと絶対値の判定をすればよかった。最後のインデックスの負数で場合わけしてしまい複雑になった。
Cは最小のだけ貪欲に適用すればよかった。
Dはあとで解く。