電波ビーチ

☆(ゝω・)v

AOJ

重みつきUnion-Find木を解説

これを解こうとしてできなかったのでまとめた。 judge.u-aizu.ac.jp 重み付きUnion-Find 英語名はよくわかんなくてweighted union-find とか weighted union heuristic、weighted disjoint set dataみたいに言われてるっぽい。Union-Find木に「あるノードか…

AOJ ALDS1_6_C Quick Sort

ソートアルゴリズムの実装自体やったことないぜ!!!!!!!!!メリークリスマスイヴ!!!!!!!!! n 枚のカードの列を整列します。1枚のカードは絵柄(S, H, C, またはD)と数字のペアで構成されています。これらを以下の疑似コードに基づくクイック…

【AOJ】Rubyで2次元配列を連番で初期化 && Rubyでpythonのisdigitっぽいやつ

AOJ ITP1_6_B タイトルのやつでおいしい書き方ができずに少しハマった。 2次元配列を連番で初期化 map内での宣言で要素を初期化できる。範囲オブジェクトをto_aで配列にしてぶちこんだ。 cards = Array.new(4).map { Array.new((1..13).to_a) } => [[1, 2, …

mkdirで連番ディレクトリの作成

あらすじ 直近のABC107で1完だった。酒が入っていた&&出先で適当に暇つぶしのつもりだった&&時間が30分ほどしかなかったとはいえ、半年ほどろくにコードを書いてないだけでこれほどカスに成り果ててしまった。とてもかなしいのでAOJ Introduction fungosを…

Goで「文字列のa番目からb番目までを反転」をやる

そういう問題があったので。 Transformation | Aizu Online Judge func Reverse(s string, a int, b int) string { r := []rune(s) for i, j := a, b; i < (a+b)/2+1; i, j = i+1, j-1 { r[i], r[j] = r[j], r[i] } return string(r) } (a+b)/2+1でちゃんと+…

AOJ ALDS1_4 B BinarySearch

みんなだいすきバイナリサーチです。何度メモっても忘れる。 概要 二分探索 | アルゴリズムとデータ構造 | Aizu Online Judge ソート済み配列があったときそこにxが含まれているかどうか以外に、「xを最初に越える最小のy」とか「xを下回る最大のy」みたいな…

0-1ナップザック問題をメモ化再帰で思い出す

前回の続きというか書き忘れ or3.hatenablog.com DPは配列でやるのがよく入門でみかけるんだけど、最初に学習するときって順序的にはDFSからのメモ化再帰からのDPっていう感じのほうが理に適っている感じがある。なのでメモ化再帰バージョンを。 # 典型的ナ…

0-1ナップザック問題を思い出す

プログラマになりたいくせにしばらくプログラミングから離れていたらものの見事に忘れ果てていたので、基本に立ち返ることにした。まずはナップザック問題から。 0-1ナップザック問題 n, maxw = list(map(int, input().split())) v_lis, w_lis = [], [] # in…