pcad
解説読んでみてもまだもやっとしているので先にサンプルコードを移植してみる
変数がいっぱいあるから追っかけにくいんだな といっても単純にmapとかreduceになる形でもなさそう サイクルに分けるところと計算するところを分けたらどうかな ちょっとずつCPUとメモリがもったいないけど
荷物を重さの順にソートするんだけど、要素の交換のときに重さに応じた コストがかかり、トータルのコストが最小になるようにソートするというもの ALDS1_6_D: Minimum Cost Sort - kb84tkhrのブログ あきらめて解説を読む
二分木をpreorderで巡回した結果とinorderので巡回した結果を入力として受け取り、 その二分木をpostorderで巡回したときの結果を出力せよ ALDS1_7_D: Reconstruction of the Tree - kb84tkhrのブログ これ考えてみる ということはもっと狙いを絞ってつくら…
ざーっと記事を見直してみたやり残しはこの三つ 荷物を重さの順にソートするんだけど、要素の交換のときに重さに応じた コストがかかり、トータルのコストが最小になるようにソートするというもの ALDS1_6_D: Minimum Cost Sort - kb84tkhrのブログ 二分木を…
A*にとりかかるまえにちょっと試す 履歴をsetに覚えさせるあたりが重かった？ 幅優先探索＋マンハッタン距離の差分計算バージョンから 履歴を覚えてチェックするところを省いてみた 12番(15手)で比べてみると チェックあり： 01.59s、チェックなし: TLE(16秒…
反復深化とくらべて幅優先が遅いってことはない気がするんだけど IDA*のサンプルコードを参考にして直してみた
これだけやっても速くなるかもな 試してみよう
サンプルコードを読む IDA*のサンプルコードから
あきらめて解説を読む 反復深化 単純に深さ優先探索するとずーっと先まで答えを探しに行って戻ってこないので ある深さで探索を打ち切り、見つからなかったら1段深くまで探索する それって幅優先探索と比べたらどこがいいの？
こんどは普通に15パズル 計算量が上がっているのでありましょう ためしに8 Puzzleをそのまま15 Puzzle対応にしたら 18手の問題は解けたけど28手の問題でTLE 15手と18手でも大きく所要時間やメモリが異なっている 問題の制約として45手以内に解けることになっ…
といったところを考慮して書き直し 盤面を1次元で覚えたら見た目がだいぶすっきりしていい気分 ハッシュ関数は消して、盤面をタプルにしてからsetに入れてみた
前の記事で書けなかったメモを書いていく 解説やサンプルコードは意外とおんなじようなことが書いてあった 書き方は違うけど考え方は同じ（だと思う
なんとかAC出た 02.95s 84156KB解説読むともっとよくなるだろう
ふつうは15パズルなやつの3x3版 たぶん計算量がそれほどでもないって意味 ハッシュと幅優先探索を使う 幅優先はわかる この手のやつは深さ優先でやるととんでもない深みにはまって 帰ってこないということはこの間何かで教訓を得た ハッシュってなんだ何に使…
ここ put_queen(s, r, c) if rec(r + 1): return True unput_queen(s, r, c) 失敗したときは自前で状態を戻してるコピーを作って失敗したら捨てるだけにできるといいかなあ メモリはもったいないけど
解説を読む 1行にひとつしか置けないとか、 次の行にクイーンを置くときはまだ置かれてない列にとか、 8クイーン問題固有の事情をガッツリ組み込んである感じだな その方が速いんだろうな
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 自力でできそうな気がしませんね！ でも一度は自分で考える
1日寝かせてダメだったら解説読む ダメだった ていうか考える時間とMPが不足していた 星2.5個だし何か思いついてもいいかなあとは思ったんだけど どれどれ まず考えられるのが、すべての正方形について、その内部に1が含まれないかを調べるアルゴリズムです。…
マス目の中で障害物を避けてできるだけ大きな正方形を作る問題2次元のDPを使う表の中で上の要素と左の要素から現在の要素の値を求める うーんいろいろマス目に書き込んでみたけどどうもうまくいかない各マス目で、左にはどれだけ行けて、上にはどれだけ行け…
二分探索を自分で書いてみた版 ドンピシャの値じゃなくて、含まれる区間を求めるわけだけど どうも二分探索苦手 配列の範囲を飛び出ちゃったりとかする あっちこっちで1足したり引いたりしてるうちにごちゃごちゃしてしまう エラーもWAも出なくなったバージ…
このへんであきらめて解説を読みすすめるか 最初の考え方とは全然違うアプローチだった L[i]を長さがi+1であるような増加部分列の最後の要素の最小値とする配列 なんだかややこしい Lの最後の要素を更新していくっていうやり方じゃないんだな 読んでみても実…
わからなかったので解説を見る ふたつ考え方が載っていて、ひとつめは2乗のオーダで時間がかかるので使えない んだけどまずこっちを理解しよう L[i]をA[i]からA[i]までの要素を使いA[i]を最後に選んだ時のLISの長さとする配列 なるほど「A[i]を最後に選んだ…
最長増加部分列を求める ヒントの絵の意味が分からないなあ アイコンは1次元の動的計画法と二分探索 そうしてみるとヒントの絵も二分探索か 最長共通部分列ってのやったけどあれと似てるかなあ ちょっと違うかなあ あれは2次元の表作ったけど今回は１次元で…
