競技プログラミング

拡張ダイクストラのメモ

拡張ダイクストラ前回の問題で、拡張ダイクストラを使った。キューにぶち込む値の組を変えていくってことかな?普通のダイクストラの場合は、プライオリティキューに現時点での距離を先頭に、頂点をその次にしたリスト(or タプル)を入れる。これを拡張させた…

ARC 005 C 器物損壊!高橋君

qiita.com 続き。 atcoder.jp dijkstraでどうやってやんだよ...って思って、dijkstraの解答を探した。 ferin-tech.hatenablog.com 拡張ダイクストラとは????????????????????? 明日一通り調べよう... H, W = map(int, input().split())…

ABC 035 D トレジャーハント(2)

昨日の続きです。昨日は、考えでは、ダメなことがわかったので、解答を見た。考えは、だいぶ似ていた。ただし、最短経路上の単位獲得金額がでかい都市を探す必要がなかった。すべての都市を往復することで、経路上の単位獲得金額がでかい都市を特定すること…

ABC 035 D トレジャーハント

qiita.com 続き。 atcoder.jp 考えたこと 1 に戻ってくる最短経路をTから引いて、経路内で最も単位あたりの獲得金額が高い頂点を探して、そこで最大限いたことにするというものを実装してみた。結果的にダメだった。8割くらいACしたけど、残り2割がダメだっ…

JOI 2007 予選 F 船旅

qiita.com 続きです。 atcoder.jp これはすげー簡単だった。まぁ100点問題だしね。 コピペで瞬殺!!! import queue push = queue.heappush pop = queue.heappop INF = 10**16 def dijkstra(s, G, d): q = [] d[s] = 0 push(q, (0, s)) while q: cost, v = …

SoundHound 2018 予選 D - Saving Snuuk

qiita.com 続きです。 atcoder.jp ダイクストラな問題みたい。普通にわからんかったが。 editorial.pdfを見て実装してみる。 最後の出力が になってここがボトルネックになってTLEになっている。editorialにもここの処理書いてないやん。適当に検索したら、…

単一始点最短路探索アルゴリズム(1)

こんにちは、えぬわいです(普通) ダイクストラ法の復習です。 import queue push = queue.heappush pop = queue.heappop INF = 10000 from collections import defaultdict G = defaultdict(list) N, M, S, GOAL = map(int, input().split()) V = N d = [] f…

ARC 041 D 辺彩色(2)

自分の中で、けものみちが熱いです。 qiita.com 続き。 atcoder.jp 難しいなぁと思いながら、解説は理解できたが、実装がわかんなかったので、実装例を見てみた。 kmjp.hatenablog.jp お世話になってる kmjp さん!!!かっけー pythonで書き直し。 from sys…

閉路探索

前回の記事で、解説みると、奇数長の閉路を探索する必要があることがわかった。 閉路の検出ってどうやるんだっけなぁって思って調べた。 inzkyk.github.io わかりやすい。擬似コードも載ってる。確認する。 from collections import defaultdict G = default…

Maximum-Cup 2018 C 嘘つきな天使たち

最近努力が足りていないえぬわいです。 qiita.com 続きです。 atcoder.jp 2 部グラフで解けた。塗った時の数を記録していけば、おk。連結であることが保証されていないので、その点は気をつけた。自分で考えてACできるとちょーきもちー。 from collections i…

CODE FESTIVAL 2017 qualB C 3 Steps

俺ガイルとゲーマーズの最終巻が読めていないえぬわいです。今週は、全然解けてないですね〜。もっと解かないとな〜。 qiita.com 続きです。 atcoder.jp ワカンねぇな〜って思って、解説見たら問題の解釈が間違っていたみたい。 思い出した2部グラフの特徴と…

AtCoder ABC 126 D - Even Relation

ぼくがかんがえたさいきょうの生活習慣を送っているえぬわいです。3 日だけですけど。これから続けていくんだという気持ち。 qiita.com 続きです。 atcoder.jp ARC 036 D 偶数メートルのとっかかりの部分みたいな感じでした。たまたま偶数メートルの解説を読…

2部グラフ判定

アニマエールのOP・EDを聞いたら、見返す機運が高まってるえぬわいです。 今日は、蟻本に載ってる2部グラフ判定を自分で実装して理解しました。 ポイントとしては、 とりあえず、塗っていって判定する 塗ってる最中でダメだと思ったら打ち切る 色は、符号を…

ABC 087 D People on a Line

ストライク・ザ・ブラッドで好きなキャラクターは藍羽浅葱。えぬわいです。 qiita.com 続き。 atcoder.jp 重み付きUnionFind木というのがあるらしい... ノード間の重みを保存しつつ、縮約していくアルゴリズムらしい。 qiita.com けんちょんさんの記事を参考…

ARC 036 D 偶数メートル

qiita.com 続き。 atcoder.jp ARC D だけあって解答の読み応えがちげぇぜ(解答見た) UnionFindを使うと、状態管理をすることができる例。 UnionFindで N 個の頂点間を偶数距離で移動できるかの判定に使っている。解答みておったまげた。 class UnionFind(): …

ARC 097 D Equals

ポスター発表が終わりました。えぬわいです。 qiita.com 続きです。 atcoder.jp 概要 1 から N までの数列をシャッフルする。ある数字の組みが与えられるので、その組みの位置をスワップして、最大何個まで元の位置に戻せるかという問題。 考えたこと 組みと…

ABC 049 D 連結

qiita.com 続きです。 atcoder.jp 考察まとめです。 Union-Find木を使って解いてみる。まずTLEになったやつ。 class UnionFind(): def __init__(self, n=None): if type(n) == int: self.par = [i for i in range(n)] self.rank = [0 for i in range(n)] els…

ATC 001 B Union Find

人間は愚か。えぬわいです。 qiita.com atcoder.jp Union-find木の講座用の問題らしい。 Union-Find木とは グループの併合と判定ができるアルゴリズム 併合するのは、グループ同士、判定できるのは、ノード。つまり、グループは木で表される。 初期化 はじめ…

ABC 085 B Kagami MochiとABC 091 B Two Colors Card Game

setとmapを使う問題。 c++で set と map を使ったことがなかったので、調べてやってみる。 #include <cstdio> #include <set> using namespace std; // auto は型推論 int D[100], N; int main() { scanf("%d", &N); set<int> st; int d; for (int i = 0; i < N; i++) { scanf(</int></set></cstdio>…

DPのメモ

個人的なDPのメモ。 DPでだいたい最後にdp[0][K]みたいな感じで、0 添字で参照してるので、これをdp[N][K]みたいに書けるようする。というのが目的。 単純なナップザックの問題だと、dpテーブルの添字が何を表しているのか、読み取りづらい。結果的に、漸化…

aximum-Cup 2018 D Many Go Round(3)

結局こんな感じのDPを書いた。 INF = 10**9+7 def rec(pos, j): if pos == N: if j == L: return 0 return INF # pos 番目を使わない ans = rec(pos+1, j) ans = min(ans, rec(pos+1, (j+a[pos])%M)+(j+a[pos])//M) return ans ans = rec(0, 0) print(ans) p…

Maximum-Cup 2018 D Many Go Round(1)

ひとりぼっちの〇〇生活のカコちゃんがぼっちーの友達になりましたね。えぬわいです。 qiita.com 続き。 atcoder.jp 難しくなってきたなぁという気持ち。 1 日でなんとかするのは、きつい時期なのかなと。 DPを書く前に普通に再帰関数だけ書いてみてみる。 N…

ARC 057 B 高橋君ゲーム

おはやー!(天下ハナビ)。えぬわいです。 qiita.com 続きです。 atcoder.jp とりあえず、問題通り、再帰関数を書いてみる。 書いてみる。(ここでバグ見つけて無限に時間かかった) とりあえず、今日は、DPにできそうな再帰関数。 N, K = map(int, input().s…

飽きた

これは、報告兼けじめです。 重大な報告だと思った? 残念!!!重大じゃないです。 この前取り組んでた ABC 032 D ナップサック問題 これですけど、飽きたので、飛ばします。 以上、報告です。 バグ取りで、無理やなと感じたので、供養。南無。 #include <cstdio> #</cstdio>…

BC 032 D ナップサック問題

qiita.com 続きです。 atcoder.jp ナップザックを条件的にやるやつだと思います。 まだTLEなので、途中経過だけ書いておこうかなって。 ぬっ。 from collections import defaultdict N, W = map(int, input().split()) v, w = ([], []) for i in range(N): v…

AOJ 2502 VOCAL ANDROID

qiita.com 続きです。 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2502 サンプルケース通ったのに、ダメだったパターン。解答見ても謎。間違ってるところがわからないです。 わかる方いましたらコメントしてください。僕が喜びます。 WAコー…

Indeedなう C Optimal Recommendations

めっちゃトイレ行きたい。えぬわいです。 qiita.com 続きです。 atcoder.jp いい感じのDP問題だと思いました。 3 変数だと考えにくいので、2 変数で、DPテーブルを考察してみたら。サクッと行けました。 サクッと行けた。嘘です。入力のところで、dpテーブル…

AOJ Course Edit Distance (Levenshtein Distance)

好きなアニメは、旦那が何を言っているかわからない件。えぬわいです。 qiita.com 続きです。 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_E&lang=jp レーベンシュタイン距離というのがあるらしい。 手のつけ方がわからなかったので、w…

OJ Course Longest Common Subsequence

うるせぇよな。普通に。俺は好きなことを勉強したい。(仲間内のオタク構文) えぬわいです。 qiita.com 続き。 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_C&lang=jp 言わずもしれたLCS。 再帰から導いてできるかもと思ったらできな…

TDPC E 数

人と関わって成し遂げる事は難しいので、少なくとも一人でできることはちゃんとやろう。えぬわいです。 qiita.com 続きです。 atcoder.jp DP週間です。 考えたこと 再帰関数で、和を足していけばよい。と考えていました。結果的に、全ての数を捻出する方法が…