/ 最近 .rdf 追記 設定 本棚

脳log[2021-05-22~]



2021年05月22日 (土) 怖くて見てなかったけどこの前の ARC (20210510)のパフォが 300 台だった! えー、つまり灰パフォ? これが初めてではないし、むしろ大体そうなんだけど、ARC の傷を癒すには ABC1回では足りないぜ。なんなら ABC の D 問題にだってたまに……ときどきやられる。■明日の ARC (20時から!)のお誘いメールが来ない……。A 問題から 400 点なのはたいへん厳しい。ARC の 400 点は五分五分だ。

最終更新: 2021-06-08T14:41+0900

[AtCoder] エイシングプログラミングコンテスト2021(AtCoder Beginner Contest 202)E 問題 Count Descendants

解けてしまった問題とまるで歯が立たなかった問題は、日記にならなくて困るという点で共通する。E 問題で Ruby の AC 提出をざっと見たら他の人の解法が異なっていたのでそれを。

ちなみに F 問題の提出(Ruby)はなかった。ゼロだった。まずね、凸包がよくない。それは自分の人生とは一切関わることのない専門用語(だということにしてこれまで無視してきたもの)なので。

話は E 問題。こちらはやること自体は明白で、読めばわかる。木が与えられて、深さを調べるのも、親を辿るのも、基本操作だ。この問題の問題は制約にあって、ノード数もクエリの数も、上限が20万だというところ。定数時間でクエリに答えたい。

 クエリ(U,D)に答える方法1

  1. ある深さ D にあるノードのうち祖先に U を持つものを選ぼうか。
  2. 実装したことはないけどダブリング(要は繰り返し二乗法でしょ?)で効率的に親を辿る?
  3. (ほぼ)全ノードがフラットに並んでたらダブリング関係なくクエリ(N)×ある深さのノード数(N)で死ぬ。

 クエリ(U,D)に答える方法2

  1. あるノード U の子孫ノードを深さごとに数えておこうか。
  2. 深さを調べる深さ優先探索のついでにそれはできるけど、子ノードが記録した配列をマージするのが大変。ほぼノードの数だけマージ操作が必要。マージテク
  3. 実装しなかったのでこれがアリなのかわからない。子ノードのうち底が深くないものから深い方へ、順番に足し合わせていくとどうなるか。

    一直線の木で Σk 個の要素を処理するような実装でなければアリなのか。

 提出 #22827097 (TLE×27 / AC×3)

これはマージしないでいいように1つの深さ記録配列を共有する実装。ただしノードごとに Array#dup した配列をスナップショットとして持っている。配列の要素数の合計がギガ単位になるけどどうかな、と期待して出したけど全然ダメだった。AtCoder の入力マジえげつない。上限は飾りじゃないのよ。

 提出 #22832306 (AC / 708 ms / 285,364 KB)

基本形はさっきのと同じ。クエリを先読みして必要なものだけ記録するようにした。TLE から 22 分経過していてコンテスト終了まで残り 10 分。あぶなかった。

 クエリ(U,D)に答える方法3

これは他の人の AC 提出を読んで知った方法。二分探索を使うらしい。オイラーツアー?

  1. 深さ優先探索で深さを調べると同時に、あるノードに降りてきたタイミングと上っていくタイミングを記録しておく。
  2. クエリがきたらノード U の両タイミングの間に処理をしたノード(=子孫ノード)のうち、ある深さ D にあるノードの数を答える。
  3. タイミング配列をなめて深さを確かめる線形時間の処理は許されない。どうする?
  4. (3つの提出を読んだのに思い出せない) どうする?
  5. タイミング配列を深さごとに分けておくのかな。
  6. クエリが指定する深さのタイミング配列を取り出して、そこからクエリが指定するノードの子孫にあたる範囲を二分探索で切り出すと、答えがわかる……かな? 実装して AC をもらってないので不確か。

確かなことはこのあたりの提出を読めばわかる。(提出の早い順)

メモリ消費にけっこう差があって、自分の提出は最も多い部類。正直どこが原因なのかわからない。


2021年05月18日 (火) 1より小さい正の整数は1より大きい - 西尾泰和のScrapbox」■間違えたし意味がわからなかったし、しまいには1と10の大小関係がわからなくなってきた>「3が1より小さいなら、3は10より大きい」。命題(P ⇒ Q の Q)があからさまに偽だからこの偽の命題を成り立たせる(P 以外の)隠れた条件は何か、という風に逆転した論理を自動的に考えてしまうのだと思う(生存戦略。ヒトは全知全能の神ではないが、無知の知ぐらいはある)。そうなるともう何もわからない……。■種明かしを読めば Ruby で空配列に対するクエリ [].all? が(どんなブロックを与えても与えなくても) true を返すのと同じだと理解できる。■これには疑問>「最後の「3が偶数なら、4は奇数である」が正解多数だから1の"P が偽ならば、Q の真偽にかかわらず「P ならば Q」が真である"は理解してる人が多い」。 偶奇って正負、陰陽、表裏、左右と同じでペアのそれぞれにアイデンティティがあるわけではないので、「3が奇数なら4は偶数だし、3が偶数なら4は奇数」というように納得して正解の選択肢を選ぶことができる。しかしこれはさっき書いた逆転した論理。自分のように偶奇の性質によってたまたま正解が選べただけの人がいるのでは?■■■@2021-06-23 今日読んでいた本『『詭弁論理学』(野崎 昭弘 (著) / 中公新書)』の 171、172 ページにちょうど書いてあった。「『もし Q ならば、Pである。』と『P でない。』とは、どちらも正しい(ことがありうる――Q でないことが結論される)ので、矛盾とはいわないのである。『もし Q ならば、P である。』と『もし Q ならば、P でない。』とも、Q が起こりえない状況においては、『Q でない』ことが確認されるだけで、矛盾ではない。


2021年05月10日 (月) [AtCoder] 昨日の ARC118。A 問題で Float を使ったら WA が出て、雑に .round(5) を呼び出したら AC になった。これが良くなかった。B 問題も同じ流れで Float を使って答えを出したら 5 WA。この WA が消せなかった(round の呼び出し方が間違ってたんだけど、それを直しても、引数を大きくしても、1 WA だったのを後日確認している)。今日になって解法はそのまま整数でやり直したら AC。A 問題の時点で良くない流れができていましたね。C 問題は Coprime (緑 diff) が解けるなら解けても良かったんじゃないかな。自分はまだ克服していない>「Coprime はまた解けなかった」「Coprime の単語が見えた瞬間にあきらめた。完全に苦手意識を持っている」■一応サンプル出力を素因数分解して考えはした。C 問題。素数(の累乗。0乗はダメだよ)の組み合わせで A の要素を作る。上限に注意する。A の各要素は組み合わせに使用する素数のどれかが必ず欠けている(setwise coprime)。A の要素それぞれについてそれを構成する素因数を見たとき、A 数列の全体を各素因数を含む複数のグループに分類できる(pairwise not coprime)。N の上限 2500 に対して A 数列の要素の上限 10000 が低く見えるのが難しいように思った。実際に作ってみて確かめようと思ったが、AC 目前の B 問題を先に片付けようとして、でも B 問題でつまずいたまま起き上がれなかったんだよなあ。


2021年05月09日 (日) 「あなたが20歳だとします。ある初対面の40歳の人Xがいて、その人が初対面の60歳の人に対して話す時とは明らかに異なる口調態度であなたに話しかけて来た場合、その人Xとの関係は今後どうなりますか?」 / Twitter」■ニュートラルでありたいけど目の前で使い分けられるともやもやするかも。年齢差関係なくタメ口の人に対する第一印象には「馴れ馴れしいな」「侮り?」「不作法?」「輩系?」という警戒心が混じる。あ、これニュートラルではない? タメ口を抵抗なく受け入れるための能力的、人柄的なハードルは高め(礼儀正しさという美徳をすでに捨てているわけなので)。超えられないなら困った人であり、敬遠するかも。立場、役職の違いはハードルを越える助けにならない。たぶん年齢差も助けにならない。年齢差にふさわしい何か(それが人柄や能力、ふるまいなど)があって初めて敬意が抱けるのであって、年齢差そのものがマイナスを押し上げるプラス要因になるわけではない。■ともあれ、相手によって対応が変わるのは当たり前のことであり(関係って相互的なものだ)、要はうまくやれているかどうかだと思う。■差別的な口調態度というのをタメ口に限定して書いてきたけど、高圧的態度、聞く耳を持たない態度だったならそれは論外です。死ね。


2021年05月07日 (金) [Git] 「これは神! GitHubが、クリックするだけで親リポジトリと同期できるようになったらしい!」■しかしですね、こういうひねくれ者もおります。「自分の GitHub リポジトリにコピーブランチはいらない。ローカルの作業リポジトリで git fetch --all して <remote>/master などと参照すればよい。」■「マンガでわかるGit 12話「本家リポジトリに追従する方法」 | リクナビNEXTジャーナル」にある「最後にプッシュして完了」の手順が必要ですか、っていう話。それをしないとできない操作は何ですか、っていう。■■■たぶん基本的な考えとして、ブランチ作成/プッシュ/プルを GitHub の自分が所有するフォークリポジトリに対してのみ行うというフローが想定されているのではないか。つまりローカルリポジトリは自分が所有するフォークリポジトリのクローンとして作成し、origin (フォーク。自分の GitHub リポジトリ)を起点に作業をする。にも関わらずこれまでは本家リポジトリに追随するという目的のために、ローカルリポジトリから本家リポジトリを参照する必要があった。今回の GitHub のアップデートによりローカルと本家の繋がりを断つことができ、origin を中心とした作業フローがより完全なものになるとか?■自分は git checkout -b myBranch 本家/mastergit push -u myGitHubRepo myBranchgit rebase 本家/master [myBranch] というフローで作業をするために、「自分のではないリモートリポジトリへのプッシュをできなくする」「新しく作成したブランチが自動的に設定する、分岐元との繋がりを断つ(--no-track を既定値にする)」という下準備をローカルリポジトリで行っていた。そもそも「(クローンしたなら)リモート名 origin を削除する。余計な自動化も自分が管理しない名前もない方がまし」という考えによってリモート名 origin が存在しなかった。■だって origin ってリポジトリ名なの? ブランチ名なの? 本家なの? フォークなの? そういう曖昧なものの上で作業をしたくない。ましてそれ(origin)が他人(git)のお膳立てなら、助けではなく余分な複雑さを持ち込むようにしか思えない。定型のタイプの繰り返しに倦んできた頃に提案してくれたなら考えないこともない……かな? それでもやっぱり自分は pull は使わないので(許容できるのは checkout や add までであって、自動で merge/rebase は乱暴だ)、origin もいらないんだよな(本家リポジトリにはその代わりにわかりやすい名前を付けます。「ブランチ名とひと目で区別できるように、リモート名は @ を付けたり大文字にしたりしようかな」)。■自分にとって3つのリポジトリの関係は「本家―ローカル―フォーク」として捉えられている。でもひょっとしたら「本家―フォーク―ローカル」の想定もあるのかもな、と考えてみた次第。でも自分で GitHub にフォークリポジトリを持たなくても「本家―ローカル(フォーク)」の2者間でもフォークは成り立つので、中心に GitHub 上のフォークリポジトリを置くのは、GitHub の中の人の立場としてならともかく、個人としては順序が違うと思う。メンタルモデルはひとつで十分だ。そのとき GitHub 上のフォークリポジトリは3番目に位置するオプショナルな存在となる(だから意識しなければこれを忘れる>「フォークする。プルリクエストを出すためには GitHub 上でフォークしたという事実が大事」 新規作成した空のリポジトリにプッシュしても PR は出せないのである)。■しかし GitHub のアップデートによって今後は、GitHub と origin を必須の前提として作業フローからリモートの区別・存在感を消すのがある種最適な選択になるのかもね。本家とフォークの2つのリモート名を使い分ける必要がなくなるのなら、単純化がなされるのなら、割り切りによる制約がむしろメリットと感じられる人もいるだろう。さもなければ無駄に複雑化して面倒なことをしているなと自分は思います。


2021年05月05日 (水) うんこの生産効率が高すぎる。毎日3回まで!


2021年05月04日 (火) 「洗たくマグちゃん」効果に裏付けなし 消費者庁が措置命令 シリーズ累計500万個売れた人気商品 - ITmedia NEWS」■何日か前に家で見た。どうして王道を避けてあえてスピリチュアルでロハスな選択をしてしまうのか、不思議に思っていたところ、間を空けずに ITmedia で二度目のご対面となった。■で、スラド。「消費者庁、洗剤を使わずに洗濯しても十分に洗浄できると表示していた「洗たくマグちゃん」に措置命令 | スラド サイエンス」■消費者庁が言っているのは、実際に洗濯してみるなど、効果をうたうのに十分な合理的根拠がないことを問題にしている。販売元は一応の資料を提出したらしいが、たぶんマグネシウムに関する間接的な試験結果だったりしたのだろう。はっきりさせたいのは、消費者庁は効果がないことを証明したわけではないということ(消費者庁に効果がないこと(翻って効果があること)の証明を押しつけられるならお得だ。もちろんそうはいかない)。スラドのコメントを読むときはそこのところをはき違えた、たとえば「使ってみた」系の記事に対する揶揄などが、印象に基づく根拠のない中傷だということに注意しよう。消費者庁に駄目出しされてもしかたのない見事なブーメランコメントだ。コメント主の家にも洗たくマグちゃんが転がっているから恨み千倍なのではないか。そういうタイプの人間だよ(書きすぎ)。噂にふりまわされたり思い込みで馬鹿なことを言ったりしてないで、使ってみた系の記事を見習って自分でも効果のあるなしを確かめてみたらいい。それが迷信から足を洗って科学を始める第一歩ですよ。まだ遅くないからがんばりましょう。■関連。20151214■■■@2021-05-31 より詳細に。テストのしかたにも言及がある。「「実質的にはただの水洗い」洗たくマグちゃんは無意味だと言える"科学的な理由" 「アルカリで洗う」はウソだった | PRESIDENT Online(プレジデントオンライン)」 予想された内容。だけど結果論で正当化はできないよ。


2021年04月29日 (木) 【速報】飯塚幸三被告「アクセルを踏んでいないのにエンジンが高回転しパニック状態になった」 : 暇人\(^o^)/速報 - ライブドアブログ」■これに対する「反省してない」「嘘つき」という反応が本当に嫌い。実際のところは当人しか知らないけど、この人の主観においてアクセルを踏んでいないというのは普通にありうる。自分だってゆっくりバックしてるときに踏んでるペダルがアクセルかブレーキか、混同することがある(そして一瞬踏んだ後で認識を改める。その前にパニクって暴走して事故を起こしたらどうなるか)。主観的事実に基づかない供述をして潔く罪を認める姿勢を示すことこそが嘘であり、己の信念に反する行為だとして受け入れがたい、というのが自分という人間。たとえ弁護士に罪を認めた方が心証が良くなって刑が軽くなる可能性がありますよと助言されたとしても、従うかどうかはわからない。そのことと、起こった事故に関して車のドライバーとして所有者として被害者遺族に対する責任を果たすこと、判決を受け入れて罪を償うことは矛盾しない。この人がそうだと言っているわけではないが。■「反省してない」「嘘つき」という反応は、これが特殊な反応ではないと思うからこそ看過できなかった。反省するとは嘘をついて、真実を飲み込んですべてを己で引き受けることなのか。「そうだ」という反応はありそう。「それが大人だ」という雰囲気を感じなくもない。自分とは異なる人間。それって場の和を守るためのスケープゴートを求める姿勢と何が違うの? 演出された予定調和なんてくそくらえ。被告の主張とは無関係に証拠を固めて罪を問えばいい。自分が被告の立場でもそう思ってる。


2021年04月28日 (水) これが突然の変化なのかこれまでぼんやり生きてきたせいなのか知らないけど、左右の目って見え方がかなり違う。違うよね? 顔の真ん中に手を立てて、たとえば白い物を見ると差が際立つんだけど、自分の左目の視界は右に比べて薄暗く、それにかなり青い。目を圧迫するような姿勢をとっていて一時的にちかちかしてるだけかとも思ったんだけど、5分10分では変わりがない。光の当たり方の影響を考えて方角を変えても変わらない。え、そういうもの?


2021年04月27日 (火)

最終更新: 2021-04-30T21:11+0900

[AtCoder] AtCoder Beginner Contest 199(Sponsored by Panasonic)D 問題 RGB Coloring 2

10分間3問早解き」回だったわけなので4問目(D 問題)は時間中に解けなかった。90 分使っても解けなかった。辺がないケースで TLE が避けられなかった。

 提出 #22101036 (AC / 343 ms)

AC のきっかけはこのツイート。

chokudai(高橋 直大)ナス@chokudai

D問題、非連結ですって言うだけでDiff400くらい落ちそう

chokudai(高橋 直大)ナス@chokudai

非連結ですって言っても落ちないわ(サンプルにあるし)

連結で出題しないと400落ちなさそう。

連結で出題しないと落ちない」がよくわからないけど、ともかく、非連結なら問題を分割できるじゃん、と気がつきました。ツイートを読んで初めて気がつきました。

サンプル4つのうち2つが辺がゼロのケースだったんだけど、極端すぎてそれが全体としては非連結なグラフであること、個々の頂点としては最も簡単な連結成分を構成している、ということがわかりませんでした。そんなことってある?

 AC 前の提出 #22100473 (TLE×2 / 1つは after_contest)

テストケースが公開されていないので、提出前のテストには一直線の木を使っていた。連結成分の数を増やしても、辺の数を増やしても、探索を助ける制約が増えるだけだと思ったので。

しかしまだ TLE。どういう木が嫌か考えると、この提出は次のような入力に弱い。

だけど次のように番号の付け方を変えただけで問題が問題でなくなる。

たぶん頂点を次数でソートしてから DFS をすれば緩和されたと思う(が、AC 提出では違う方法(先読み)をとった)。

ソートするにせよ先読みするにせよ、2番目の問題に対処するには非連結なグラフを連結成分に分割する必要があったが、それをしないまま DFS の処理量を削減する方法を考えていた、というのが失敗に終わったコンテスト中の時間の使い方だった。

 提出 #22109995 (AC / 238 ms)

DFS の処理順を次数の降順にしたら悪くなりにくいのか、343 ms からタイムが大いに改善した。このムラが DFS の沼であり抜け出せない楽しみなんだよなあ>20201101p0220201107p01.05


2021年04月25日 (日) [AtCoder] 昨日の ABC199 で10分間3問早解きの結果、吹けば飛ぶようなょゎょゎ水色になっていた。次はないな。■「「#ボケちゃいMAX https://t.co/DpY5sB73Os」 / Twitter」 ちなみに座れるような椅子はない。キーボードは布団の上である。「PC 前でスタンバイ」とはそういう体勢である。■■■ついに後編。「アルゴリズム・AtCoder のための数学【後編:数学的考察編】 - Qiita」 対象読者だと思いたいが、次の一文に海より深い断絶を感じる>「この問題も規則性を使うことができます。実際、A301=1,A302=1A301=1,A302=1 であるため、」 待って待って、説明がすっぽり抜けてるよ! A301=1,A302=1 なんてどこにも書いてないよ! それを導くところがこの問題の難しさだと思うよ! 「数列の任意の項が直前の 2 項によって決まっているので、連続する 2 項が既出の値をとるとき(たとえば初項である 1 と 1)、数列は循環している」「ある項の取り得る値が 100 種類に限定されているので、連続する2項が取り得る値も 100^2 通りに制限され、数列は必ず循環する」とはっきり宣言してもらってはじめてこちらは「へー、そうなんかー。そんなん考えたこともなかったなー。漸化式で定義された数列が循環するってそういうことかー」と反応できるんですよ。実際今初めて考えたからね。■同じようなことが以前にも>「『kを使った場合のコストは、k-1以下のすべてを使ったコストより高い』 これって要は 100000 > 11111 (2進数) と同じことなんだけど、自分のような人間は「この一連の操作のコストは(書き換えた要素の数によらず)2^k である」という問題文を読んだだけではたどり着けなくて、上のように事実として示されて2進数で考えてみて初めて了解できることだったりする。」■べつに噛んで含めるような解説が読みたいというわけでもない。ABC の一文解説とか好きなんである>20210224p0120200520p0120200428p01。これだけ書いてあれば十分でしょ、もう他に書くことないよ、と突き放される感じ。実際それで通じる人には通じるだろうし、ならばこちらもそれが理解できる人間でありたいと意地になるよね。程度を低く見積もってもらっては自尊心が傷つくのです。一寸の虫でもお馬鹿ちゃんでも。


2021年04月24日 (土) 「『あなたの iPhone はハッキングされました』みたいなメッセージが表示されたー。このアプリをインストールしたらいいの? 診断っていうボタン押したらいいの?」とか言って明け方に起こされた。突っ込みどころだらけで取り合うのもあほらしい手口ではないか。■そのメッセージは“何が”表示している? インターネットを閲覧していて表示されたものでしょう? そのメッセージが「お前はもう死んでいる」だったらどう? わーたいへんだー死んでしまったー。■OS が表示してるメッセージなら話がちょっと違うけど、「ハッキング」なんてチャラい用語をユーザーに提示する OS なら即座に今後の使用を考え直すレベルなのでそれは考えない。■英語ばっかりで説明されているそのアプリの画面で唯一の日本語であるレビューを読んでみ? 明らかに日本人が書いたものでないカタコトのサクラ。本気でだますつもりなら日本語を勉強してからおととい出直して来やがれ、って言うべき場面なんだよ。なんでおろおろしてんの?■もうすこし頭を使う奴ならメッセージに信憑性を持たせるために「あなたの iPhone をハッキングしました。その証拠に私はあなたのメールアドレスを知っています。それは○○ですね!!!」くらいのメッセージを出すんだよ。もちろんそれは User-Agent による自動補完なんだけど。■俺以外の現代人は「広告をスキップ」とか「広告を閉じる」といった操作に慣らされすぎていてマヒしてるかもしれんけど、こういうアホなメッセージを無視するためにメッセージとともに表示されている「閉じる」ボタンをクリックしてはいけないのだよ。iPhone だったら Safari か? ブラウザを操作して消すべきだ。広告が釣りに引っかかるユーザーを誘導している。フィッシングサイト同様に汚らわしい広告にも普段から一切触れないのがいいと俺は思う>20170403。■眠い。


2021年04月22日 (木)

最終更新: 2021-06-11T11:27+0900

[Ruby] 多重代入の評価順

以前書いた。「最初に右辺を評価して、それから左辺の評価と代入を左から順番に実行していく感じかな? 右辺の一時記憶が必要? 多重代入は遅くて時々評価順が難しい、というのが現在の評価。」「クイズです。a の結果を確認してから予想してカンマを付けたら予想通りの結果になったので驚きはないけど、やっぱり普通の代入とは違うんだなあ

そしてこの PR が多重代入について>Evaluate multiple assignment left hand side before right hand side by jeremyevans · Pull Request #4390 · ruby/ruby マージされている。

3.1.0 から変わりそう? 評価順が変わってパフォーマンスがさらにちょっと遅くなる? 新しい評価順っていうのが、

  1. 左辺の変数、レシーバ(メソッド引数も?)を左から
  2. 右辺の値を左から
  3. 左辺の変数代入、代入メソッドを左から

従来は2が最初にあって、1と3がインターリーブされていた。……ということが PR の概要欄と NEWS の修正に書いてある。

パフォーマンス劣化の理由は左辺の評価結果を一時的に蓄える必要があるからか?

いやあ、あっさり変えるし変えられるもんなんだなあ。まあたぶん、Ruby ユーザーの 1 % も変化に気がつかないだろうとは思う。

 新展開@2021-05-06

  1. https://bugs.ruby-lang.org/issues/4443#change-91847
  2. https://bugs.ruby-lang.org/issues/15928#note-10

非効率だしバグらせやすいし、作り込む価値がないと言っている?

自分はもうこの仕様について(穴にはまった実体験から)知っているので、常に穴を意識して書くし、逆に評価順を利用することもあるけど、これまで幸運にも意識せずに来られた大多数のユーザーが、将来的潜在的には驚きとともに多重代入の評価順の詳細を理解させられるんだろうな、ということを考えると、「作り込む価値はある。ただしうまく実装できる限りにおいては」という評価が妥当かなと思う。