kb84tkhrのブログ

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

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マスに置いたり置かなかったり、そのまま書くとすごい計算量になる?
コードの長さはいつもより少し長くなりそうな予感

続きを読む