今日解いた競プロの問題。
ABC206-E: 自力AC。「$x/gcd(x,y)\neq 1$かつ$y/gcd(x,y)\neq 1$」はgを固定して全探索すれば容易だが、$gcd(x,y)\neq 1$なる$(x,y)$の数え方を思いつくのに時間がかかった。$x$を固定する全探索と$gcd(x,y)$を固定する全探索を考察したがどちらも上手くいかない。
図で考えてみると、$gcd(x,y)=g$なる(x,y)の組はxy平面上において等間隔$g$の格子状に分布することになる。これを$2\leq g$についてすべて重ね合わせれば$gcd(x,y)\neq 1$なる$(x,y)$の組が全て求められる。しかし数を数えようと思ったときは重複カウントが問題になる。
まず$p$を素数として、$p^n\ (n\geq 2)$、またはその倍数となる$g$については考える必要がない。$p=1$の場合だけカウントすれば良いからだ。つまり素因数分解したときにどの素数の指数も1となる数のみ調べることになる。これを思いつくのに時間がかかった。あとは包除原理を適用すれば良くて、$g$の持つ素因数の種類数の偶奇で場合分けして足し引きしていけば良い。なお、素因数分解周りはosa_k法かエラトステネスの篩を用いれば$O(\log N)$で済むので、全体$O(R\log R)$で解ける。
gcdの性質、というか整数の性質全般に関する知識が足りていないな。あと図で書いてイメージを湧かせるのをもっと早めに取り組めばよかった。知っているかイメージが湧けば比較的瞬殺な問題のはず。素因数の数ではなく種類数が問題になるとは思っていなかった。
結月ゆかり、東北きりたん、初音ミクを新しいPCの方にインストールし直した。ノートPCに入れてるよりも強いデスクトップに入れていた方が価値を発揮できるだろう。
以前にノートPCに入れたときはインストールに数十分かかった記憶があるのだが、なんかどれも数分～十数分で済んでしまった。ディスクドライブの読み出し性能が違うのか、CPUやストレージの速度が違うのか、両方なのか。とにかくサクッと済んで良かった。
ディスクドライブが動いている間妙に音が出る。ドライブの回転によってPCケース本体が細かく揺れているのは間違いないが、ケースの中から音がしているようにも思われないし、揺れているケースが他の硬いものに当たっているようにも思われない。よく調べてみると、固定の緩いケースのふたとケース本体が細かくぶつかりあって音が出ていた。ふたを手でぐっと本体に押さえると音が収まった。蓋と本体の間にちょっとスポンジなどを挟むと良い気がする。
酒井順子「男尊女子」を読み進めた。
最近の人は「嫁」と言っても「家の女」ではなく、フラットに「妻」とかと同じような言葉として使っている、それはそう。「嫁＝家の女＝差別用語」という意識は70年代ウーマンリブのあたりからという話は初耳だった。
でもある程度最近の人でも「嫁」という言葉を良くない言葉と見なしている人も見かけたので、その辺は人次第というか、その人の知識と価値観次第な気がする。
「服従」のくだりは本書の性質上男女の問題と絡めて話してはいるが、現代的にはもう男女関係ない話題な気がする。そして筆者も割とそれに勘付いているか分かっている節がある。「責任を持ち指図する側」と「責任を持たず服従する側」という構図、そして「責任を持つ側」は重圧から逃れるために「服従する側」に回りたい気持ちがあるというのは、個人主義とそれに付随する自己責任論が普及した現代だと割と性別問わず普遍的な問題のような。
古典的な性役割だと女性は「服従する側」だからその文法に則った「服従したい」→「無理やりされたい」が生まれるのはある種自然であって、この点においては男性が「服従したい」を表現するために歪んだ欲求を抱えがちなイメージがある。本書で紹介されていたSMも恐らくそうだし、あとは昨今のTSFものも若干それを含んでいるような。
新しいPCでキャプチャーボードの使用を試してみた。1080p60fpsで録画しているのにCPU使用率が3%を超えることがなかった。余裕にもほどがある。さすがハイエンドPC。
動画エンコード処理はさすがにCPU使用率が数十%とかになるようだが、その分の仕事はしてくれる。540fpsくらい出ていた。
今までキャプチャーボードは使いたいときにPCに繋ぐという使い方だったのだが、据え置きのデスクトップPCが来たことで常に繋げておけるようになった。いつでも配信が出来る。別に配信する機会そう多くないけど。
Categories: 未分類