L+1 を L に変更しただけなんだな。off-by-one エラーってやつ。TLE である 04_corner_11.txt はどんなコーナーケースか。ppppp....ppppp だろうことは想像に難くない。■提出 #34804490 (AC / 64 ms)。連続する p を一塊で扱うようにした。一番後ろの p を使わないで得をすることがないので。■■■C 問題「Lights Out on Tree」(水 diff)。与えられた頂点集合の上下関係を知るためにダブリングを書いたり、深さの偶奇が関係するかと思って深さを記録したりしたけど、実は直接の親子関係しか関係しなかった。ボタン操作の基本は「表向いてる親を裏返して、つられて反転した子孫ノードを裏向きに戻すために直接の子を再度裏返す」なんだけど、直接の子が最初に表向きだったノードなら操作回数が節約できる。■提出 #34798597 (TLE×18)。クエリのたびに子ノードのリストをたどる愚直解。■提出 #34799643 (AC / 422 ms)。子ノードは数だけ数えておいて一律に操作回数を計上し、子から親を調べることで足しすぎた分を引く。終了 12 分前に２完のノルマ達成。■■■B 問題と C 問題の配点が同じだから AC の２完遅解きは AB の２完遅解きと同じであり、２完遅解きは A の１完早解きに毛が生えたパフォーマンスしか出ない。-27。ARC にはレートを吸われてばかり。上昇したレートだけ数えたらもう赤なのではないか(頭がパー)。未来のレート上昇を演出するために現在のレートを捧げるのだ。2つの文字列のどっちを前にした方が得か考えてソートするのだ」というのが無意識に作用していた。二項関係だけでソートしていいんだと、知らずに気付かされていた。推移律はどうですか？ よくわかりませんよね。祈りながら提出したら AC だっただけです。■ゴルファーの提出(#34766963)を見てると複素数を使ってるんだけど、そういえば自分が書いたソートのための比較関数が外積と同じ式だった。この前の外積を使う問題(ABC266-C「Convex Quadrilateral」)を自分は複素数で解いたから(#34376180)、なにかしら関係があるのだろうか。ソートからどうして複素数が出てくるのか飛躍がありすぎてさっぱりわからんけど。「（解説を見て）なるほどこれ「Xの個数/1の個数」の降順にソートしてたのか」という声もあるけれど、こちらもさっぱりわからない。俺にもなるほどさせてくれ。
職場に一人はいる」という表現で一人対その他の構図を設定するところが卑怯だし生理的に受け付けない。
center = now #中心 とあるな。……使われてないけど。770 ms と自分の倍くらい速いのなんで？ 直径を構成する頂点のリストを用意して、U から直径までの距離を愚直に(１ずつ)数えてる。１回のクエリごとに高々半径と同じだけの遡行回数で直径に行き当たるだろうけど、それでいつでも大丈夫？ しかしこんなややこしいことをしていて早いし速いし間違えてないのすごいなー。■直径を幹として他のすべての頂点を幹から分かれた枝(※)と見る木のイメージはこれまで持ったことがなかったなあ。※枝の長さは分枝点から直径の両端までの距離のうち短い方より短いか同じ。■提出 #34582537 (tinsep19 さん / 1606 ms)。クエリ先読みもありか。そうか。まねまね>提出 #34647156 (AC / 1826 ms) うーん、遅い。■■■精進２。先週末あった ARC147-C「Min Diff Sum」(青 diff)。コンテスト中に三分探索を書いていたんだけど、そのときも今日も３分点を求める式を間違えていた。(l+l+r)/3 とか l+(r-l)*0.3 が書けなかった。もっとも、それが書けても不満度を妥当な計算量で求めるのがまた難しかったんだけど。この部分問題には ABC の C 問題と D 問題の中間くらいのポジションをあげてもいいと思う。■提出 #34655113 (TLE×23)。三分探索が書けて判定式が書けて不満度の計算ができても、ローカルで６秒かかっているのでジャッジサーバーでは３秒くらいかかると思う。TLE。■提出 #34656235 (AC / 746 ms)。ループの中の線形時間の処理を累積和＋二分探索に書き換えて AC。■提出 #34660104 (AC / 1739 ms)。整理していくと結局区間の左端の数と右端の数を数えるだけになって、三分探索も二分探索も不要になった。速くなるかなと思ったけど倍以上遅くなった。さっきの 746 ms がソート(NlogN)+累積和(N)+二重探索(log^2(N))で、今度の 1739 ms がソート(NlogN)+線形探索(N)。オーダーは O(NlogN) で変わってないけどね、だからこそこんなに差をつけられて、しかも負けてるのが納得しがたい。考察が進んで遅くなるとか……。ローカルで若干速くなってるものがジャッジサーバーでは２倍遅くなってたりするから、ジャッジが詰まりまくってた影響があったりする？ あとローカルでは入力の受け取り方を変えるだけで３秒が２秒になったりした。入力サイズがでかい。■提出 #34661754 (AC / 658 ms)。ちょこっと速くなった。二重探索に対して妥当な改善だと思う。あたうる限りの努力」という初めて見る表現があって、気持ち悪いなあと思った。それ以前から「
できうる限り」というあまり珍しくない表現も気に入らないと思っていた。だってね、「～しうる」という表現にすでに可能の意味があるのに、～するの部分にできるを当てはめるのは二重表現に思えてくどい。「できる限り」で十分なところでもったいぶって「できうる限り」なんて気取ってんじゃねーよ、という感想が先に立つ。■「あたうる限り」はどうか。これには「できうる限り」の「できる」にさらにもったいを付けて「あたう」に置き換えただけではない悪さを感じる。つまり、「～しうる」に接続するのに「あた(う)」でいいのですか、という疑惑。あたうの「う」と～しうるの「う」の音が同じだから、つい、くっつけちゃったんじゃありませんかという寸詰まりの据わりの悪さ。■「あたう(能う)」について ATOK で明鏡国語辞典を引いたら自動詞五段活用らしい。「～しうる」についても一応引いて、動詞の連用形とともに複合動詞を作ることを確認した。「あたう」の連用形とは何か。「あたい」になりそう？ ところで、明鏡で「あたう(能う)」を引いたときにそのものずばりこう書いてあった。「
「能う限り」を「能うる限り・能ううる限り」とするのは誤り」。２つの誤用例のうち「あたうる限り」の方は我が意を得たりでわかる。次に考え得るのは「あたううる」なの？ 「あたいうる」の扱いがないのがアリだからなのかそれとも想定外なほど完全にナシだからなのか判断できない。もちろん「あたいうる」が仮に合法でも、気取ってんじゃねーよ、という感想をもつだけだけど。■■■珍しくない表現と問題提起だったらしい。「「あたう限り」？ 「あたうる限り」？｜NHK放送文化研究所」「「できうる限り」か「できる限り」か | 毎日ことば」「首相演説の「能うる限り」は「能う限り」の誤りでは？ | 毎日ことば」 五段活用は五段活用でもワ行五段活用であるらしい。いくつかの活用形がないんだっけ？ 連用形がなさそう？
What does the expression SCHAR_MAX == CHAR_MAX evaluate to?」 char の符号が処理系定義なのは知ってたけど、処理系定義と未定義を混同した。だいたい符号付きにされるから成り立つ(1)のを正解にするってさ。それとあとになって気がついたけど、この問いに答えるには SCHAR_MAX と CHAR_MAX の型の異同について考えるだけでは足りなくて、int 型へ昇格されて比較された結果がどうなるかを答えないといけなかった。だってビットパターンは２つとも同じなわけだから(追記：嘘だよ。符号付き最[小]値と負号無し最[大]値の話になってるよ)、型が異なることが比較結果が偽となることを即座に意味しない。左のように書いてから疑いを持って検索したら、C++ のリファレンスではあるけどこう書いてあった。「
具体的な値は実装依存であるが、127（2^7 - 1）以上であることが規格で定められている。このマクロによって定義される値の型は int である。」 SCHAR_MAX の型は最初から int であると。そんな気がしたぜ。ちなみに UCHAR_MAX についても「具体的な値は実装依存であるが、255（2^8 - 1）以上であることが規格で定められている。このマクロによって定義される値の型は、 unsigned char の全ての値が int で表すことができれば int、そうでなければ unsigned int である」とあるので、基本的に int であると。UCHAR だけど char でもなければ unsigned でもないと。■「
Assume x has type int . Is the expression x<<0 ...」 負の数の左シフトはシフト数によらず定義されないそうで。■「
Assume x has type unsigned short . Is the expression x<<31 ...」 unsigned short の昇格先としてつい unsigned int を期待してしまったけど、int で十分だから int だった。C 言語の int 好きを十分頭に入れてクイズに臨んだのにほころびが。■「
Does evaluating the expression INT_MIN % -1 invoke undefined behavior」 最後の問い。選択肢が「Who knows」(不正解)しかない。他の選択肢があっても普通に答えが返ってくると思ってたから不正解で間違いない。これの結果を保証すると効率に響くという不都合な式らしいけど、コンピュータの気持ちで余りを計算することができないので INT_MIN の何がまずいのかわからず。ひょっとして
-INT_MIN が存在しないことが関係する？■■■近くにあったツイートでこちらが目に入った。「科学としてのソフトウェア工学研究の危険性。ほとんどの「定量的な結果」は非常に限定された条件下でのみ意味があるのに、ときにそれを金科玉条のようにして議論が進められる。この結果起こるのは、データに現れない心理的な部分の軽視である。 https://t.co/Shrb4HQn6G」■この手の指摘をつい最近オープンダイアローグの文脈で読んだ。この本『開かれた対話と未来』。オープンダイアローグの個別的な性質から成果を科学的に評価するのが難しいそう。難しいけどやってるみたい。■英語が不自由なので流し見だけどリンク先を読むと、新型コロナのときにも見られた「根拠はあるんですか」を戒める内容ぽい。つまり、有望そう妥当そうではあるけどまだ根拠がない論を「根拠は？」で潰して、安い根拠をそなえた愚策次善の策をありがたがるなよと、そういう雰囲気。私見ですけどね、データが必要なのは凡人と秀才だけで、馬鹿と天才にはデータの裏付けなんていらんのですよ。問題はデータがないと馬鹿と天才が見分けられないことで……。F = lambda{|a,p,k| } のシグニチャが見いだせたら９割解けている。それがなかなか解らなかった。シグニチャとは、親が p である(p の色は決定済みである)ノード a が取り得る色が k 種類のとき、a を根とする部分木を塗り分ける通り数。■提出 #34462566 (AC / 262 Byte / 313 ms)。こんがらかった考えをお風呂で整理したら、９行目の K-1,K-2 の場合分けが自然に出てきて、するするっと実装が完了しました。昨日から何度も解けた気がしては答えが合わないということを繰り返していたのにね。
.min だった部分を .then(&@m) に書き換えただけで通ってしまうのだなあ。あと細かいことだけど、コンストラクタに lambda を渡したのは失敗。ブロックが普通。b = a^x; (b&x)-(b&a) を書いた。これの間違いは A の方が X より大きな MSB を持つときに、それを操作(足し算)回数の節約には利用できないし、ましてや負の操作回数によって操作回数を貯金することもできないのにしてしまっているところ。■提出 #34171598 (WA×4 / TLE×10)。さっきの提出の修正版。BIT の添字の操作と同じように LSB を順番に取り出して、節約できる操作回数を正確に数えるようにした。WA が大幅に減って TLE が生じてるのはその結果。ではすべてが TLE になるのではなく依然として WA が４つあるのはなぜか。解を二分探索しているのだけど、MSB が異なる２つの解を比較したとき、ある要素 A にとって小さい方の解では無視されたビットが大きい方の解では操作回数の節約に利用できるという状況が起こりうる。判定に単調性がない。■……１時間経過。提出 #34178565 (TLE×1 / 5307 ms)。解の MSB が同じなら単調性があるわけなので高次のビットから 0/1 を決める方針。１ケースだけ 307 ms オーバーした。■終了後の提出 #34182184 (AC / 2052 ms)。判定が済んだ部分について入力のビットを折っておくことで時間の節約をした。そうすると決めて時間があれば書き換えはただの作業。■あわや緑落ちかというところまで下降しているレートにとっては１完でも +1 だったので、悪い日ではなかった。