TopCoder SRM 485(Div 1) - simezi

問題解けない→鬱→練習のモチベーションが下がる→問題解けない
の無限ループだよ！！

143.66 / Opened / Unopened
313位

1907->1848

ir5さんと一緒の部屋。
ir5さんは最近凄い勢いで問題解いてるので見習いたい。

ていうか僕も問題考えてる時間は長いんだけどね。。。
頭悪くて問題解けないんだよね。どうしたらいいんだろうね。

黒板に等差数列を書いたあと、全ての数について、2で割れるだけ割るという操作をする。
操作後の数列が与えられたとき、操作前の数列としてありうるもののうち、辞書順で最初に来るものを求めよ。

これは難問の予感。。。方針がさっぱり立たない。
これって答えそんな簡単に定まるんだろうか。
探索？

答えの数列が全て偶数の等差数列だと、
全ての項を2で割った数列も等差数列となるから、そのような数列は辞書順で最初ではない。
よってどこかの項が奇数。

まだ条件足りないよなあ。

答えの数列は32bitの符号付整数に収まる……とか書いてある。
うーん、この条件があるとどうなんだろう。
最初の項は最大でも32通りか。

なら1つの項に2をかける回数と、固定する項を決めてやり、後は帳尻を合わせられるか判定すればよい。

みんな続々と提出してる。嘘だろー！そんなに簡単かこれ？
System Testで結構やばいことになりそうな気がする。

書く。添え字が厄介でちょっと苦戦。書けた。
見直す。あー、帳尻をあわせる部分で、2のn乗倍か判定するはずが、倍数かどうかとか判定してた。危ない！

久しぶりのSRMだったので慎重になってたのがよかった。普段なら送ってリサブミットのパターン。見直してよかった。

グリッドの各マスの色が白または黒または'?'で指定されている。
'?'のマスの色は自由に変えることができる。
このとき、どの4点を選んでもそれが長方形にならないような色の選び方の総数を求めよ。
答えは64bit整数に収まることが保証されている。

ただし、4点が長方形になるとは、4点を(x,y),(x,Y),(X,y),(X,Y)としたときに
(x,y)から(X,y)までの全てのマス、(x,y)から(x,Y)までの全てのマス、
(x,Y)から(X,Y)までの全てのマス、(x,Y)から(X,Y)までの全てのマスの色が等しいことをいう。

うーん、DPっぽい……
でもサイズがでかすぎてこんなのやりようが……
マスが10x10でもDPかけねーぞ。。。マスが10x10で2x2の正方形がない、くらい制約きつくしないと僕にはDPが書けない。

時間まで色々考えたけど解けず。

落とせそうなのなし。
というかEasyみんなのコードがスパゲッティすぎて読めないのと、入力の制約がきつすぎるので殆ど誰もチャレンジしてない。これは酷い。

通った。通ったけど落ち込むなーこの順位。。。