display: none で隠す方法。これだと自分が使っているブラウザではキーボードを使ってグループ化されたラジオボタンの間でフォーカスを移動させることができなかった。ラベル要素をクリックすることでしか切り替えできなかった。これも「アクセシブルじゃないクリックイベント」のひとつ。■ラベル要素はクリックに反応してラジオボタンにフォーカスを移すけど、それ自身がフォーカスを受け取ってキー入力を処理することはない。しかしでは当のラジオボタンは……。規格は知らないけど、非表示(display:none)のラジオボタンは無効(disabled)ではないからチェック状態の設定・参照が問題なくできるけど、フォーカスを受け取らないから操作に支障が出る、という理解でいいだろうか。結局
opacity: 0 で隠した。これならキーボードで操作できる。透明で見えないけど存在している ⦿ のために生じる微妙な空間は無視できる程度だったのでそのまま。■だけど今時は(７から顕著なのを知っているが)、Microsoft の Windows でもキーボードアクセスが蔑ろじゃない？ 括弧で囲われたアクセラレータキーはどこ行った？ その一方で「Windows 10 の起動時に自動的に実行するアプリを追加する (support.microsoft.com)」方法に shell:startup と入力させる手順があるの、ほんとバカだと思う。最終更新: 2021-06-08T14:41+0900
解けてしまった問題とまるで歯が立たなかった問題は、日記にならなくて困るという点で共通する。E 問題で Ruby の AC 提出をざっと見たら他の人の解法が異なっていたのでそれを。
ちなみに F 問題の提出(Ruby)はなかった。ゼロだった。まずね、凸包がよくない。それは自分の人生とは一切関わることのない専門用語(だということにしてこれまで無視してきたもの)なので。
話は E 問題。こちらはやること自体は明白で、読めばわかる。木が与えられて、深さを調べるのも、親を辿るのも、基本操作だ。この問題の問題は制約にあって、ノード数もクエリの数も、上限が20万だというところ。定数時間でクエリに答えたい。
実装しなかったのでこれがアリなのかわからない。子ノードのうち底が深くないものから深い方へ、順番に足し合わせていくとどうなるか。
一直線の木で Σk 個の要素を処理するような実装でなければアリなのか。
これはマージしないでいいように１つの深さ記録配列を共有する実装。ただしノードごとに Array#dup した配列をスナップショットとして持っている。配列の要素数の合計がギガ単位になるけどどうかな、と期待して出したけど全然ダメだった。AtCoder の入力マジえげつない。上限は飾りじゃないのよ。
基本形はさっきのと同じ。クエリを先読みして必要なものだけ記録するようにした。TLE から 22 分経過していてコンテスト終了まで残り 10 分。あぶなかった。
これは他の人の AC 提出を読んで知った方法。二分探索を使うらしい。オイラーツアー？
確かなことはこのあたりの提出を読めばわかる。(提出の早い順)
メモリ消費にけっこう差があって、自分の提出は最も多い部類。正直どこが原因なのかわからない。
3が1より小さいなら、3は10より大きい」。命題(P ⇒ Q の Q)があからさまに偽だからこの偽の命題を成り立たせる(P 以外の)隠れた条件は何か、という風に逆転した論理を自動的に考えてしまうのだと思う(生存戦略。ヒトは全知全能の神ではないが、無知の知ぐらいはある)。そうなるともう何もわからない……。■種明かしを読めば Ruby で空配列に対するクエリ
[].all? が(どんなブロックを与えても与えなくても) true を返すのと同じだと理解できる。■これには疑問>「最後の「3が偶数なら、4は奇数である」が正解多数だから1の"P が偽ならば、Q の真偽にかかわらず「P ならば Q」が真である"は理解してる人が多い」。 偶奇って正負、陰陽、表裏、左右と同じでペアのそれぞれにアイデンティティがあるわけではないので、「３が奇数なら４は偶数だし、３が偶数なら４は奇数」というように納得して正解の選択肢を選ぶことができる。しかしこれはさっき書いた逆転した論理。自分のように偶奇の性質によってたまたま正解が選べただけの人がいるのでは？■■■@2021-06-23 今日読んでいた本『『詭弁論理学』(野崎 昭弘 (著) / 中公新書)』の 171、172 ページにちょうど書いてあった。「
『もし Q ならば、Pである。』と『P でない。』とは、どちらも正しい(ことがありうる――Q でないことが結論される)ので、矛盾とはいわないのである。『もし Q ならば、P である。』と『もし Q ならば、P でない。』とも、Q が起こりえない状況においては、『Q でない』ことが確認されるだけで、矛盾ではない。」
git checkout -b myBranch 本家/master、git push -u myGitHubRepo myBranch、git rebase 本家/master [myBranch] というフローで作業をするために、「自分のではないリモートリポジトリへのプッシュをできなくする」「
新しく作成したブランチが自動的に設定する、分岐元との繋がりを断つ(--no-track を既定値にする)」という下準備をローカルリポジトリで行っていた。そもそも「
(クローンしたなら)リモート名 origin を削除する。余計な自動化も自分が管理しない名前もない方がまし」という考えによってリモート名 origin が存在しなかった。■だって origin ってリポジトリ名なの？ ブランチ名なの？ 本家なの？ フォークなの？ そういう曖昧なものの上で作業をしたくない。ましてそれ(origin)が他人(git)のお膳立てなら、助けではなく余分な複雑さを持ち込むようにしか思えない。定型のタイプの繰り返しに倦んできた頃に提案してくれたなら考えないこともない……かな？ それでもやっぱり自分は pull は使わないので(許容できるのは checkout や add までであって、自動で merge/rebase は乱暴だ)、origin もいらないんだよな(本家リポジトリにはその代わりにわかりやすい名前を付けます。「
ブランチ名とひと目で区別できるように、リモート名は @ を付けたり大文字にしたりしようかな」)。■自分にとって３つのリポジトリの関係は「本家―ローカル―フォーク」として捉えられている。でもひょっとしたら「本家―フォーク―ローカル」の想定もあるのかもな、と考えてみた次第。でも自分で GitHub にフォークリポジトリを持たなくても「本家―ローカル(フォーク)」の２者間でもフォークは成り立つので、中心に GitHub 上のフォークリポジトリを置くのは、GitHub の中の人の立場としてならともかく、個人としては順序が違うと思う。メンタルモデルはひとつで十分だ。そのとき GitHub 上のフォークリポジトリは３番目に位置するオプショナルな存在となる(だから意識しなければこれを忘れる>「
フォークする。プルリクエストを出すためには GitHub 上でフォークしたという事実が大事」 新規作成した空のリポジトリにプッシュしても PR は出せないのである)。■しかし GitHub のアップデートによって今後は、GitHub と origin を必須の前提として作業フローからリモートの区別・存在感を消すのがある種最適な選択になるのかもね。本家とフォークの２つのリモート名を使い分ける必要がなくなるのなら、単純化がなされるのなら、割り切りによる制約がむしろメリットと感じられる人もいるだろう。さもなければ無駄に複雑化して面倒なことをしているなと自分は思います。
最終更新: 2021-04-30T21:11+0900
「10分間３問早解き」回だったわけなので４問目(D 問題)は時間中に解けなかった。90 分使っても解けなかった。辺がないケースで TLE が避けられなかった。
AC のきっかけはこのツイート。
chokudai(高橋 直大)ナス@chokudai
D問題、非連結ですって言うだけでDiff400くらい落ちそう
chokudai(高橋 直大)ナス@chokudai
非連結ですって言っても落ちないわ（サンプルにあるし）
連結で出題しないと400落ちなさそう。
「連結で出題しないと落ちない
」がよくわからないけど、ともかく、非連結なら問題を分割できるじゃん、と気がつきました。ツイートを読んで初めて気がつきました。
サンプル４つのうち２つが辺がゼロのケースだったんだけど、極端すぎてそれが全体としては非連結なグラフであること、個々の頂点としては最も簡単な連結成分を構成している、ということがわかりませんでした。そんなことってある？
テストケースが公開されていないので、提出前のテストには一直線の木を使っていた。連結成分の数を増やしても、辺の数を増やしても、探索を助ける制約が増えるだけだと思ったので。
しかしまだ TLE。どういう木が嫌か考えると、この提出は次のような入力に弱い。
だけど次のように番号の付け方を変えただけで問題が問題でなくなる。
たぶん頂点を次数でソートしてから DFS をすれば緩和されたと思う(が、AC 提出では違う方法(先読み)をとった)。
ソートするにせよ先読みするにせよ、２番目の問題に対処するには非連結なグラフを連結成分に分割する必要があったが、それをしないまま DFS の処理量を削減する方法を考えていた、というのが失敗に終わったコンテスト中の時間の使い方だった。
DFS の処理順を次数の降順にしたら悪くなりにくいのか、343 ms からタイムが大いに改善した。このムラが DFS の沼であり抜け出せない楽しみなんだよなあ>20201101p02、20201107p01.05。