keyword 有向グラフ 強連結成分分解 C++ 問題概要 N( 解法 xとyが衝突したときxが消滅するならxからyへ辺を張る。このようなグラフを強連結成分分解してDAGに落とす。sinkの個数が答えとなる。

問題概要 H*W(H,W 解法 射影で確認できる個数をX,Yとすると、最小はmax(X,Y)。最大はX*Y。

解法 やるだけ。

keyword シミュレーション C++ 問題概要 次の関数Algrid2がある。 vector<string> Algrid2(vector<string> input){ int H = input.size(), W = input[0].size(); for(int i=0; i</string></string>

keyword シミュレーション C++ 問題概要 スタックに黒と白のボールが10^6個積まれている。一番上のボールを捨てる。捨てたボールが 黒: スタック内のボールの色を反転させる。 白: スタック内のボールの順序を逆にする。 スタックが空になるまで繰り返す。捨…

keyword 分割統治法 C++ 問題概要 長さN( 解法 分割統治法で処理する。各区間に対して、和を小さい方からN個返すようにする。mergeの部分は、N*(1/1 + 1/2 + 1/3 + 1/4 + ... + 1/N)で処理できる。 最初はpriority_queueを使ってdijkstraっぽく書いていたけ…

keyword 動的計画法 C++ 問題概要 2次元平面上にN(ForumによるとN 解法 x座標の小さい方から、dp[i][右への進路の直前の番号][左への進路の直前(正しくは直後)の番号]でDPすればO(N^3)で求まる。もちろんこれは無駄があって、2つ目と3つ目のどちらかは必ずi-…

解法 やるだけ問題。こういうのは３分くらいでちゃちゃっと書けるようになりたい。実装時間6分。

keyword グラフ 木 C++ 問題概要 ノード数N( 解法 葉から順次処理していく。処理した葉はグラフから取り除き、新たに生じた葉をキューに突っ込んでいけばよい。計算量O(N)。 枝をkeyにしてメモ化再帰でといても良さげ。

解法 さすがにこれはやるだけ。計算時間に余裕がある時は一番分かりやすく書くのがポリシー。累積和とか尺取り法で計算量落とせるけど無理しない。

keyword シミュレーション Java 問題概要(適当) レーンが2本あって泳ぐときは前の人を追い越せない。全ての人が満足行くまで泳ぎきるのにかかる時間を求める問題。 解法 配列を2本使ってシミュレーションするだけ。とはいえ、時間を1秒ずつ進めたりすると誤…

問題概要 N,M( 解法 反射の問題が出たら大抵鏡像を考えると上手くいく。スタート地点は一般にもっとも左のマスにあると考えて良いので、あとは座標(0,i)から撞いた玉がどこの(0,j)に行くのかを定数時間で計算すれば良い。左右の壁に2回当たったら戻ってくる…

解法 プレイヤーは二人かと思ったけど実際は一人。時刻と位置で探索するだけ。

解法 問題文とか全然読んでないけど書くだけというのはすぐ分かる。

keyword 動的計画法 C++ 問題概要 日程[i,j]( ⊆[1,365]), 金額wという予約がN( 解法 D=365とする。素朴に、dp[i日目][1つ目のホールが使い終わる日][2つ目のホールが使い終わる日]とすれば計算量O(D^3)位(本当はもう少し多いか?)で解ける。でも、2つのホール…

問題概要 長さ5000(=L)以下の数列がN( 解法 「珠玉のプログラミング」とかにも載ってる有名な最大部分和を線形時間で求める問題の応用。前から数えたときの最大部分和、全体の和、後ろから数えたときの最大部分和、単なる最大部分和、を各数列に対して前処理…

解法 約数は最大公約数の約数になっている。約数の個数なんてたかが知れているので全探索で十分間に合う。間に合うときは変に2分探索とかしない。

解法 問題文がちゃんと読めたらやるだけっぽい。

解法 sprintfとsscanfでがりがり書いた。もっと楽な方法もあるかも。

問題概要 unsigned 64bit整数A,Bが与えられる。A=X+Y, B=X^Yを満たす非負整数X,Yのうち、Xが最小のものを求める問題。 解法(DP) 式変形して、A=(B^X)+Xなので、次の状態のDPで解いた。dp[i][Xのiビット目は0or1][Xのi-1ビット目は0or1][(B^X)+Xを計算したと…

問題概要 ２次元平面上にN( 解法 まず、線形性からX成分とY成分は完全に分離して考えてよいことが分かる。 S:=Σ{x[i]^2}, K:=Σ{x[i]}とすると、各jに対して、Σ_i{(x[j]-x[i])^2}=Σ_i{x[j]^2 + x[i]^2 - 2*x[j]*x[i]} = Σ_i{x[i]^2} + N*x[j]^2 - 2*x[j]*Σ_i{…

keyword 平面走査法 座標圧縮 C++ 問題概要 X軸に平行あるいは垂直な線分がS( 解法 まず座標圧縮する。その後は平面走査法でx座標の小さい方から舐めていく。計算量O(S^3)。

keyword 反復深化 Java 問題概要 あるルールα→βというルールがN(JavaでいうところのreplaceAll(α、β)という作用である。文字γをδにするのに必要な最小回数を求める問題。できなければ-1を出力する。1 解法 何か数字がやたら小さいし探索臭がするので反復深化…

keyword 動的計画法 C++ 問題概要 長さL( 解法 dp[i文字目][書き換えた回数][i文字目に何が入っているか]でDP。状態がL*K*26で、ひとつの状態から他の状態に配るのに26だから計算量はO(L*K*26^2)。dpの2つ目は"書き換えられる残り回数"とするより"書き換えた…

keyword 実装 C++ 問題概要 N(=0)点が与えられる。最終ラウンド終了時に、あるチームが取りうる順位の上限と下限を求める問題。同じ得点のときはチーム名の辞書順比較が入る。 解法 setとか使って書くだけ。M位以下の人には0点が与えられると考えたら少し楽…

keyword 数学 C++ 問題概要 3辺がX,Y,Z( 解法 和が一定のときに積を最大にする問題。当然、バランスが取れているほど大きくなる。一辺をいくつに切るかで全探索して、残りは半分に近い大きさで切る、という方法で通った。 もっと賢い(分かりやすい)方法もあ…

keyword メモ化再帰 greedy C++ 問題概要 ノード数200以下の有向木が与えられる。以下のゲーム(一人用)をする。各ターン毎にプレイヤーは以下のいずれかの行動をとる。 葉に石をおく。 葉でないノードpに対して、全ての子(not 子孫)に石が置いてあるならば、…

問題概要 原子量と分子式が与えられるので分子量を求める問題。 解法 構文解析するだけ。BNFは := | ε := | | '(' ')' 厳密にはこれだと元のBNFと異なる( ()2などが有効と判断される )けど、入力が正しいと保証されてるので問題はない。実装時間約20分。

keyword 動的計画法 C++ 問題概要 CodeForces形式のコンテストで時間内に最大何点取れるか求める問題。 解法 ある2つの問題を、どちらを先に解けば良いか考えたとき、初期点数をM、必要な時間をR、減少率をPとすると、iよりjを先に解いた方が得点が高い⇔M[i]…

問題概要 "%09d"で表示されるくじが無作為に1枚選ばれる。長さ9以下の文字列が複数与えられ、どれか一つでも末尾が一致していたら賞金がもらえる。賞金がもらえる確率を求める問題。 解法 与えられた文字列のうち、他の文字列を接尾語に持つものは削除すれば…