kb84tkhrのブログ

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

親戚故舊老少 筆いい感じ

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

ALDS1_13_B: 8 Puzzle (続き)

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

ALDS1_13_B: 8 Puzzle

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

ALDS1_13_A: 8 Queens Problem (続き2)

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

ALDS1_13_A: 8 Queens Problem (続き)

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

AtCoder Beginner’s Contest 141 感想

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

ALDS1_13_A: 8 Queens Problem

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

筆ほぼ復活しかし

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

NTL_1_B: Power

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

ALDS1_1_B: Greatest Common Divisor

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

ALDS_1_C: Prime Numbers (続き)

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

ALDS_1_C: Prime Numbers

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

DPL_3_B: Largest Rectangle (続き)

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

DPL_3_B: Largest Rectangle

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

千字文:親戚故舊老少 楷書だけ

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

Functional JavaScriptを読み始めた(どこまで読むかはわからない

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

DPL_3_A: Largest Square (続き)

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

DPL_3_A: Largest Square

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

DPL_1_D: Longest Increasing Subsequence (続き3)

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

DPL_1_D: Longest Increasing Subsequence (続き2)

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

千字文:親戚故舊老少

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

DPL_1_D: Longest Increasing Subsequence (続き)

わからなかったので解説を見る ふたつ考え方が載っていて、ひとつめは2乗のオーダで時間がかかるので使えない んだけどまずこっちを理解しよう L[i]をA[i]からA[i]までの要素を使いA[i]を最後に選んだ時のLISの長さとする配列 なるほど「A[i]を最後に選んだ…

意志の総量

意志の総量は決まってる、って読んだのは何だったかここんとこすごく実感している 2時間も残業して帰ると何もする気にならなかったりする何年か前まではそれが普通だったんだけど時間だけでなくて中身の違いっていうのも影響してるかな今は仕事中にMP消費し…

Grokking Simplicity 1-3章

まだ1-3章までしか出てないので 関数型プログラミングの話ってPure Functionが、公開関数が、再帰がmapが、副作用は避けよう、みたいなのが多いイメージだけどこの本は違うまず考え方から入る(というか考え方ばっかり 関数型プログラミングはActionとCalcul…

AtCoderをiPhone上で解いてみた

ちょっと最近、家でPCの前に座って勉強する時間が取れなくなってきているので通勤中にAtCoderできないかと思って試してみた やりかたとしては AtCoderの「コードテスト」で入力・実行してからコピペして提出Pythonistaで入力・実行して以下同文PythonAnywher…

『JavaScript: The Good Parts』読んだ

超いまさらながら JavaScript: The Good Parts ―「良いパーツ」によるベストプラクティス 作者: Douglas Crockford,水野貴明 出版社/メーカー: オライリージャパン 発売日: 2008/12/22 メディア: 大型本 購入: 94人 クリック: 1,643回 この商品を含むブログ …

DPL_1_D: Longest Increasing Subsequence

最長増加部分列を求める ヒントの絵の意味が分からないなあ アイコンは1次元の動的計画法と二分探索 そうしてみるとヒントの絵も二分探索か 最長共通部分列ってのやったけどあれと似てるかなあ ちょっと違うかなあ あれは2次元の表作ったけど今回は1次元で…

烹宰飢厭糟糠 もう一度

今日はなんかもうびっくりするほど穂先が割れて字を書くどころの話ではなかったという 墨を含ませている間にもう割れかけていて墨を取っていると生き物のように割れていく

AtCoder Beginner’s Contest 138 復習2

知り合いのコードがキューを使っててどっかで見た感じのコードだなと 思ったらグラフ関連のところで出てきたような書き方なんだな 無向グラフとして扱うわけだからそれも自然か ちょっと思い出しがてら書いてみる 深さ優先から スタックを使うからこれは普通…

MEAPでGrokking Simplicityという本を買ってみた

最近このPodcastを聞いています Thoughts on Functional Programming Podcast by Eric Normand 最初のエピソードから順番に聞いているんですが オープニングの音楽もなくいきなり Eric Normandです “A theory of Functional Programming”っていう本を書こう…