ABC201-Eを解いた。やはりDFSで十分解けた。
とりあえず求めるものは重みのXORの和なので、重みをビットごとに分けて解いて後で足せば良い。
まず適当な頂点を根として深さを計算する。注目している頂点xを端点として、もう一方の端点をより深い頂点とするようなパスを考える。全てのこのようなパスのdist(x,y)の和を計算するには、xより深いところにあってパスの重みのXORが1となるような頂点の数を求めれば良い。
そしてもう一つのパターン。注目している頂点xを経由して、両方の端点がxより深い頂点であるようなパスを考える。全てのこのようなパスのdist(x,y)の和を計算するには、xより深いところにあってパスの重みのXORが1となるような頂点の数と0となるような頂点の数を、xより1つ深い頂点ごとに計算してあればよい。
このような計算を全頂点に対してDFSでやっていけばどうにかなる。
ということで解いたのがこれ。
https://atcoder.jp/contests/abc201/submissions/28999754
しかし妙に遅い。なんで？
色々試してみても決定的なボトルネックが見つからず、全体的に重いんだろうという結論にしかならなかったので、想定解はなんなんだと解説を見てみたら納得した。
XORなので、寄り道をしようが同じルートで帰ってくればそれは全部打ち消される。(そしてこの問題は木なので同じルートでしか帰れない。)なので適当な頂点から重みのXORが0になる頂点の数と1になる頂点の数さえ数えればそれでもう解けてしまう。うわーーーすっきり。
「最短経路」という言葉に惑わされていた気がする。木だから寄り道しない限り最短だろくらいで思考停止していたけど、寄り道を有効活用する思考回路は無かった。でも思いつけてもおかしくはなかった気がするな。求めるものを等価でより扱いやすい形に変形すると良いかも、というのが教訓か。
ここ最近の昼飯は、なんかを買ってきて食べたり家のインスタント食品を食べたりしてなんとかごまかしてきたのだが、今日は財布が寂しくまた手ごろなインスタント食品も家になかったので適当なシリアル食品一杯でごまかそうとした。しかしこれが良くなかった。あまりにも頭が働かず体によくない。長めに昼寝をしてしまった後、たまたま残っていたごはんに卵をかけてかきこんだ。
自分はあまり料理が出来ないので、コロナで学食から遠ざかってからの昼飯は
- なんか買ってくる
- 家にあるレトルト食品やインスタント食品を食べる
- 冷蔵庫の残り物を食べる
- 朝飯を遅めにしてブランチとする
などでごまかしてきたのだが、生活習慣を整えて朝早起きするようになってからブランチの手は使えなくなったし、残りの手口もあまり続くものではない。
ちゃんと料理できるようになって昼から料理するか。
レポート課題が進まない。やるだけみたいな難度の課題ではないので時間がかかる。今日はたまたま授業がなかったのでめちゃめちゃに進めてやるぞと意気込んでいたのだが。
どうも「難しい問題」というか、「すぐに答えが分からない問題」に集中する力がずっと失われている気がする。というか能力が失われたというより取り組み方を忘れた。
とりあえず思いつく手を明日試してみるか。
- 頭に入れて歩き回る
- 時間を決めて「この間はとにかく集中する」ということにしてみる
- 問題を分割できないか思考し、出来ることからやる
- SNS他Webコンテンツなどの夾雑物を封印する
パッヘルベルのカノン弾けるようになってみたいな～という雑な思い付きでいろいろググってたら、良い感じのキーボードの練習サイトを見つけた。
https://ayakosan.com/c-lessonxx.htm
midi再生とか使ってるあたり古いサイト感はあるけど、中身は割と信頼できそう。
今日見たコンテンツ。
鍋に弾丸を受けながら 第7話
謎のハチミツ気になりすぎる…
ただでは死ねない葵ちゃん
https://www.nicovideo.jp/watch/sm39973940
このシリーズは編集クオリティが安定して高いので見やすいところもいいが、脚本がやっぱり面白い。
ポテトがSしか売ってない
https://www.nicovideo.jp/watch/sm39907185
普通に曲が良いんだが…
Categories: 未分類