今日解いた競プロの問題。
ABC224-E: 解説AC。自力でかなりそれっぽい解法まで行ったのだが、なぜか1WAが取れず、かなり悩んだ結果コーナーケースに気付けた。
https://atcoder.jp/contests/abc224/submissions/32494169
DAGを構築してdfsする嘘解法。あるマスから書かれている数がより大きい全てのマスに辺を貼ると$\Theta (N^2)$でTLEするので、書かれている数がより大きいマスの中で書かれている数が最も小さいマス一つに辺を貼っている。しかしこれではだめで、そのようなマスは複数あり得る。その中の1つだけに辺を張っても(運次第で)WAになってしまう。例えば以下のケースで落ちる。
2 3 4
1 1 1
1 3 5
1 2 5
2 2 10なお張るべき全ての辺を張ればおそらくTLEになるので、この解法は本質的に無理がある。(例: 同じ列にA=1なるマスがN/2個とA=2なるマスがN/2個並んでいる場合)
なお解説通りの解法の実装はすんなり通った。
ABC227-D: 解説AC。決め打ち二分探索に見えなかった…言われてみれば明らかに二分探索の可能性がある形式ではある。しかし気づいたところで決め打ち判定のアルゴリズムを思いつけていたかどうかは微妙。
プロジェクトの数を$P$とすると$P\times K$人は明らかに必要。$P$人以上の部署が$K$個以上あれば明らかに可能だし、全体の人数が$P\times K$人未満ならば明らかに不可能。問題はその中間で、人数は足りているがある部署に集中しているといった場合。
まだ思いつく道筋が思いつけていない。
酒井順子「男尊女子」を読み進めた。
カマトトというものは概念としては知ってるけどちゃんと認識したことないな。男である自分の目が節穴なのかもしれんが、女子のカマトトに対してだけでなく世の中全体に対して節穴な面があるので、自分が男特有の感覚というものの参考例になるかどうかは大分怪しい。
頭をよく見せるのと頭を悪く見せる二軸で生きるのは面倒そうだな～と思いつつ、カマトトを鬱陶しく思っていた筆者が「実際にカマトトをやってみて男子が引っかかってみると快感がある」と記述しているのには興味深く感じた。この筆者は女性の理屈に染まらないでいつつ女性の心に起こる現象を明瞭に記述してくれるので、男目線だと非常に良い理解の助けになる。
干宝「捜神記」を読み進めた。巻一28~31。不思議な女性の話が何篇か。
28「董永とその妻」がちょっと気に入った。主人聖人じゃん。でも奴隷は買ってるんだよな…(時代柄当たり前だが)
31「成公智瓊」に出てくる智瓊がちょっと面白かった。不思議な女が訪ねてきて「あなたの妻になりに来ました」までは昔話あるあるだが、「恩があってとかそういうのじゃなくてそういう運命なので来ました」「自分は神女なので子供は産めません」「(神女だから嫉妬とか無いので)あなたが他の女性をさらに妻にしても問題ありません」とか言うところが珍奇に感じた。正体をべらべら話すのもちょっとテンプレから外れていて面白いし「恩とかそういうのではない」というのもｱｯﾊｲとしか言いようがなくてちょっと滑稽で面白いし、他の女の人と結婚してもいいというのがなかなか聞かない話だ。妻になるけど子供は産めません、をデメリットにしないためというような気もする。
というか前提ルールをめっちゃ細かく話すのが普通に面白いんだよな。
今週のぷにるを読んだ。
相変わらずやべーやつなきらら先輩。コタローのこの思慕感情の源はなんなんだ。
アリスのルンルーンとの和解に向けたフラグが立った気がするが、どうなるんだろう。どこまでも純粋に無機質なロボットだし…
宮下紘「プライバシーという権利」を読み進めた。取り扱う概念の性質上仕方ないが、やや哲学的な方向に向かっている。
この辺を誤解していたのだが、公開情報もプライバシーとして保護されうるのか。本人が一度公開したものを消すのは難しいと思うので、そこに権利概念を持ち込んでも有名無実になりそうな気がするのだが、理屈として保証するべきであろうというのはまあ分かるといえば分かる。
「情報自己決定権」と「自己情報コントロール権」の違いは良く分からなかったな。後の章で詳説するようだから楽しみにしておこう。
いろいろこれまでに提起された理屈を読んだが、かなり面倒そうな思索をしてるな～と思った。
これは個人の思想なのだが、基本的に人間は情報を受け取ってそれに対応した行為を実行する自動装置だと思っている。この受け取る情報(行為を変える引数)の中には「自身の記憶」も含まれるし、「目覚ましの音」もあれば、「友達の呼び声」も含まれるし、「街中で見かけた広告」も含まれる。こうした引数たちに「これらは自己の内」「これらは外部」という線引きが出来れば「自己を構成する情報」と「行為する機械」のセットをまとめて「独立した個人」としてみなすことができるだろうが、実際にそこに明瞭な線をビッと引こうとするのはかなり厳しい。
プライバシーについて論じている人たちは、この辺の「自己」というものの曖昧さみたいなのに割と自覚的でありながらなお「それでも『個人』『自己』は定義可能でありそれは守られるべきものである」と信じて概念整理を行っているように見える。ようやるなあ、という気持ち。
自作PCを完遂するために久しぶりに秋葉原に行った。いつも電子部品を目的に行っているので、PCパーツを探すために行くのはほぼ初めてかもしれない。
部品を選ぶだけなら家でも出来るのだが、選ぶための(ちょっとやそっと調べても出てこない)勘所を質問するみたいなのはやっぱり店員さんに聞くのが一番良い。電機店のギークな店員さんの話好きなんだよな。
Categories: 未分類