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 だったので、悪い日ではなかった。以下の操作を 0 回以上 N 回以下行うことができます」という制約が付いていた。一応ね、実装前にざっと制約を探しはしていた。でも制約セクションには入力の制約は書いてあっても出力の制約は書かれていなかったのだな。転倒数の総和の最大値はたぶん入力となる数列が逆順にソートされている場合で、0 から 2N-1 の範囲の和(=N(2N-1))になるから、入力次第で操作回数が N を超える。■次に考えたのは、入力の先頭を出力の先頭にとりあえず配置して、次に配置する要素を、出力の末尾との比較によって入力の前の方から貪欲に引っぱってくる方法。考えなければいけないのは、出力の末尾より大きい(小さい)要素が入力の中に残っていないときにどうやってジグザグを維持するか。たとえば出力の末尾２要素が O1,O2 で入力の残りが I1,I2,I3 のときに大小関係が O1<O2<I1<I2<I3 だったら、O2 より小さい要素を入力から選んでジグザグを作ることができない。解決するのは簡単で、入力の先頭を出力の末尾の１つ手前に挿入すればジグザグになる。O1 との大小関係も大丈夫。I1 が O1 より小さいせいでジグザグが壊れるならそもそも苦労していない。この解法のネックも操作回数で、2N の入力のそれぞれに対して 0 回から複数回の操作が必要になる。ランダム入力では N=100000 に対して 180000 回くらいの操作が必要になった。■次に思いついたのは(考えたって書くのやめちゃった)、さっきの解法の例で出した O1,O2,I1,I2,I3 の中で、O2,I1,I2 の大小関係にだけ注目してジグザグが作れるんじゃないかということ。３つの大小関係がどうであれ０回か１回のスワップで山ないしは谷が作れる。(O2 がスワップ対象だけど)スワップによる既成出力への影響はどうか。スワップが必要なのは真ん中の要素が山なら極大値、谷なら極小値になっていなければいけないのにそうではなかったときだから、山を作るためにスワップされたどちらかの端の要素はそれまでより小さくなり、逆に谷を作るためのスワップでは端の要素が大きくなる。山になる要素の隣は谷になるべき要素だから、スワップで小さくなってもジグザグは維持される。谷を作る場合も同じ。■提出 #34071956 (AC / 331 Byte / 212 ms)。N 回のループの各回で１回以下のスワップだから交換回数も大丈夫。精進だからこそトントントンと AC までステップが踏めたんだろうなあ。２番目のトンがなければ AC につながる３歩目のトンはなかったし、次の一歩が出てこないことも２歩目があさっての方向に向いていることもよくあることなので、５割以上の確率で０完になる AGC はリスキーすぎる。緑だったときにレート変動対象から外れて以来不参加だよ。■■■B 問題「Adjacent Chmax」は小さい P から順番に DP かなと思ったけど、何を記録するのかが(実装を始めても)はっきりせず。
低血糖症(ハイパーグリセミア hyperglycemia)」と書かれていた。低なのに hyper？ hypo では？ と疑問に思って検索したらやっぱり Wikipedia には hypoglycemia と書いてある。そうだと思った。■ここからが自分の鈍いところだけど、タイポグリセミアに残っているのはグリセミアであって低～要素が残ってないし、高血糖症からできあがっていていけない理由はないよねって思ったけど(食い違っている症状名カタカナ英語のどれが間違いで訂正すべき対象なのかを考えていた)、ややあって typo と hypo がかかっていることに気がついたのだった。hypoglycemia だから typoglycemia なのであって低血糖症でなければいけないのだった。