問題概要 配列Xと配列Y(長さはともにN(

問題概要 平均値の最大化。

問題概要 8クイーンの正しくないかもしれない配置が与えられる(ただし、各行はちがうことが保証されている)。正しい状態にするには最低幾つ動かす必要があるか求める問題。 解法 n=8だったらnクイーンの全探索は余裕を持って間に合うので解を全て生成して距…

問題概要 ノード数V( 解法 Dijkstraした後距離の近い順にソートして確定させていく。

問題概要 G=(V,E)からG'を以下のように得る。G'=(V',E')とすると、V'=Eで、辺aと辺bがGで同じ頂点に接続していたら(a,b) in E'となる。今、グラフG[0]=(V,E)(|V|, |E| 解法 まず、|E|

問題概要(適当) 全探索すれば解ける問題。

結果。 2/5完。整理できてないままコーディングを始めると混乱すると分かっているのになぜ書き始めてしまうのか。 数学ゲーの方が簡単らしいけどグラフに逃げた。解けたので結果オーライだけど、戦略としてはよくない。

問題概要 頂点数N( 解法 ハッシュを使って、各ノードについて隣接する頂点集合を計算しておく。何故かローリングハッシュ風なハッシュ関数使ってる人多かったけど、順序関係ないんだし乱数列のxorや+で計算する方が楽だと思う。しかしハッシュを使っても重い…

問題概要 1~10^5の数字が書かれたフラグがある。最初は全てオフになっている。以下のQ( iをオンにする。ただし、既にオンになっていたり、他のオンになっている数字と互いに素でなければ素の旨指摘してオンにしない。 iをオフにする。ただし、既にオフになっ…

問題概要 長さL( 解法 何だか謎の制約があるらしいけど無視してDPで解く。文字列の先頭から考えて、dp[i][j] = (i文字目まで見て、残っている直前の文字がjであるような最小コスト)とすると十分間に合う。

結果。 2/5完。Aを後回しにしてBから解いたのはよくて、Cに飛び込んだのも悪くなかった。いずれも解法は割とすぐに見えたし、実装もそこまで大きくハマることはなかったんだけどCのTLEで死んだ。想定解法が(多分)O(N logN)なのにN=10^6ってちょっとひどいと…

問題概要 整数n( 解法 nを素因数分解してp_i^e_iが出てきたとき、これと同じ素数のべきで構成された数だけを使う。なので、まずそれぞれの要素を素因数分解してその約数でnを割り、割りきれなかったら即座に0を返す。割り切れないときはどのp_i^e_iが満たさ…

問題概要 長さN( 右の空のマスにずらす。 1つ右、2つ右にチェッカーがあって3つ右が空のとき右に3つずらす。 のいずれかをする。最右にチェッカーが来たら即消す。交互に動かして、動かせなくなった方の負け。勝つのはどちらか求める問題。 解法 なんか賢い…

結果。 久しぶりに2完。500遅すぎてひどいなーとか思っていたらみんなバタバタ落ちて順位はそこそこだった。でも前回落とした分を回収できていないのが辛い。 今回はチェックシートを用意して挑んだけど悪くなかった。何というか安心感が得られる。

問題概要 重み付き区間スケジューリング問題。 解法 DP。

問題概要 ノード数N( 解法 (直前に居た頂点、今いる頂点)を組にしたグラフを考える。後は行列累乗で計算するだけ。最初見たときはM

問題概要 長さN( 解法 重さと力の和が大きいやつから順に並べれば良い。

問題概要 ノード数V( 解法 Introduction to Algorithmsとかにも載っている問題。増加のクエリに答えるのは簡単。減少のクエリに対しては、該当する辺を含む閉路があればそれを除去して、閉路が無ければそれを通るようにsinkからsourceへ流量1を押し戻す。そ…

問題概要 辞書が与えられる。辞書内の文字のうち、辞書内のふたつの言葉が連結されてできたものを全て出力する問題。 解法 文字列の長さが短いので、どこで区切るかを各文字について全探索する。

問題概要 Fibonacci数を出力する。 解法 多倍長使うだけ。コード略。

問題概要 平面上にN( 解法 ビットDP。3点以上が角にくるような長方形がコーナーケースで前処理をかけておく必要がある。

問題概要 Suffix Arrayを構築する。 スコア制で、速いO(N)だと満点がとれる。自分のは蟻本準拠のO(N * log^2(N))で60点だった。ソートをバケットソートで書き直してもはやくならなかった。

ライブラリを書くときは名前の衝突を回避するため構造体か名前空間にくるんで書くことにしているけど、蟻本を参考にSuffixArrayを構造体で書いてみたら困ったことがあった。 struct Foo{ int as[10], ids[10]; bool cmp(int i, int j){ return as[i] < as[j]…

問題概要 C個の授業がそれぞれT箇所で開催されている。授業の疲労度と教室移動の疲労度が定義されているので、疲労度を最小化する問題。 解法 普通に状態を考えて普通にDPする。

問題概要 ノード数N( 解法 二分探索+二部グラフチェックする。

問題概要 a + b^2 = c^3 (mod K( 解法 bをNから1に減らしながらやる。BITのb^3 (K)のindexに1を加えて、[b^2+1, b^2+b]までのBITの区間和を足し上げる。このとき、K

問題概要 ノード数N( 解法 まず星グラフを考える。その後辺数が余っていたら頂点を一つ選んで既にあるクリークにその頂点を含むクリークになるように辺を追加する。First Acceptだったっぽい。

問題概要 山が3つあって、それぞれの山には石がx, y, z個置いてある。先手と後手の人が交互に以下のいずれかの処理をする。 xの石をひとつyの山に移す。 yの石をひとつzの山に移す。 zの石をひとつ取り除く。 xの石をひとつyの山に移し、zの石をひとつ取り除…

問題概要 ノード数N( 解法 まず、適当な点を根にしてLCAを持ち、オイラーツアーを計算しておく。また、始めて訪ねたタイミングと出て行くときのタイミングを記録しておく。このとき、10種類のBITを用いて入るときに+1、出ていくときに-1を加えるようにすると…

結果。 5/9完で8位。多くの人に解かれていた数学ゲー2問が解けていれば…。