hotpepsiの練習帳

Codeforces 142 Div2

23:46

A. Dragons

問題

• 自分の腕力sよりも弱いドラゴンは倒せる
• ドラゴンを倒すと腕力がy増える
• n匹のドラゴンが倒せるかどうかを求める

方針

• ソートして足していくだけ

B. T-primes

問題

• 約数がちょうど3つかどうかを判定する

方針

• 素数の2乗ならOK
• 初期化時にstd::set<long long>に突っ込んでおく

C. Shifts

問題

• N行M列のビット列が与えられる
• ある列全てを1にするための最小のシフト回数を求める

方針

• ある行yについて処理することを考える
• その行yを位置xに揃えるコストを求める
• ある位置currentにビットが立っていたら、その前にビットが立っている位置prevとcurrentの近いほうにシフトするものとして最小コストを計算
• 全行のコストを足して、一番小さい桁が答え

結果

oox 808pt 620th rating 1629 -> 1555 (-74)

Cは単純にfindと逆の文字列のfindでやったらTLEした。単純すぎた。

ビットが立っている位置を保持しておいて、2分探索なら通りそう。

Codeforces 141 Div2

01:56

A. Is your horseshoe on the other hoof?

問題

• 4色の蹄鉄を用意したい
• 何種類買う必要があるか

方針

• ソートして重複(連続)してるのを数える

B. Two Tables

問題

• テーブルの重なりの最大値を求める

方針

• 範囲に気をつけて全探索

C. Fractal Detector

問題

• 4分割して塗る操作を2回以上行った図形をフラクタルとして、何個あるか数える

方針

• わからん...
• ふらさんのブログを写経、再帰的にDP

結果

oox 241st rating 1564 -> 1629

Cがわからないまま放置していたのだがようやく復習(といっても写経しただけ)。きれいなDP。

Codeforces 139 Div2

02:32

A. Dice Tower

問題

• サイコロを縦に積む
• 一番上の面と、横の2面だけか見えている
• 並べ方が一意かどうかを求める

方針

• 上からありえないやつをフィルタしていったがWA
• 見えている2面が全部同じこと(＝上面で見えている面が横面に出ないこと)が条件

B. Well-known Numbers

問題

• 直前のk個の和からなる数列をkぼなっちと呼ぶ
• 数sをkぼなっちの和で表す

方針

• メモ化したらごみ(ゼロ)が入ってしまいWA
• 大きい数から貪欲でやればよいっぽい

C. Barcode

問題

• 与えられた模様をバーコード状に変更するための最小コストを求める
• それぞれの色はX以上Y以下の幅であること

方針

• コンテスト中は方針が立たず
• 他の方のブログを読む
• DP
• 長さlenのバーコードを考える
• 全体の長さがlenで、長さL(X～Y)で白で終わるバーコードを考える
• 全体の長さがゼロまたはlen-Lで、黒で終わるバーコードがあればOK

結果

半年ぶりに参加。ゼロ完。

AはA問題らしくてとても良い問題だと思う。

Bはテスト不足。

Cは典型問題。こういうのをさくっと解けるようになりたい。

SRM 556

00:55

Div1 Easy (250) XorTravelingSalesman

問題

• N個の都市があり、それぞれの都市の値と、都市Aから都市Bへ遷移可能かどうかが与えられる。
• 別の都市へ移ると、現在の値と、移動先の都市の値のXORが現在値となる。
• 最初の都市の値を初期値として、最大値を求める。

方針

• なんか一見典型問題っぽい
• でも同じ場所に戻ってきたときに違う値になる
• 1024までしかないので、[都市数][値]の配列で全探索できそう
• 提出
• Failed System Test
• 問題文をちゃんと読んでなかった
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_556/XorTravelingSalesman.cpp

Div1 Medium (500) LeftRightDigitsGame2

問題

• N枚のカードが積まれている。
• 上から1枚ずつ取り、左か右に並べてN桁の数を作る。
• 生成可能な数のうち、lowerBound以上で最小の数値を求める。

方針

• 貪欲に置いたらできるのかな
• サンプル合わず
• おにぎりさんのを参考に、kusanoさんのを写経
• 原理はへーそうかという感じだけどこれは書けないな...
• 左から置いたのと右から置いたのがmixされるようになってる
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_556/LeftRightDigitsGame2.cpp

結果

x-- 0pt 414th rating 1378 -> 1319 (-59)

XORって色んな問題作れるんだなあと感心した。

SRM 555

19:24

Div1 Easy (250) CuttingBitString

問題

• ビット列が文字列で与えられる。
• 5のべき乗のビット列文字列に分割したとき、何個になるかを求める。

方針

• テーブル作ってメモ化かな
• まず文字列のテーブルを作る
• 5倍だから1倍と4倍=2bitシフトで足して作るか
• できた...時間かかりすぎ
• メモ化、若干バグる
• 提出
• Passed System Test
• (終了後)
• 50bitはlong longに収まるので数値でやればよかった
• 解きなおし
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_555/CuttingBitString.cpp

Div1 Medium (500) XorBoard

問題

• 0か1の状態を持つH×Wのセルがある。
• 行または列の反転操作の回数と、1の個数Sが与えられる。
• 何通りの操作があるか求める。

方針

• ちょうどSにするのが謎
• (終了後)
• naoya_tさんとkojingharangさんのを読む
• なるほど
• 個数に影響するのは、ある場所を奇数回反転させたとき
• 1回反転＋偶数回反転に分離して考える
• 1の個数は、行r回と列c回だとすると、s＝r×W＋c×H－2×r×c
• s＝Sかつ、残りの反転回数が偶数になる場合をループで調べる
• 行で考えると、r個の場合の数と、残りの偶数回の分配の場合の数の積
• 行の場合の数と列の場合の数の積
• 1回反転については、r個をH箇所に配る場合の数＝combination(H, r)
• 偶数回の反転については、(Rcount-r)÷2＝rrとして、rr個をH箇所に配る重複組み合わせ＝homogeneous_product(H, rr)＝combination(rr+H-1, H-1)
• combinationで計算できるが、(1555+1555÷2)≒2333の大きさが必要
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_555/XorBoard.cpp

結果

o-- 107.65pt 549th 1421 -> 1378 (-43)

点数悪いけど、解ける問題のときにプラス点なのはよい。

今回は裏onsiteということで喫茶店に集まって解いた。なかなか盛り上がってよいですね。

coding phaseが終わって他の人を見たら微動だにしてなかった。集中力のなさに反省。

mediumはさぼっていたけど、解けないと話題についていけないので、参加した回のは順次やっていくことにしたい。