2018-08-01から1ヶ月間の記事一覧
難しいと感じたら今は飛ばして、実力をつけてから挑戦してみましょう。 ではお言葉に甘えて でもこの本でこの先にこの問題が解けるようななにかが出てくるのかなあ? で ALDS1_7_A: Rooted Trees ふむ 木を作るだけでよさそうだ でもサンプルデータを見てみ…
総当たりくらいしか思いつかないので総当たりを書いてみた コストがそれまでの最小コストを上回るか、ソートが成功するまで あらゆる手を試します 最初の最小コストはそこそこの値をセットしておかないと大変なことになるので 昨日のアルゴリズムで算出した…
ちょっと時間がない 普通にソートしてみてからその結果に持っていけるように交換順序を考える と 重いものから順に正しい位置へ で1次近似しよう
ALDS1_5_Dが思考★★★、実装★★☆だったのに対し、今度は思考★★★★☆、実装★★☆ 思考の星が1個半多い これはダメかもしれんね 荷物を重さの順にソートするんだけど、要素の交換のときに重さに応じた コストがかかり、トータルのコストが最小になるようにソートする…
ひとことで感想を言うと、身も蓋もない本、って感じ 人生は、運よりも実力よりも「勘違いさせる力」で決まっている 作者: ふろむだ 出版社/メーカー: ダイヤモンド社 発売日: 2018/08/09 メディア: 単行本(ソフトカバー) この商品を含むブログを見る 人間…
やっぱり挿入ソートベースじゃダメなのか じゃあマージソートかクイックソートかバケツソートか バケツソートは値が109あるからありそうにない なにか別の値に置き換えるっていう技があるかもしれないけど バブルソートや挿入ソートと見比べてみると、クイッ…
いずれ読もうと思ってた本いつもと違う図書館に行ったら置いてあったので早速借りてみたWeb上で読んだものも多いけど
あるいは挿入ソート的なやりかただけど二分探索してみるとか でも挿入するのにO(n)かかるとあんまり変わらないかもしれない やってみた
チャレンジ問題 数列AでA[i]>A[j]かつi
いわゆるバケツソート 原理は知ってた 解説はA,Bが1オリジンになってますが なんかA[0]とかB[0]が使われてないのが気持ち悪いので 0番目から詰めました
PythonのコードはVisual Studio Codeで書いてます インストールして特に何も調べずに使ってたので便利な機能を見逃して人生を損してるかもしれない ということでとりあえず@ITの記事をざっと確認してみました カスタマイズ方面にはあまり手を出さない方向で
前回の結果を使ってQuick Sort Stableかどうかも判定するんだけどアレだな バブルソートじゃTLEだろうからマージソート使うんだな 配列の値から数字を取り出すところはmerge_sortやquick_sortに 関数を渡すのかなと思ったけどそこまですることもあるまいとい…
今回も擬似コード翻訳すれば終わりなんだけどなんかややこしい ノートに絵を書いてみるまでピンとこなかった (解説見れば書いてあるんだけど)
擬似コードをそのまま書けばほとんど終わりだけどあえてイテレータで書いてみた こういう書き方で合ってるんだろうか 若干無理してる感あるような気も
まずは自力で2次元ベクトルのクラスを作ってみる add, sub, scaleを演算子のオーバーロードで書いてみるテストただしこの問題が解ける最低限で
図書館で借りた『Effective Python』をざっと読みました今の自分には優しすぎもせず難しすぎもせずちょうどいいレベルで使えそうな情報がいっぱい ジェネレータの仕組みを使ったコルーチンでライフゲームっていうのが面白かったなオブジェクトに明示的に状態…
昨日竜ヶ岩洞(りゅうがしどう)っていう鍾乳洞に行きましてこの暑さの中洞内は18度っていうこともあってか(なくてか)思った以上の賑わいでした車の行列もすごかったし(ウチは期せずして?ウラ技使ったような形でショートカットしてしまったんですけど) …
章が「再帰・分割統治法」でセクションが「全探索」なんだけど n重ループみたいな単純な全探索じゃないといけないんだろうか 普通に書くと再帰になってしまいそう 再帰を使って全部試せば全探索? ・・・絵からして再帰でよさそうだな
この問題はやや難しいチャレンジ問題です。 出た 思考★★☆、実装★★☆だから水たまりの問題より少し実装が難しいということか ぱっと見難しい最適化の問題かと思ったけど、ベルトコンベアーとトラックという 制限がついてるからなんとかなるのかな 荷物は出てき…
イテレータ イテレータってforとかで使ってるくらいで素では使ったことないな たぶん普通は素で使うことはないんだろう C++と見比べてみると C++ではend()と比較して、PythonではStopIteration例外を補足する これは前も見た サンプルのprint()をできるだけ…
「簡易的な」辞書って書いてあるけど、ただ配列にいれるだけじゃダメなんだろうね 100,000個で2secって書いてあるし 問題の並びや前にあった解説から空気を読んで配列に入れてハッシュ法でやることにする
今度は二分探索 ふたつに分けながら探すっていうことだけ覚えてる 1足したり引いたり終了の判定したりあたりの細かいことは書きながら考える 番兵は・・・いないよね?
ひとつめの数列の中に、ふたつめの数列に含まれる要素がいくつあるかを数える 線形探索って書いてあるからソートはなし? 要素数が10000個とか500個とかだから単純に二重ループでやればいいのかな お、こんなデータがある ループの順番に気をつけないと
AC取ったし解説読む ざっくり方針は同じにみえる データ構造の章に出てるっていうのがヒントになったし
小さな習慣を始めてから1年がたちました 振り返ってみてどうかな消えちゃったものもありますがだいたいは続いてますね増えすぎて整理したものもあります 腕立て伏せ1回っていう目標なのに今やジム通い、みたいな劇的な広がりはありませんがぼちぼちやってい…
スタックが空にならなくても水たまりが終わることがある 浅くなってきてた水たまりが深くなったらいったん水たまりが終わったことに するけれども、右側の底がもっと高くなったら「飲み込まれる」ような動きがいる と思って作り込んだのがこれ
さて しかしスタックだかキューだかリストだか知らんけど 使うとしたらスタックかなあ 何を積むか 計算量を増やさないようにするには、左から順番に1回見るだけで終わらないといけなさそう
※この問題はやや難しいチャレンジ問題です。難しいと感じたら今は飛ばして、実力をつけてから挑戦してみましょう。 どこが難しいんだろう? 水面の高さを覚えておいて、あと面積を足し算していくだけじゃない? 今水たまりの中か外か覚えておいて場合分けは…
標準のデータ構造でALDS1_3_A、ALDS1_3_B、ALDS1_3_Cを書き直しました すっきり