プログラミング
ABC 351 D - Grid and Magnet
かかった時間：時間切れ
昨日から解いてた問題。完全に実力不足だった。
どうでもいいけど問題設定が滑稽で好き。鉄の鎧を着て歩いていて、磁石にくっついて身動きが取れなくなってるの好き。
基本的にはグラフ探索なのだけど、計算量に厳しい問題だった。途中で解説を読んでしまったが、読まなかったら解けなかったと思う。
TLEになる要因で大きかったのは、seenのフラグ管理で2次元配列を使っていた点だった。問題になるのはリセットのときで、リセットのたびに盤面に応じた計算量がかかってしまう。結論、Setでやるのがよさそう。リセットはset.clear()でできるし、要素確認もset.has()でいける。
解いている時もSetを使おうと思ったのだが、(x,y)の2次元座標をSetで管理するのが難しいと考えて避けてしまった。これは、今回のようなグリッド問題においてはSetに格納する値をx*width+yという一次元数値に変換することで解決できた。以下の順でマスごとに一意番号を割り振っているイメージだ。
0 1 2 3
4 5 6 7
ABC 350 D - New Friends
かかった時間： 41:56
前段で351-Dを解いていたことにより簡単に正解できた。
最初の考察が的確だった。ユーザとフレンド関係はまんま無向グラフで、ブロックごとに分けて全辺数から既存辺を引けば出せる、と気づけたのがよかった。そして、ブロックごとの探索の実装は351-Dでやったばかりだった。今回の探索対象は1次元だったのでだいぶやりやすかった。
ただ、訪問済みのノードは探索をスキップする処理を抜かしており、一回TLEを出してしまった。もったいないところ。
余談だが、問題を読んだ感想は「こんなSNSあったらやだな」だった。AとBが友達、BとCが友達だからって、AとCを勝手に友達にされちゃうってことでしょ。陽キャの思想だ。
ABC 347 D - Popcount and XOR
かかった時間： 58:43
解く方針は早めに分かって、スイスイ実装できたつもりでいたけど、思ったより時間がかかってしまったパターン。D問題も一部解けるようになってきたので、そろそろ速さも意識していきたい頃合いか。
全体としては、以前に解いた問題でBigIntとビット演算に苦しんだおかげで、この問題では困ることなくビット演算を使えた。成長を感じた。
最後のテストケースが通らず、原因さがしと修正に10分くらいかかった。XおよびYの定義域オーバーによるものだった。定義域の外にある答えをはじき出してしまうケースははじめてだったので、新しい知見となった。
色彩検定
きょうは勉強しなかった。
きょうの一枚
晩ごはんのココイチ。
ここ数日元気が出ず全てにやる気が出ない周期が来ていたので、ごはん作りもサボってココイチで幸せを獲得した。ココイチって結構割高な印象だが、気にせず食べたいものをトッピング。手仕込みヒレカツおいしかったな。空腹でおいしいものをたくさん食べるのはやはり幸福度が高い。
自分のパフォーマンスが出ていないと自分を責めてしまいがちだけど、元気ないときこそ自分のご機嫌を取りに行くのだ。自分くらいは自分を甘やかす存在でいようじゃないか。
その他トピック
Youtubeでゴスペラーズのアカペラ曲のカバーを上げているのだが、数日前に再生数が急激に伸びた。うれしい。5月にも似たようなことがあったのだが、その時と同様で、某有名アイドルの方が会員制ブログでその曲が好きだと言及したらしい。世の中何が理由で自分のコンテンツが見られるか、分からないものだ。