pcad
予定通りTLE まずは lru_cache をつけてみる 引数がリストだとlru_cacheが使えないので タプルにしてから渡す
行列の積を求める時の掛け算の数を最小にするという問題 行列は微妙に苦手意識があるんだけれどもなぜかというとどっちが行で どっちが列か不安になるから、というくらい えーと行列の掛け算はと m行n列の行列×n行l列の行列は掛け算できて積はm行l列 その時…
やっぱTLEじゃないすかー ほかのひとのコードを見てみる 本のアルゴリズムで通ってるやつはないっぽい そして(細かくは見てないけど)けっこういろんな解き方があるっぽい
やっぱTLEじゃないすかー ほかのひとのコードを見てみる 本のアルゴリズムで通ってるやつはないっぽい そして(細かくは見てないけど)けっこういろんな解き方があるっぽい
やっぱりアルゴリズムの問題? 解説を読んだ 自分のコードに近い感じに読み替えるとこうか
最長共通部分文字列 TCCAGATGGと TCACAなら TCAAなんだって 途中がとびとびでもいいんだ 何か実世界の応用もあるのかな
heapqを使って
他の人のソースでも見てみるか 見てみたらみんなheapq使ってました 自分で二分ヒープ書いて通すのは無理なのかな
TLE! すみません解説見ます 解説見た ・・・同じじゃね?
やっぱり末尾から持ち上げていく感じ? でとりあえず書いてみた・・・
二分ヒープに挿入と取り出しをつけて優先度キューに仕立て上げようという問題今回は問題文にアルゴリズムの説明はない ということは、これまでのアルゴリズムを再利用するということかな?それとも説明するほど難しくはないということ? 一番単純な再利用は…
適当に数字を並べた配列を並べ替えてmax-ヒープを作ります アルゴリズムは書いてあるのでコードにするだけ 自分で考え出せるかというとそれはまた別の話
ここからヒープの話 ヒープというのは優先度付きキューを実現するための構造・・・らしい あまり知らないゾーンに入ってきた
解説の疑似コードを見る この問題でgetSuccessorを呼ぶのは必ず子が2つあるときなので、 右に子がいないときのことは考えなくていい気がする汎用的に次節点を求めるならこう書かないといけないんだろうけどていうか考えてなかった
いろんなケースでちゃんと動くことを確認しようと思ったら どれだけ書けばいいか見当がつかない こういう場合コンピュータの中の人に力づくでテストしてもらうっていうのは どうだろう
オンラインジャッジのテストケースは網羅性とか気にしないんだろうか まあ文句言ってても始まらないので軽くテストできるように書くか
そろそろ問題最後まで読むか 読む zが子を持たない場合、(略) zがちょうどひとつの子を持つ場合、(略) このふたつは問題なし zが子を2つ持つ場合、zの次節点yのキーをzのキーへコピーし、
削除したノードのところに(どっちでもいいけど)左の子をつなぎ直して、 右の子は左の子の右端のノードの右につなぐ だと、削除前より木が深くなっちゃったりするのでよくなさそう 左の子の右端のノードを削除したノードのところにつなぐ こっちで行こう
こんどは削除を追加 削除はすこしめんどくさそうな気がしている だからガイドらしきことが書いてあるけど見ないで考えてみる 削除したノードのところをつなぎなおさないといけないんだけど どこをどこにつなぎ直せばいいのかな
前回のプログラムにfind命令を追加します どれに追加しようかなまずは普通に作ったやつから
もっとがんばって関数型っぽい雰囲気を目指すとどうなるのか といっても入出力ありで関数型っぽく書くっていうのがどういうことなのか よくわかっていなかったりする Scheme手習いとかでは入力は引数だけ、出力は値だけだったからなあ
挿入のとき、最初の要素だけ特別扱いしてるのが気になった 番兵使えないかな?
チャレンジ問題 二分木をpreorderで巡回した結果とinorderので巡回した結果を入力として受け取り、 その二分木をpostorderで巡回したときの結果を出力せよ、というもの 見るからにパズルチックで問題のとおりにコード書けば解けるってものではなさそう どこ…
二分探索木に要素を挿入します コードは問題に書いてあるものに従います 親を覚えるようにしてるってことはどこかで使う予定ってことだろうなあ 挿入・検索では使わなさそうだから削除で使うかな?
今度は二分木を作ったあと、Preorder、Inorder、Postorderで 巡回してみるっていう問題 読み込むところは完全に流用でいいと思うけどあえて1から書き直す 不要な部分もあるし 一度書いたらすぐにもう一度書いてみるっていう勉強法があるらしくて なんかよさ…
今度は二分木 どっちかというと左子右兄弟表現とやらよりこっちのほうがシンプルで 先に出てきそうな気がしますがどうなんでしょう 同じようなことを書くのですいすい書けます
左子右兄弟表現で 意外と変えずに済んだところも多いかな
難しいと感じたら今は飛ばして、実力をつけてから挑戦してみましょう。 ではお言葉に甘えて でもこの本でこの先にこの問題が解けるようななにかが出てくるのかなあ? で ALDS1_7_A: Rooted Trees ふむ 木を作るだけでよさそうだ でもサンプルデータを見てみ…
総当たりくらいしか思いつかないので総当たりを書いてみた コストがそれまでの最小コストを上回るか、ソートが成功するまで あらゆる手を試します 最初の最小コストはそこそこの値をセットしておかないと大変なことになるので 昨日のアルゴリズムで算出した…
ちょっと時間がない 普通にソートしてみてからその結果に持っていけるように交換順序を考える と 重いものから順に正しい位置へ で1次近似しよう