Prime Number | Aizu Online Judge github.com

code-festival-2017-quala.contest.atcoder.jp 解き方 回文を作るのに必要な同じ文字の数を計算 各アルファベットの出現回数を計算 必要な文字数が多い場所から順に、条件を満たす最小のアルファベットを入れる貪欲 ここが嘘解法っぽさがある github.com

code-festival-2017-quala.contest.atcoder.jp 解き方 行、列を入れ替える順番は無視して良いので、何列、何行入れ替えるかで全探索 ハマったところ +=の副作用を見逃してた github.com

code-festival-2017-quala.contest.atcoder.jp github.com

競技プログラミング Code Festival 予選 結果 894th, 1679 -> 1640 (パフォーマンス:1287) 体調不良の時にratedなコンテストに出てはいけない。 その他 メンタルと体調がどっちも死んでた

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

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

E - Bichrome Tree 解き方 ある頂点iの部分木について、黒白それぞれの重みの和を、b_i, w_iとして、それを更新していく 黒白は入れ替えても問題ないので、違う色か同じ色かだけ考えれば良い 頂点iがleafの場合、色はどちらでもよく、重みはx_iになる 頂点i…

D - Restoring Road Network 解き方 これまでに追加した辺のコストの合計と、その辺による各都市間の最短距離(d[i][j])を保持、更新する 距離が小さい方から順に考えていく。 町i, j間の最短距離がcの時、 もし、d[i][j] == cならば、もう辺を追加する必要は…

C - Sugar Water 解き方 A, B, C, Dそれぞれの操作を何回するか、全探索 A, Bについては、100A <= F <= 30 * 100より、たかだか30回 C, Dについては、最大でF/2g溶ける（E=100の時）ので、たかだか1500回 合計で[tex:O(109)]なので、ダメでは？という気もす…

競技プログラミング ARC083 結果 97th, 1551->1679 (Perf: 2363) Cを3回WAしてダメかと思ったが、うまいことEまで解けた。 AOJ0189, AOJ2249, AOJ2200 蟻本練習問題。warshall floydだったりdijkstraだったり、最短経路問題の基本系 その他 金沢行ってきた W…

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

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

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

F - Sandglass 解き方 ある時刻におけるAの砂の量は、max(E1+C, min(E2+C, a+C))の形で表せる（aは最初にAに入っている砂の量） 各r_iについて、E1, E2, Cを前計算しておき、クエリに対しては二分探索→最後だけ計算 r_{i-1}のときの関数が求まれば、そこから…

競技プログラミング AOJ 2170 蟻本初級の練習問題。union find ABC073 87th 順調に解けた。 その他 特になし

D - joisino's travel 解き方 すべての町の間の最短経路の距離を事前にWarshall Floyd等で前計算 町の回り方をR!通りすべて試す（R<=8なので間に合う） github.com

C - Write and Erase 解き方 unordered_setを使えば良い github.com

B - Theater やるだけ github.com

A - September 9 数字として扱ったが、文字列のほうが簡単だった。 github.com

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

D - Derangement 解き方 となるiの個数を数える ただし、上記のようなiが連続している場合、その2つを入れ替えれば良いので差し引く ハマったところ 特になし https://github.com/HiroakiMikami/procon-workspace/blob/master/src/atcoder/arc082/d.ccgithub…

C - Together 解き方 差が2以下であれば、同じ数字にできる 差が2以下となる数字の個数の最大値を求める ソートして、尺取り法すれば良い ハマったところ 特になし https://github.com/HiroakiMikami/procon-workspace/blob/master/src/atcoder/arc082/c.ccg…

競技プログラミング ARC082 結果: 241st, 1475->1551 (Perf: 2005) その他 BitCoinは取引ログを1日分とった 開発記録はプライベートWikiでつける予定 ServerlessFramework勉強始めた