hotpepsiの練習帳

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はさぼっていたけど、解けないと話題についていけないので、参加した回のは順次やっていくことにしたい。