PCK2012.ソースは紛失しました。
問1 10問解いたら何点取れる？
- 10個の値の総和を取る。intで計算して良い。
問2 乗車券
- 問題文に書いている条件を実装する。if文が使えると解ける。
問3 家庭菜園
- あるやつが雑草だと決め打ちして取り除くと、残ったもので出来る数列が等差数列になっていれば、きめ打ちしたやつが雑草だと分かるので、その長さを出す。
- とりあえずなんか条件曖昧なので、一応、複数ある場合は最大の大きさのものを出力したら通った。
- 実装方法を間違えるとかなり苦労する問題だったらしい。周りの人が苦労していた。
- ていうか問題が曖昧らしい。
問4 すべての数は6174に通ず
- なんかタイトル的に、「同じ数が並んでいる以外必ず6174に通ずる」感じしたので、あまり気をつけない解法をした。
- とりあえずstringで持ちつつ、N="6174"になるまでwhile().使わなくても良いstringを使うことによるTLEが少し不安だけど、問4だし通るだろと思ったら通った。
- stringstreamとか使えると楽。N<1000のとき、上位桁を0で埋めるの忘れないようにしましょう。
問5 パイプつなぎ職人の給料
- K+1個のパイプを作ると仮定した場合、K個のジョイントを取り除いて、残ったものにその個数かけてやれば良いのだが、その時取り除くジョイントというのは小さいものから適当に選んでよい。
- 事前にソートをしておけば、それは高速に計算できる。
- O(N log N)
問6 マヤの大予言
- 見かけより簡単だよ。
西暦→マヤ暦
- 普通にループで西暦での経過日数を求めるとTLEしそうなので、400年周期とかで上手く計算量減らすor以下の関数を使って経過日数を求める みたいなことをする。
static long long getDays(long long y, long long m, long long d) { if(m <= 2){ --y; m += 12; } long long dy = 365 * (y - 1); long long c = y / 100; long long dl = (y >> 2) - c + (c >> 2); long long dm = (m * 979 - 1033) >> 5; return dy + dl + dm + d - 1; }
- getDays(y,m,d) - getDays(2012,12,21)すると経過日数が分かる。
- それをマヤ暦の１周期の日数)で余りを取ってやって、それをマヤ暦に変換する。
マヤ暦→西暦
- マヤ暦での日数は高々200万もないので、それを計算してから、西暦で日付進めるループ回す。うるう年に気をつけて。
問7 すごろくを作る
- ゴールにたどり着けない場合がある⇔遷移において、そのマスからどう頑張ってもゴールにたどり着けないようなマスにたどり着いてしまう。
- なので、はじめに全てのマスからゴールにたどり着けるかをO(N^2)でシミュレーションし、その後、スタートからそういうマスにたどり着いてしまうかをO(N)で確かめた。O(N^2)だと思う。
問8 ビートパネル
- "一度光ったパネルは押されるまで光が消えることはない"ので、「今どのパネルが光っている状態(2^16)で何小節目を見ているか(30)」でどの押し方を試すかを遷移として、bitDPすると速い。O(N･C･2^16)
問9 有限体電卓
ゴツいが、中身はただの四則演算。違うのはなんか有限体らしいことだけ。逆元の定義とかきちんとなされているので実装するだけ。
構文解析
逆元の計算
a^bを計算するには普通にループ回すとO(b)かかるが、二分累乗法というのを用いるとO(log b)で出来ます。これは知っとくべき。
問10 ねこまっしぐら(解いてないからかなり怪しい)
- 2^16通り餌を配置してみて、それがOKかどうか判定する。つまり多角形の辺上の全ての点からたどり着けるかどうか確かめる。
- 実際に↑は無理なので、有限個の可能性だけ確かめる。有限個の点に絞るために、
- 1.{元々の頂点}
- 2.{線分を直線としてみた場合の任意の2直線の交点のうち多角形の辺に乗っているもの}
- 3.{頂点同士を結んだ直線と、多角形の辺と交差する点}
- を考慮して、うまくやれば計算量は大きいが通るかもしれない。
