/ 最近 .rdf 追記 設定 本棚

脳log[2021-10-09~]



2021年10月09日 (土) 「暑いのに動いてない」なくすエアコン、シャープが発売 設定温度に達した後の湿度上昇防ぐ - ITmedia NEWS」■これは、冷やし終わっても止まらず電気を食い熱を生み続けるエアコン。「冷風を送り出すファンの回転数を抑えることで、室温を下げずに平均湿度を従来機に比べ約12%下げる。」 冷やすことが目的ではないけど除湿のために冷房運転をするからこういう制御になるんだけど、結果は室内の温度ムラを生む。除湿運転によりホットスポットができる。そうするとマッチポンプなんだよ。室温がコントロールできていると思うならあとは除湿ではなく送風を頑張るのがいいと思う。実はコントロールできていませんでした(だから暑い)ということが明らかになったりもするだろう。都合のいいことに消費者の多くは室内機のファンの音をエアコンが仕事をしている音だと思っていると思う。■すべての不満は部屋に対してキャパシティに余裕のあるエアコンを選ぶことで解消するのかな、と考えないではない。


2021年10月05日 (火) 自分のおばあちゃんくらいの世代の人が「行かれる」とか「歩かれへん」という言葉を使っていたイメージがある。行かれるは可能以外の用法も考えられるが、歩かれへんは歩けない以外の意味は考えられない。自分世代なら歩けへんと言う。最近こういう記事を見かけたが(「「ら抜き言葉」で抜かれているのは「ら」ではなかった?「目から鱗」「言われてみれば確かに」 - Togetter」)、ら抜きが行き過ぎた可能動詞化だとすれば、これらは可能動詞以前の形態だと考えられる。『ちいさい言語学者の冒険――子どもに学ぶことばの秘密』という本がある(未読だけど)。子供にとって(たぶん日本語学習者にとっても)歩ける、走れるからの推測で食べれると言ってしまうのはある種の必然なのだろう。自分が小学生の頃は食べれるは食べられるの間違いだと目くじらを立てるくらいにはら抜きが使われていたし、だけどら抜きで何が悪いと開き直れるほどには広がっていなかった。普通一度訂正されたら一生守るよね。二度目は死ぞ。自分は本で読んだ言葉、教科書に書かれていた文法を重んじているが、自然言語はプログラミング言語などと違い文法は後付けの解釈だ。言葉も教科書も移り変わり正解はひとつではない。ATOK では送り仮名を必ず本則に設定するのだが、それ以外が間違いというわけではない。ら抜きは拙く聞こえるしダサいので絶対使わへんけどな! たとえ風俗を写し取るためだったとしても、本の中で使われていたら読み進めるのは苦痛だ。だけど自分から見て上の世代の人がら抜き言葉を話すのもまた、テレビで垣間見える世間で当たり前の光景なんだよね。口語はすっかりら抜きに席巻されてしまった。自分を中心に置いて上と下を見ると時代の流れがわからなくなる。聴覚優位で下の世代の人間はら抜きしか聞こえてこないのでら抜きが当然。では上の世代の人間は? 自ら変化していった? 変化に取り残される人間もいる。省略と拙速は「お嬢様」には似つかわしくありませんことよ。でもさ入れは嫌かも。


2021年10月04日 (月)

最終更新: 2021-11-04T10:11+0900

[AtCoder] AtCoder Beginner Contest 221/F 問題 Diameter set

精進ですよ。おとといあった ABC の F 問題。

コンテスト時間中は木の中心についての理解がぼんやりで解答に至らなかった。そもそも木の中心などというものを考えたことがなく、でもサンプルの2のような円形の木で制限時間内に答えを数えきるためには、木の中心を中心とした組み合わせを考えるしかなかった。

木の直径については知っている。過去にある問題で満点解答のためのヒューリスティクスとして、深さを求める関数を2度呼び出して答えとしたことがあった。後にそれが運任せではなく確かな手段らしいことを知った。証明は知らない。

木において辺とは頂点集合を左右に分けるものだということを知っている。どの辺でもいいので1本選んで真ん中に横向きに置いて形を整えるとアレイ(亜鈴)型になるイメージ。コンテスト中には思い出せなかった。そのせいで問題の木を具体的にイメージする力が弱かった。このことは今朝のトイレで考えるでもなくふと思い浮かんだ。

たとえば直径が偶数の時、直径の中心には頂点が1つある。問題は直径を与える頂点ペアが複数あるときに中心が複数あるかどうか。中心が仮に2つあるなら、2つの中心の中点が本来の中心であるべきであり、直径だと思っていたもの、2つの中心だと思っていたものは直径でも中心でもなかったことになる。だから中心は1つ。

たとえば直径が奇数の時。直径の中心には1本の辺がある。この辺は中心に位置する唯一の辺だろうか。仮に直径の中心に位置する辺が2つあるなら、2つの辺の中点が本来の……(略)。だから中心は1つ。

色の塗り方だけど、中心から最も遠く半径と同じだけ離れている点の集合を、中心から直接出るどの頂点の先にあるかで分類する(中心が辺なら辺が結ぶ2つの頂点を考える)。同じ頂点の先にぶら下がっている2点を同時に塗ってしまうと、そのあいだの距離は必ず直径よりも短くなる。直径より長くなることはありえないし、仮に直径と等しくなることがあるなら、真の中心はどこだ?という話になる。そんなものはない。

ここまでを今朝のうちに納得してから実装したのに、直径が偶数のケースで中心の求め方を間違えたり(提出 #26352819)、線形時間の集計を繰り返して TLE になったり(提出 #26353052)、無駄に長さ N の配列確保を繰り返して TLE になったり(提出 #26353383)、いっぱい間違えた。

配列アクセスとハッシュ表アクセスだと配列の方が断然速いのだけど、初期化が1度で済まないなら、ハッシュ表の初期化コストの低さが効いてくるみたい。

 提出 #26353562 (AC / 750 Byte / 725 ms)

8問目の黄 diff AC。これより上は橙が1問だけだから、かなりのレア度なんだ。

ちなみに 水 diff だった E 問題 LEQ は、まだ TLE を回避する計算方法がわかっていない。

 木の直径

さっき書いた。

木の直径については知っている。(中略)。証明は知らない。

木の中心を念頭に置いて考えると直径を求めるアルゴリズムはこういうことだ。中心は、頂点の場合も辺の場合もあるけど、頂点集合を左右のどちらか(もしくは中心から直接出る辺のどれか)に振り分ける。任意の1点を始点に選んで最も遠い頂点を求める1回目の探索は、中心を挟んで異なる側にある、中心から最も遠い点を求めている。2回目の探索も同じ。同じ側に属する点が最遠点として選ばれることがないのは、中心に寄り道するパスを想定して比較材料にするとわかる。2回の探索で見つかったどちらの頂点も中心からは半径分だけ離れているから、そしてお互いに異なる側にあるから、合わせて直径になる。

 ある問題

さっき書いた。

木の直径については知っている。過去にある問題で満点解答のためのヒューリスティクスとして、深さを求める関数を2度呼び出して答えとしたことがあった。

エディタのログから「.max_by」を GREP したら該当するファイルが(たったの) 15 見つかったので、順番に調べてみた。「ある問題」とは ARC022-C「ロミオとジュリエット」だった。これが青 diff なんだからチョロい!(嘘です。調子乗りました)


2021年10月01日 (金) [AtCoder] 精進。ABC104-C「All Green」(水 diff)。配点の高い問題から解いていきたいけど完答ボーナスがちょっとした番狂わせを演出するのにどう対処するか。貪欲がダメなら DP すればいいじゃない。だから DFS で解いた>提出 #26249595。問題群を ボーナス込みの得点合計÷問題数 でソートして効率のいい方から総当たり(打ち切りあり。残りスコアの合計からと得点効率から計算する最小値更新の見込みから)。問題の解き方は問題群単位で全部解くか1問も解かないかスコアを満たせるだけ解くかの3パターンしかない。制約がたいへん控えめなので解法もバラエティに富んでいる印象>Ruby によるすべての提出。と思ったらほとんどがビット全探索で DFS が少々、といった感じ。DP はダメだったか。たしかに、全部解くか残スコア分だけ解くかの2択に対して p 回繰り返すループは、それが無理な制約ではないにしても無駄が多い。


2021年09月30日 (木) 娘の「なぜ1+1=2なのか」に対して「りんご1つとりんご1つを合わせると2つになるって説明は」と聞くと「それは『例え』」と返された話 - Togetter」■おもしろそうな話。バイリンガルの小学1年生だって。どこに疑問を持ってるのかわからないところがある。たとえば自分なら1と2という文字とその関係について考えている。1+1が3や「あ」ではなく2である理由。だから答えは、順番さえ最初にエイヤで決めてしまってそれに従うのなら(たとえばイロハニホヘト……)、1+1=2がイ+イ=ロでもいい、という話になる。これより難しいことは考えられないし疑問に思うこともありません。ところで、見慣れない表記をしたせいでわからなくなったのだけど、イ+イ=ロからの類推でロ+ロ=ハとしてしまう間違いの原因はどこにあったのか。コメントからのリンクで「ペアノの公理」というページをチラ見したのだけど、「順序」(相対的)ではなくて「0からの隔たり」(絶対的)と考えた方が良かったのですか?


2021年09月29日 (水) ひえーFacebook、Aタグの上でマウス押下した瞬間にhref書き換えてんのか!で次の瞬間マウスクリックするとその書き変わったURLを踏む / Twitter」■なにそれすげー(すごく邪悪)。マウスボタンダウンとマウスクリックの間隙をついた操作。こういうのは大体 Tab/Enter/Appキー/Shift+F10 には対応していない中途半端なゴミになるのが関の山なので、邪悪な目的に使う分にはどうでもいいけど(どうせスクリプトは無効だし、Facebook は非ログインユーザーを門前払いしている)、乱用するとナビゲーションに困難を来す結果になりますよ。■関連で <a> タグの ping 属性を知った。「<a>: The Anchor element | MDN」 いらない機能ですね。「A space-separated list of URLs. When the link is followed, the browser will send POST requests with the body PING to the URLs. Typically for tracking.」 もちろん User-Agent たる Firefox はユーザーが望まない動作を行わないオプションを用意してくれるものと信じている。■まじであった。「Firefox 3 で対応が追加、但し既定では有効化されていない (browser.send_pings の設定で隠蔽)。」 けっこう古くからあったみたい。古すぎて、今でもこの設定が参照されているかは要確認だけど。


2021年09月28日 (火)

最終更新: 2021-12-21T16:21+0900

[AtCoder] AtCoder Beginner Contest 220/F,E

昨日あった ABC。今回は全体に易化傾向で、D 問題がやるだけの茶 diff。F 問題でも水 diff。実は F 問題より E 問題の方が解かれていないけど、そちらも水 diff の範囲。ABC は5完6完を狙いたいところなんだけど、ABCD を 17 分4完(+うっかり余りをとり忘れて 1 WA)でレートは微減。あなたは残りの 83 分間何をしていたのですか?

 F 問題 Distance Sums 2

こちらが先に解けた。やり方はすぐにわかる。1か所だけ素直に求めて、あとは辺の左右にあるノード数の差を見ながら差分を更新する。すぐに実装できたかというとそうはいかない。どういう処理をどういう順番で並べると答えが次々生み出されてくるのか、とっかかりが掴めなかった。結局、根を1つ決めると木に深さという概念が生まれて、根の深さを0にしておくと全頂点の深さの和が根にとっての答えになった。これがとっかかりになって最後まで書けた。

 提出 #26188321 (AC / 572 Byte / 573 ms)

木の問題は深さと距離と子孫がそれぞれ Depth, Distance, Descendant なもんだから、いつも D が識別子として不足して困る。それに直径(Diameter)も追加で(ちなみにアクセントは i でも e でもなくて a らしいですよ)。

 E 問題 Distance on Large Perfect Binary Tree

83 分間合わないサンプル2を合わそうとしていました。明らかに同じような計算がノードごとに繰り返されるので、累積和の累積和を表引きして TLE を避けるのだと思っていた。ところが実際は一番内部の式が定数になったので(たとえば 2^a × 2^{N-a} が a の値によらないようなこと)、愚直解だと思っていたものがそのまま答えだった。

しかしその愚直解を合わせるのにも一生分の時間がかかるように思われた。死ぬ前に解けて良かった。3つくらい勘違いポイントがあった。組み合わせを半分(それとも2倍?)扱いしなければいけないのはどういうケースか(同じ深さの2頂点を組み合わせて距離 D を作る場合ではない)、それは頂点何個分か(N,D に足し引きして求まる数ではないし冪(数)でもない)。

 提出 #26199345 (AC / 203 Byte / 167 ms)

余りをとる数え上げ問題は正答までの距離が計れなくて途方に暮れがち。

愚直解っていうのは、深さごとに、頂点がいくつあるか、頂点1つが相対的深さ D の頂点をいくつ持っているか、相対的深さ 1 の頂点と D-1 の頂点をいくつ持っているか、相対的深さ 2 と D-2 ならいくつか……を数えて掛け合わせて足し合わせること。

E 問題も F 問題も青 diff でいいじゃないかというくらい苦労したけど、振り返ればどちらも考察は要求されていない(「すぐにわかる」「愚直解」)。ある意味やるだけの問題だった。やるだけ(できるとは言っていない)。


2021年09月25日 (土)

最終更新: 2021-09-30T13:08+0900

[AtCoder] AtCoder Regular Contest 127/A,B

 A 問題 Leading 1s

制約上の上限が 16 桁だっていうから、f の値の上限も 16。たとえば f(x) = 5 のとき、x は 11111 であるかプリフィックスが 111110 であるかのどちらか。f の値ごとに N 以下の範囲にそういう x が何個あるかを数える。桁数を固定すれば数えやすい。提出 #26096008

競プロ典型90問「025 - Digit Product Equation(★7)」の簡単バージョン。

 B 問題 Ternary Strings

頭の中がぐちゃぐちゃで解けなかった。終了直前の提出がこれ>提出 #26101512 (1 WA)。

とってもくやしいことに、1文字書き換えたら通りましたとさ>提出 #26105189 (AC)。2行目の N==1L==1 にしただけ。なんだよもー。もーもーもー。

一応考えたことを。最小化したい最大値の先頭の桁は2で決まっている。その後ろに0から N-1 までの N 個の数を3進数で表記したものをくっつける。これが2から始まる N 個の数。0から始まる N 個の数と1から始まる N 個の数は、桁ごとの制約を満たすようにテキトーに決める。これだけ。なんで書けへんの? 他の人の提出を見ると tr で 0,1,2 をローテーションするのが簡単そうだった。簡単にできることをすごく難しく考えていた。

驚いたことに、このふがいない有様でレートは上昇しているのである()。どれだけ低いレートに甘んじているかわかろうというもの。


2021年09月20日 (月) 天穂(てんすい)のサクナヒメ。アップデートによって「外から我が家へ帰った時、犬が出迎えてくれるように」なった結果、人間が寝床に入った夜でも犬だけは必ず駆け寄ってきて撫でろ抱っこしろと要求を欠かさない。忠犬である。これぞ犬。犬の鑑。最初は撫でて抱っこしていた。まもなく抱っこはいいかなと考え直して撫でるだけになった。そしてゲームも終盤になってとうとう撫でるのが邪魔くさくなった。駆け寄ってきてもジャンプして素通りである。そうするとね、追いかけてくるんですよ。嬉しそうに田んぼの中までも水につかりながら。改めて思いを強くしましたね。猫が好きだと。■不具合ぽいのに2つでくわした。1つは肥料に追加素材を入れるとき。種類数に上限があるのだけど、追加素材を2回に分けて入れようとすると上限まで入らないことがある。2回目に1回目で入れた素材を追加投入したときに、つまり個数だけが増えて種類数は増えないのだけど、空欄があるのに新しい素材が投入できなくなる。追加投入する素材を後回しにして新規投入分を先に投入すると空欄はできない。2つめはナマズのボスと戦う常夜の無尽瀧の深部。入ってすぐの岩の門をくぐらずに飛燕と羽衣で上に上ると洞窟の天井の上を歩けた。そのまま進んで画面が切り替わってボス戦が始まって、でもボスは足下にいて姿も見えないので戦えない……。メニュー画面から脱出もできないから直前のオートセーブから再開した。2回目は天井に上れなかったからそんなに簡単ではないのだと思う。あと戦闘中にフリーズが1回。真っ暗な画面に UI 要素だけの状態で止まった。■敵に1ダメージしか通らないときに頼りになる異世送り・体だけど、これって体勢を崩して倒れている敵にしか効かないってわけじゃあなかったのね。そうでないと羽衣がくっつかないか単に時間がかかるってだけで。R1 で羽衣を伸ばして方向キーを入れて、防御力が下がるまでじっと方向キーを入れっぱなしで待てばいい。300層をクリアするまで気が付かなかったぜ。知っていれば異様に堅いロボットにもあんなに苦労せずに済んだろうに。攻撃チャンスが少なすぎると思ったんだ。


2021年09月19日 (日)

最終更新: 2021-09-23T19:26+0900

[AtCoder] AtCoder Regular Contest 126

昨日の ABC に続いて今日は ARC があった。

昨日と同じく ABC の3完(+2WA)。24 時終了でもう 27 時になりそうだけどまだ結果が出ない……(水色に戻れたの?どうなの?)

 A 問題 Make 10

脳内で組み合わせを全探索して優先順位を付けて貪欲法で>提出 #25984785

 B 問題 Cross-free Matching

LIS が見えていなかったせいで配列に対して insert/delete_at を繰り返す効率の悪い実装になったけど、通るは通った>提出 #25988002 (911 ms)。

LIS ではないこの解答の形は「Shortest Path on a Line」と「蛍光灯」で書いていた>20200826p02

LIS にすると倍以上速くなってこう>提出 #26015260 (440 ms)。

 C 問題 Maximize GCD

最初にサンプルの3にだけ答えを返すように if で処理を分けた。そうすると残りのケースで K の高すぎる上限を気にかける必要がない。

次に GCD について。砂で隙間を埋めるように1ずつの操作ができるとなると、GCD が取り得る値について A 数列の素因数から推測できることは何もないような気がしてくる。じゃあ探索しますか?

  1. 考えてる途中でなぜか +1 の他に -1 の操作もできるつもりになっていて WA>提出 #25992664
  2. -1 の操作に対応した部分を削除して AC>提出 #25993948 (1248 ms)。
  3. C 問題も B 問題同様、制約と入力がガチガチに厳しくないのに助けられている。余分な log を削って 943 ms>提出 #26017330

どうもね、N 回のループの中身を対数時間の処理にするということが、N^2 のループに対する高速化だという意識が強すぎて、N 回のループで前処理をして N 回の本番ループを定数時間で済ませる方が速いという感覚が持てない。N が2×N になってもオーダーは変わらないけど、ループを2本に増やすことに無意識の抵抗があるらしい。

 D 問題 Pure Straight

残っていた 20 分で愚直解だけ>提出 #25995534

RE と TLE の背後に WA が隠れている可能性がないではないが、「Shift and Inversions」でやったようにうまい遷移と、それと省略を見つけて高速化すればいいのかなと。


2021年09月18日 (土) [AtCoder] 精進。ARC065-D「連結」(青 diff)。出力部の直前4行の集計部分がキモ>提出 #25899408。必要なのは数だけであって、具体的な組み合わせを明らかにする時間的余裕は制約により与えられていない。結果だけ見ればシンプルだけどけっこう考え込んだよ。■■■[AtCoder] 今日はサイシードプログラミングコンテスト2021 (ABC219)だった。ABC の3完(+2WA)で大爆死の回。DP っぽい D 問題「Strange Lunchbox」が解けなかった。Ruby での AC はコンテスト終了直後の時点でゼロだ。わからん。E 問題「Moat」は盤面が 4×4 なんだからどうとでも処理できる。マス目ごとに堀の内部か外部かを決めて総当たりしても高々 65536 通り。そこから堀の内部が一塊になっていないものを除外する。つまり、堀の内部が連結ではない場合と、堀の内部の内部に堀の外部が島になっている場合を除外する。盤面が小さいから横着して添字をベタ書きした。でも時間内に書ききれなかった。終了後に AC>提出 #25962480。うーん。■D 問題もできた>提出 #25964674。うん、緑 diff なのもうなずける普通の DP だった。同じ形を書いたことがあるし、すらすら書けてバグも明らかなものがひとつだけ(pop と shift の取り違え)。だけど時間に追われると DP は普通に解けない。■F 問題の「Cleaning Robot」が面白そう。橙 diff だけど。K の制約が突き抜けていて予め無駄な努力を拒絶する親切仕様。ネタバレが許されないタイプの問題だと思う。自分でネタを掴みたい。■@2021-09-30 メモ。まず1サイクル巡回して通過点と原点との関係を角度(GCD(X,Y) で割った X 座標と Y 座標)ごとに絶対値(GCD(X,Y))で記録する。1サイクルごとに原点がどこに移動するかも記録する。重複(後追いと交差)を省いて K 回分数え上げる。どうやって?


2021年09月17日 (金) [AtCoder] 精進。ARC063-D「高橋君と見えざる手」(水 diff)。ちょっと似た問題が思いつかない不思議な問題。入力のうち T は未使用>提出 #25884205。出力部分を p [Hi,Lo].min としたけど、「Ai​ は相異なる」という制約を見落としていた。それなら Hi と Lo の数は必ず一致する。だから簡単になってこう>提出 #25884286。ああ、このメモしながらスキャンするだけの水 diff には覚えがある。AtCoder じゃんけんだ>20210830。今の ARC だと A 問題(茶 diff)でもこれより難しいよ。これとか>「Many Formulae」。メモしながら一度スキャンするだけなのは同じなんだけど>提出 #23369338


2021年09月16日 (木) 信号無視で検挙も不起訴→「ブルー」の免許で更新されたとしてゴールド求め提訴:バイク速報」■これ、まとめ内でも理解してないコメントがいくつもあって、自分も知らなかったのだけど、サインしないで裁判沙汰にして不起訴(起訴猶予)になったけど点数は引かれてました、っていう経緯みたい。勝ったと思ってたら負けてた、みたいな。それはわからんで。■「起訴猶予とは?不起訴・無罪との違い | 弁護士法人泉総合法律事務所」 不起訴になる理由に3種類あるらしく、嫌疑なしと嫌疑不十分と起訴猶予。この件は起訴猶予。起訴猶予とは「犯罪を犯したことを裁判で証明できるが、被害が軽微である、示談ができて被害者も許してくれた、社会的制裁を既に受けている、深く反省しているなどの諸事情を総合考慮して、今回は起訴を見送るという判断」らしく、これだけ読めばお目こぼししてもらえてラッキーだったねという印象だけど、ラッキーだったとは考えられない理由が2つある。1つ目は、そもそも信号無視程度の違反は罰金案件ではないから不起訴という結果はプラスの結果ではないのではないか、ということ。2つ目は、「犯罪を犯したことを裁判で証明できる」というのは検察官の見込みであって裁判を経た裁判官の判断ではないということ。だから起訴猶予でも嫌疑なしでも不起訴は不起訴であり罪はまだ存在しない。■さて、反則金で済ませられるところを裁判沙汰にして罰金案件にして、おそらく二重に課せられることはないだろうからこの時点で反則金の支払いは免除されてると思うが、不起訴の結果で罰金の支払いも回避できたけど、なぜか違反の事実は消えず点数が加算(減算)されていた。これをどう考えればいいか。合理的な説明できる? 裁判所にいったんエスカレーションした案件で点数だけが反則金(罰金)とは別口で処理されてるように見えるんだけど、これは矛盾では? 矛盾ではないというなら存在する違反に目をつぶった検察官の恣意か、存在しない違反に対して点数を引いた警察の恣意か、どちらかを権力の乱用・私物化として問題視するほかないと思う。実際問題、起訴猶予を選んで公判を開かない、(まかり間違っても)前科を付けないという検察官の判断は裁量の範囲で妥当なものだと思う。そして警察は、(理由や思惑によらず忖度せず)不起訴という事実を以て行政処分をあきらめるのが筋の通し方だろう。だって起訴猶予でも不起訴を、推定有罪扱いはできないでしょう。コメントによれば不起訴で点数を戻す警察もあるらしいし、それが当然だと思う。京都府警の主張では行政処分は警察の管轄ということらしいけど、反則金制度が運転者に二重の処罰を受けさせるために存在しているとでも?(そうなの?) まさか司法判断を虚仮にする自虐趣味はないと思うが、地裁判決が狂ってることはまれによくあるので、京都地裁の判断を期待して待ちたい。