週報 20230827~20230902
振り返り
技術
以下印象に残った問題の感想
DFSするだけ。RubyだとO(NN!)は通らなくてキレてた。PyPyで通した。
この手の経路を1回だけ通るパターンの探索はDFSなんだけど通過済みの経路を探索する実装方法がパターン化してるので覚えちゃった方が手癖でかけるようになって良さそう。
code:rb
@g = Array.new(n) {[]}
@visited = Array.new(n, false)
def dfs(v)
dfs(v)
end
end
@visitedv = false # ここが結構ポイント。子を調べ切ったらfalseに戻す。こうすることで状態を管理する@visitedがグローバルに一つだけで済む。 end
あとはpermutationで全列挙して探索という手もあった。この場合はa->bへの経路を0(1)で繋がってるか確認しないといけないので下記のような感じでグラフを2次元で管理するのが正解だった。
code:rb
a,b,c = gets.split.map(&:to_i)
g = Array.new(n) { Array.new(n) }
m.times do |i|
end
選挙区 x 獲得議席数でDPテーブルを作り、ある獲得議席数を得るために必要な候補者の鞍替え数を最小化するように更新していく。作成したDPテーブルのうち選挙区全体の過半数となる議席数以上の中から最小の値になるものを探し出力すればOK。
最近のD問題にしては割と素直。こういうDP問題を1発で解けるようになってきたのは成長という感じがする。
グリッドの最短経路問題。概ねの解法はわかってたけど最後DFSしちゃった。グリッドの最短経路はBFS!!!BFSならO(HW)で済む。
結局ダイクストラとかグラフの最短経路問題と同じ。
ただ想定解法はRubyだと通らなかった。PyPyで通した。
グリッドを文字列比較じゃなくintでの比較にすれば通るらしい。そんな...
文字列比較を10**6とかやるとintでの比較と比べるとやはり差が出るらしい
さらに比較の数を減らした方がさらに良い
if a == 1 || a == 2 || a == 3よりif !(a == '0' || a == '4')の方が10**6とか比べると違いが出る
BFSの書き方も効率の良い書き方があった
queueから都度shiftしてpushしてを繰り返すより、まずはqueueに入ってるもの全ての処理をやって空にしてから次の段のqueueを処理するみたいなやり方の方が計算量が少なく済むっぽい
解き方の方向性は大体わかってたが、問題文で求めるべきものを読み間違えていたので実装に綻びが出ていた。与えられたグラフが全て連結していないと思ってしまっていたのが敗因。二部グラフのDFSで色付けて数え上げえてみたいなやつは分かってたんだけどな..。惜しい。
ハロプロ
ごっちん...
今週良かったインターネットコンテンツ
読書
ネガティブ・ケイパビリティというワードを切り口として陰謀論・SNS社会・ひろゆきみたいな昨今の流行りの風潮を語る本。このワード自体については個人的には明快な答えに飛びつかない能力という表現がしっくりきた。
「わかったというのは感情なのです」という一文が結構刺さった。ある分かりの種別の中の例として、数学は無機的なルールの羅列で進行するので結果だけしか得られず感情が動きにくいので苦手な人はずっとピンとこないままになる、みたいな話が面白い。
知ると分かるは別物というのも当たり前なんだけど、こう明確に分かるとはどういう状態かを認識できるようになると日常でも精神のコントロールに使えそうでよかった
自分の経験則を拠り所として年寄りの説教みたいな話を延々と繰り返す本。主張的にはショーペンハウアーの読書についてと似ているがおっさんの主観的な説教を読むくらいなら名のしれた哲学者(こっちもだいぶ っさんだが)の説教を読んだ方がまだマシ。 その他やったこととか考えたこととか
心理的安全性の高い組織、全員がギャルになれば良いみたいな話はある
20年ぶりくらいにポケモンカードGBをやってた。懐かしすぎてすぐ全部クリアしたが、当時はできなかったカードコンプリートをやっていきたいという気持ちが出てきてる。
コンプリートはチャンピオンになってからだと手に入らないカードがあることがわかり断念...