kb84tkhrのブログ

何を書こうか考え中です あ、あと組織とは関係ないってやつです 個人的なやつ

pcad

ALDS1_9_C: Priority Queue (続き2)

TLE! すみません解説見ます 解説見た ・・・同じじゃね?

ALDS1_9_C: Priority Queue (続き)

やっぱり末尾から持ち上げていく感じ? でとりあえず書いてみた・・・

ALDS1_9_C: Priority Queue

二分ヒープに挿入と取り出しをつけて優先度キューに仕立て上げようという問題今回は問題文にアルゴリズムの説明はない ということは、これまでのアルゴリズムを再利用するということかな?それとも説明するほど難しくはないということ? 一番単純な再利用は…

ALDS1_9_B: Maximum Heap

適当に数字を並べた配列を並べ替えてmax-ヒープを作ります アルゴリズムは書いてあるのでコードにするだけ 自分で考え出せるかというとそれはまた別の話

ALDS1_9_A: Complete Binary Tree

ここからヒープの話 ヒープというのは優先度付きキューを実現するための構造・・・らしい あまり知らないゾーンに入ってきた

ALDS1_8_C: Binary Search Tree III (続き5)

解説の疑似コードを見る この問題でgetSuccessorを呼ぶのは必ず子が2つあるときなので、 右に子がいないときのことは考えなくていい気がする汎用的に次節点を求めるならこう書かないといけないんだろうけどていうか考えてなかった

ALDS1_8_C: Binary Search Tree III (続き4)

いろんなケースでちゃんと動くことを確認しようと思ったら どれだけ書けばいいか見当がつかない こういう場合コンピュータの中の人に力づくでテストしてもらうっていうのは どうだろう

ALDS1_8_C: Binary Search Tree III (続き3)

オンラインジャッジのテストケースは網羅性とか気にしないんだろうか まあ文句言ってても始まらないので軽くテストできるように書くか

ALDS1_8_C: Binary Search Tree III (続きの続き)

そろそろ問題最後まで読むか 読む zが子を持たない場合、(略) zがちょうどひとつの子を持つ場合、(略) このふたつは問題なし zが子を2つ持つ場合、zの次節点yのキーをzのキーへコピーし、

ALDS1_8_C: Binary Search Tree III (続き)

削除したノードのところに(どっちでもいいけど)左の子をつなぎ直して、 右の子は左の子の右端のノードの右につなぐ だと、削除前より木が深くなっちゃったりするのでよくなさそう 左の子の右端のノードを削除したノードのところにつなぐ こっちで行こう

ALDS1_8_C: Binary Search Tree III

こんどは削除を追加 削除はすこしめんどくさそうな気がしている だからガイドらしきことが書いてあるけど見ないで考えてみる 削除したノードのところをつなぎなおさないといけないんだけど どこをどこにつなぎ直せばいいのかな

ALDS1_8_B: Binary Search Tree II

前回のプログラムにfind命令を追加します どれに追加しようかなまずは普通に作ったやつから

ALDS1_8_A: Binary Search Tree I (続きの続き)

もっとがんばって関数型っぽい雰囲気を目指すとどうなるのか といっても入出力ありで関数型っぽく書くっていうのがどういうことなのか よくわかっていなかったりする Scheme手習いとかでは入力は引数だけ、出力は値だけだったからなあ

ALDS1_8_A: Binary Search Tree I (続き)

挿入のとき、最初の要素だけ特別扱いしてるのが気になった 番兵使えないかな?

ALDS1_7_D: Reconstruction of the Tree

チャレンジ問題 二分木をpreorderで巡回した結果とinorderので巡回した結果を入力として受け取り、 その二分木をpostorderで巡回したときの結果を出力せよ、というもの 見るからにパズルチックで問題のとおりにコード書けば解けるってものではなさそう どこ…

ALDS1_8_A: Binary Search Tree I

二分探索木に要素を挿入します コードは問題に書いてあるものに従います 親を覚えるようにしてるってことはどこかで使う予定ってことだろうなあ 挿入・検索では使わなさそうだから削除で使うかな?

ALDS1_7_C: Tree Walk

今度は二分木を作ったあと、Preorder、Inorder、Postorderで 巡回してみるっていう問題 読み込むところは完全に流用でいいと思うけどあえて1から書き直す 不要な部分もあるし 一度書いたらすぐにもう一度書いてみるっていう勉強法があるらしくて なんかよさ…

ALDS1_7_B: Binary Tree

今度は二分木 どっちかというと左子右兄弟表現とやらよりこっちのほうがシンプルで 先に出てきそうな気がしますがどうなんでしょう 同じようなことを書くのですいすい書けます

ALDS1_7_A: Rooted Trees (続き)

左子右兄弟表現で 意外と変えずに済んだところも多いかな

ALDS1_7_A: Rooted Trees

難しいと感じたら今は飛ばして、実力をつけてから挑戦してみましょう。 ではお言葉に甘えて でもこの本でこの先にこの問題が解けるようななにかが出てくるのかなあ? で ALDS1_7_A: Rooted Trees ふむ 木を作るだけでよさそうだ でもサンプルデータを見てみ…

ALDS1_6_D: Minimum Cost Sort (続きの続き)

総当たりくらいしか思いつかないので総当たりを書いてみた コストがそれまでの最小コストを上回るか、ソートが成功するまで あらゆる手を試します 最初の最小コストはそこそこの値をセットしておかないと大変なことになるので 昨日のアルゴリズムで算出した…

ALDS1_6_D: Minimum Cost Sort

ちょっと時間がない 普通にソートしてみてからその結果に持っていけるように交換順序を考える と 重いものから順に正しい位置へ で1次近似しよう

ALDS1_6_D: Minimum Cost Sort

ALDS1_5_Dが思考★★★、実装★★☆だったのに対し、今度は思考★★★★☆、実装★★☆ 思考の星が1個半多い これはダメかもしれんね 荷物を重さの順にソートするんだけど、要素の交換のときに重さに応じた コストがかかり、トータルのコストが最小になるようにソートする…

ALDS1_5_D: The Number of Inversions (続きの続き)

やっぱり挿入ソートベースじゃダメなのか じゃあマージソートかクイックソートかバケツソートか バケツソートは値が109あるからありそうにない なにか別の値に置き換えるっていう技があるかもしれないけど バブルソートや挿入ソートと見比べてみると、クイッ…

ALDS1_5_D: The Number of Inversions (続き)

あるいは挿入ソート的なやりかただけど二分探索してみるとか でも挿入するのにO(n)かかるとあんまり変わらないかもしれない やってみた

ALDS1_5_D: The Number of Inversions

チャレンジ問題 数列AでA[i]>A[j]かつi

ALDS1_6_A: Counting Sort

いわゆるバケツソート 原理は知ってた 解説はA,Bが1オリジンになってますが なんかA[0]とかB[0]が使われてないのが気持ち悪いので 0番目から詰めました

ALDS1_6_C: Quick Sort

前回の結果を使ってQuick Sort Stableかどうかも判定するんだけどアレだな バブルソートじゃTLEだろうからマージソート使うんだな 配列の値から数字を取り出すところはmerge_sortやquick_sortに 関数を渡すのかなと思ったけどそこまですることもあるまいとい…

ALDS1_6_B: Partition

今回も擬似コード翻訳すれば終わりなんだけどなんかややこしい ノートに絵を書いてみるまでピンとこなかった (解説見れば書いてあるんだけど)

ALDS1_5_B: Merge Sort

擬似コードをそのまま書けばほとんど終わりだけどあえてイテレータで書いてみた こういう書き方で合ってるんだろうか 若干無理してる感あるような気も