競技プログラミング/AOJ

DDCC2017 Qual D: 石

ddcc2017-qual.contest.atcoder.jp 解き方 南北、東西に対称となる4点それぞれについて場合分け 以下の2パターンのどちらかが答えとなる 東西方向に揃える→南北・東西両方に揃える→0個になるまで取り除いていく(最大となるように) 南北方向に揃える→南北・…

Tenka1 Programmer Contest 2017 D: IntegerS

tenka1-2017.contest.atcoder.jp 解き方 選んだ整数のorとしてありうる数字を列挙し、それらを満たす整数の集合を探索する ハマったところ xorとorを見間違えて最初苦戦した bit演算を使う場合、bitに対してfor文をまわすのを避けるべきではない github.com

AOJ 0009: Prime Number

Prime Number | Aizu Online Judge github.com

AOJ0005: GCD and LCM

GCD and LCM | Aizu Online Judge 解き方 ユークリッドの互除法 LCMは効率の良いアルゴリズムがあるらしいがよくわからない github.com

AOJ2224: Save your cats

Save your cats | Aizu Online Judge 解き方 pileを頂点、fenceを辺としたグラフを考えると、その双対グラフの最小全域木(コストは、fenceの長さ)を求めれば良い 双対グラフを求めるためには、最短閉路の列挙などする必要があり面倒 元の平面グラフの全域…

AOJ2200: Mr. Rito Post Office

Mr. Rito Post Office | Aizu Online Judge 解き方 からへの行き方は次の2通り 陸路で行く 船のあるところまで陸路で行き、船で適当なところまで行き、再度陸路 前計算として、陸路での最短距離、海路での最短距離をWarshall Floydで求めておく dp[i][j] = …

AOJ2249: Road Construction

Road Construction | Aizu Online Judge 解き方 captalを始点としてdijkstraして、その後経路復元 経路復元のための情報において、条件を満たす辺のなかでコスト最小のものを保存するようにする 多分、priority_queueを使ったdijkstraじゃないとTLEすると思…

AOJ0189: Convenient Location

Convenient Location | Aizu Online Judge 解き方 Warshall Floydして、町間の最短距離を求め、それが最小となるところを見つける github.com

AOJ2170: Marked Ancestor

Marked Ancestor | Aizu Online Judge 解き方 対応するMarked Nodeが同じ頂点が同じ集合に含まれるようなunion findを作る 一旦、最終的なunion findを作って、クエリを後ろから辿りながらunion findを更新する ハマったところ 同じノードに複数回マークつけ…

AOJ0525: おせんべい

おせんべい | Aizu Online Judge 蟻本初級の練習問題にあったので解いた。 解き方 どの行をひっくり返すかは、全部で2^R通りなので、これについてはすべて試すことができる。 ひっくり返す行を決めて、ひっくり返した後は、各列で裏と表のうち、多い方の数の…

AOJ0121: 7パズル

7 パズル | Aizu Online Judge 蟻本初級の練習問題にあったので解いた。 解き方 終了時点(綺麗に整列した状態)から幅優先探索を行い、各状態から終了状態までの最小回数を求める 状態の個数はたかだか8!個程度なので、この前計算は十分間に合う 各クエリに…

AOJ 0588: Cheese

チーズ | Aizu Online Judge 蟻本の練習問題に挙げられていたので練習 解き方 幅優先探索 N=9なので,Nそれぞれに対して幅優先探索しても,9*10^6程度のループ回数で済む ハマった所 最初,N=9を見逃して効率良い幅優先を考えていた コンテストだったらただ…