これだけやっても速くなるかもな 試してみよう

今日は書道教室筆が割れるんですって言ってたひとに、根元のカタマリがなくなるまで洗ったら復活するかもよ、って言ってみた 楷書筆は何の問題もありませんつまり自分の腕前だけの問題

サンプルコードを読む IDA*のサンプルコードから

あきらめて解説を読む 反復深化 単純に深さ優先探索するとずーっと先まで答えを探しに行って戻ってこないので ある深さで探索を打ち切り、見つからなかったら1段深くまで探索する それって幅優先探索と比べたらどこがいいの？

こんどは普通に15パズル 計算量が上がっているのでありましょう ためしに8 Puzzleをそのまま15 Puzzle対応にしたら 18手の問題は解けたけど28手の問題でTLE 15手と18手でも大きく所要時間やメモリが異なっている 問題の制約として45手以内に解けることになっ…

といったところを考慮して書き直し 盤面を1次元で覚えたら見た目がだいぶすっきりしていい気分 ハッシュ関数は消して、盤面をタプルにしてからsetに入れてみた

ここんとこ筆の復活に力を入れすぎてかなやってなかったのでちょっと思い出して筆ペンで軽く練習しておく 筆ペンはすこし抑揚をつけづらい今使ってる紙は筆ペンだとすこし滲むからっていうのもある

まあ読まないだろうけどなにかのきっかけに手にとってくれれば、と思いつつ買ってみたらムスメががっつり食いつきました こども六法 作者: 山崎聡一郎 出版社/メーカー: 弘文堂 発売日: 2019/08/20 メディア: 単行本 この商品を含むブログを見る こども向け…

前の記事で書けなかったメモを書いていく 解説やサンプルコードは意外とおんなじようなことが書いてあった 書き方は違うけど考え方は同じ（だと思う

しっかり根元までガツガツ洗って、乾いたら櫛を入れる案の定抜け毛切れ毛がいっぱい その甲斐あってか書いてるときはほとんど抜け毛なし穂先もまとまっている

なんとかAC出た 02.95s 84156KB解説読むともっとよくなるだろう

ふつうは15パズルなやつの3x3版 たぶん計算量がそれほどでもないって意味 ハッシュと幅優先探索を使う 幅優先はわかる この手のやつは深さ優先でやるととんでもない深みにはまって 帰ってこないということはこの間何かで教訓を得た ハッシュってなんだ何に使…

ここ put_queen(s, r, c) if rec(r + 1): return True unput_queen(s, r, c) 失敗したときは自前で状態を戻してるコピーを作って失敗したら捨てるだけにできるといいかなあ メモリはもったいないけど

解説を読む 1行にひとつしか置けないとか、 次の行にクイーンを置くときはまだ置かれてない列にとか、 8クイーン問題固有の事情をガッツリ組み込んである感じだな その方が速いんだろうな

翌日が休日ってことでAtCoder Beginner Contest 141に参加しました 11時まで本気で頭使ってると翌日に響くんですよねえ 午前中とかの開催もやってくれないものかな 出る人いなくなる？

8クイーン問題、問題は知ってたけど解くのは初めてだなあ 思考も実装も星三つ けっこう難しい問題という位置づけなんだ 64マスに置いたり置かなかったり、そのまま書くとすごい計算量になる？ コードの長さはいつもより少し長くなりそうな予感

ネットで調べてみると筆が割れるのはやっぱり洗い方が足りないっぽいかなり洗ったつもりではあったんだけど洗えてないと根元に墨の塊ができて膨らんでしまうとか

べき乗 10^9乗なんてまともにやると大変なので m^2n = m^n * m^nという関係を使ってlog nのオーダにしてやる 余りを求めろとなってるのは a * b % q == (a % q) * (b % q)だから毎回余りをとってやればよかろう 1000000007で割るというのは32ビットで収まる…

最大公約数と言えば互除法 x, y = [int(x) for x in input().split()] while x % y != 0: x, y = y, x % y print(y) 一時変数を使わなくても変数を入れ替えられるのがうれしい

さてじゃあどうしよう 奇数偶数だけで分けるんじゃなくて、６で割った余りで分類することにすると 3000万回ループが節約できるな でもあんまりスマートな気はしない やっぱり１億までのふるいってのが無理あるのでは １億までの数の素数の判定だから、１万ま…

整数論の章に入りました 最初は素数判定 ヒントは一目瞭然でエラトステネスのふるい なんだけど 2 ≦ 与えられる整数 ≦ 10^8 1億までのふるい！？ メモリ制限65536KBってことは6500万バイトくらい 奇数だけ覚えることにすれば1バイトでひとつの数字を覚えてお…

やっぱりわかりませんでした 解説を見る 全探索のアルゴリズムでは時間内に答えを求めることはできません。 そうでしょうね 正方形を探すために用いたアルゴリズムも適用することができないため、別の方法を考える必要があります。 想定の範囲内

Largest Squareよりも思考・実装が星ひとつ以上増えてRectangle 自力でできそうな気がしませんね！ でも一度は自分で考える

今月のお題はいまひとつ感覚がつかめないので楷書だけに絞って練習 筆はやっぱり割れる ダメなのかまんなかが膨らんで中に空洞ができてる感じ毛がそうなっちゃってるってことかなあ 今回は墨をたっぷりつけて割れを防ぐ作戦その代わり速く書かないといけない…

これ Functional JavaScript: Introducing Functional Programming with Underscore.js (English Edition) 作者: Michael Fogus 出版社/メーカー: O'Reilly Media 発売日: 2013/06/03 メディア: Kindle版 この商品を含むブログを見る 日本語版だとこれ JavaS…

1日寝かせてダメだったら解説読む ダメだった ていうか考える時間とMPが不足していた 星2.5個だし何か思いついてもいいかなあとは思ったんだけど どれどれ まず考えられるのが、すべての正方形について、その内部に1が含まれないかを調べるアルゴリズムです。…

マス目の中で障害物を避けてできるだけ大きな正方形を作る問題2次元のDPを使う表の中で上の要素と左の要素から現在の要素の値を求める うーんいろいろマス目に書き込んでみたけどどうもうまくいかない各マス目で、左にはどれだけ行けて、上にはどれだけ行け…

二分探索を自分で書いてみた版 ドンピシャの値じゃなくて、含まれる区間を求めるわけだけど どうも二分探索苦手 配列の範囲を飛び出ちゃったりとかする あっちこっちで1足したり引いたりしてるうちにごちゃごちゃしてしまう エラーもWAも出なくなったバージ…

このへんであきらめて解説を読みすすめるか 最初の考え方とは全然違うアプローチだった L[i]を長さがi+1であるような増加部分列の最後の要素の最小値とする配列 なんだかややこしい Lの最後の要素を更新していくっていうやり方じゃないんだな 読んでみても実…

相当徹底的に筆を洗って臨んだ今回でもやっぱり穂先が割れる 硯にグリグリして根元まで下すような感じにするとすこし緩和されるかなあ筆によくなさそうだなーと思いつつ書いてる時間よりも穂先を揃えてる時間の方が長く感じたり