Codeforces
問題概要 bool演算を考える。ビット演算で定義されたm変数関数f(x1,...,xm)がある。n個の変数X1,..,XN(2 解法 まず、f(0,0,...,0)とf(1,1,...,1)の値が異なるなら当然YESになる。 今、fが恒真(or恒偽)関数だとする。この場合は当然NOになる。そうでないとき…
結果。 1完。数学っぽいBを無視してCをやっていたけど結果的に戦略としては失敗だった。でも、代わりに取り組んでいたC問題は面白かったし方針もそんな悪いわけじゃないのでまあよかった。
問題概要 頂点数V( 解法 最大次数2以下と聞いた瞬間に線か環になることに気づくので、後は奇数長の閉路の個数+(残りの点数)%2が答になる。
問題概要 六角形のタイルを敷き詰めて六角形を作る。このとき各辺は向かいの辺と長さが等しい。その長さa,b,cが与えられるのでタイルの個数を求める問題。 解法 図をじっと眺める。b*cの部分を取り除くと厚さ(a-1)の層が残る。
問題概要 K( 解法 digital rootはmod (K-1)で考えればよい(0に注意)。後はmapに累積和を詰め込みながらカウントすればよい。B=0やB=K-1のときにdigital rootが0の場合とK-1の場合をちゃんと区別するようにする。
問題概要 長さN,Mが周期的に現れる点線がある。点線をいくつか選んでどの区間も最大K個以上被覆されているようにしたい。また、端同士で境界ができたらそれは別の線分でカバーされている必要がある。最小いくつの点線を選ぶ必要があるか求め具体的に構成する…
結果。 4/5完。CとEの実装に時間がかかった。Bもバグを生みやすい方法でやってしまったのはまずい。デバッグは結構うまくやれていたと思う。
問題概要 整数xを2進表記して、その文字列表現が長さ2以上の周期を持っているときxを周期的と定める。[L,R](L,R 解法 定石通り[1,X]に帰着させる。各長さごとにそれぞれ独立に考える。長さを固定すると、これは蟻本でも紹介されているメビウス関数を用いて数…
問題概要 配列に、各要素にある値を加えて置換or各要素にある値をxorする作業をr( 解法 全探索する。ただしxorを2回繰り返すのは元に戻るだけなので探索しないようにする。こうすると計算量はF_30 * 長さくらいになって間に合う。
問題概要 多項式がふたつあたえられるので、f(x)/g(x)でxを無限に飛ばしたときの収束先を求める。 解法 最高位の係数だけを見れば良い。
問題概要(適当) 長方形の中に円を敷き詰めるゲームでどちらが先に置けなくなるか求める。 解法 1個も置けないときだけ先手負けでそれ以外は先手勝ち。
問題概要 N( 解法 ある島を基準にして、右(or 左)に行って何回橋を渡れるか、を戻ってこれる場合と戻ってくる必要がない場合に分けてそれぞれdpで計算すればよい。
問題概要 H*W(H,W 解法 sum_{i,j} X[i,j] * ( (x-i)^2 + (y-j)^2 ) = sum_{i} ( (sum_{j} X[i,j]) * (x-i)^2) + sum_{j} ( (sum_{i} X[i,j]) * (y-j)^2 )なのでxとyをそれぞれ独立に考えればよい。
問題概要 n*nの行列Aで、A[i,j] = 0 or 1、1のマスは互いに隣接しない、A[i,j] = A[i, n-j+1] = A[n-i+1, j]であるようなものを考える。1の個数がx個あるようなもののうちnが最小のものを答える問題。 解法 偶数だと稼げないので奇数だけ考える。このとき、…
結果。 久しぶりに0完だった。問題読んだのはAとCで、Aは場合分け地獄にハマってしまった。Cは細かいところまで詰めることができずに通すことができなかった。最近はちょっと前に比べてWA率がとても高いのでもう少し細部まで考えるようにしないといけない。
問題概要 サッカーのグループリーグを抜けるのに要求されるスコアを求める問題。 解法 これまでの結果から得点に大差はつかないことが分かっているので、スコアについて適当な範囲で全探索する。基本的には実装ゲー。
問題概要 平均値を求める問題。
問題概要 原点のまわりを衛星が角速度Vp/rで等速円運動している。ロケットと衛星の初期位置が与えられる。ロケットは速度V(>Vp)で移動できる。原点から半径R以内に入らないようにして衛星までたどり着くには最小どれだけの時間が必要か求める問題。 解法 V>V…
問題概要 高さn( 解法 幅優先探索するだけでよい。
問題概要 N*M(N,M 解法 各(x, y)について、それより左側にある最小の空きマスと、それより右側にある最小の空きマスを計算しておく。各クエリに対しては、xについて全探索すれば計算量O(K*M)で目的地を見つけられる。また、データの更新は目的地のx座標を持…
結果。 3/5完。難しめの問題に挑んでいたけどなぜかTLEがかなり厳しい問題で落ちた。結果やさしい問題解くのが遅れて順位はひどかった。
問題概要 f(x)=k*x+b(1≦k, b 解法 fが狭義単調増加であることから、f^n(1)≦f^a(t)はf^(n-a)(1)≦tと同値。したがってf^(n-a)(1)≦tを満たす最大のn-aを求めればよい。ただしaは非負。
結果。 2/5完。いつものことながら、正確に実装しきれない。AはHackされたおかげでミスに気付いたけどこれはかなり必然的なミスだった。こういうの落とすのは良くない。
問題概要 ノード数N( 解法 木を適当に根を選んで根付き木にする。その後適当に1点選んで、それ以外の点を角度でソートして各部分木のサイズごとに再帰的に割り振る。
問題概要 H*W(H,W 解法 8近傍にマップを拡大しておき、そのマップで探索する。同じ中で新しいマップにいくことができたらそのような遷移を繰り返して無限に遠くに行くことができる。1500^2*9でちょっと恐いがcharなので十分メモリは足りる。探索はDFSだとス…
問題概要 長さL( 解法 辞書式順序に対して、a+max(b,c)=max(a+b,a+c)が成り立つという事実を使う。後ろから見れば貪欲が効く。
結果。 1/5完。長さLの文字列をとるのに配列の長さを+1していなかったという信じられないミスをしてしまった。こういうミスが起こるのは集中力が絶望的に足りていないからだし、そもそも最近はあまり真摯に問題に向き合っていない気がするので、気合いを入れ…
acceptされたコード 長さN( 解法 両端の要素が同じでその範囲ではその数がちょうどK回現れるような区間を列挙する。その区間を右端でソートして小さい順に重複しないように数え上げていけば解ける。BITなどを使っても解けるっぽい？
問題概要 H*W(H,W 解法 1の個数が2以下だと無理。それ以外の時、どれか1ヶ所変えて非連結にできるかどうかを調べる。これは全探索でよい。1ヶ所変えて無理だったら答は必ず2になる。
結果。 2/5完。Bが一番簡単だった。AでHack祭りだったけど自分も2回Hackされた。残りの時間ではずっとCを考えていて、場合分け多めにならざるを得なかったので慎重にやっていて提出したらWA。サンプル1すら通っていなかったので不思議に思っていたら問題を2…
