(N-M+1).times (0 から N-M までの繰り返し) から [*0..N-M+1] (0 から N-M+1 までを値とする配列) に書き換えたときに off-by-one エラーを仕込んでしまって合わないサンプルに困ってしまった。デバッグプリントで解決。■C 問題 Truck Driver。しばらくわからなくて目の前に沼が広がって見えた。２つの条件に合う範囲をそれぞれ二分探索で求めて考え合わせる。気がつけばこれだけ。■D 問題 Neighbor Distance。お隣さんがわかれば差分更新できる。BIT で管理するんだけど、X の値が大きいので座圧が必要。今でこそ座圧なんてやるだけ面倒なだけに見えて制約で手軽にいじめられてるなこのひと手間必要でしたかなんて考えてしまうけど、「座標値(-10^9 以上 10^9 以下の整数)でなく座標値の序列(N個以下とM個以下)でグリッドを作るって発想が出てこないんだよなあ」なんて初々しい感想を書いていた時期が自分にもありました。座圧ができれば橙 diff の F 問題「. (Single Dot)」が解けた時期が AtCoder にはありました。WA になった最初の提出まで 24 分かかってるんだけど、実装に取りかかる前に強制うんこ休憩に襲われて急いで E 問題を読んで駆け込んだのだった。なお E 問題のロリハ方針が決まってもまだ出られなかったもよう。WA の原因は番兵が小さすぎたこと。番兵との距離が１しかないならいないはずの番兵との距離を答えに計上して間違える。修正に２分。■E 問題 Shift String。入力が素直に２進数に見えるのでハッシュ値を比較するのもハッシュ値を差分更新するのも自然に行えると思う。マルチテストケースであり問題の見た目から基数に２が選ばれやすいだろうから、ありがちな素数の組に対してハッシュの衝突が狙いやすいと思ったけど、AtCoder で最も有名な２つの素数を使っていても大丈夫だったみたい。■F 問題 Back and Forth Filling。50 分弱残して解けなかった。似た設定でこれより答えやすい問題を見たことがある。自分の左右に最低いくつ最大いくつの数があるかを DP で求めて BIT で区間 add をすれば答えの C 数列が得られると思ったけど、サンプルが合うところまでいかなかった。■コンテスト成績証。737 位、1502 水パフォ。Array#index に投げるのはケチだから。■C 問題 Odd One Subsequence。数列から(位置が)異なる３つの要素を選ぶ方法。Array#tally で集計して計算する。同じ数字を２つ選ぶ方法は nC2 で、残りの数字の選び方は N-n。■E 問題 Hit and Away。難しいから 425 点になっている D 問題と、E 問題だから 450 点の E 問題。解きやすいのも解いて得するのも明らかに E 問題なので D 問題を読まずに先に E 問題を開いた。最初は危険な頂点を起点にしてじわじわ広げていく陣取り的な操作を考えた。UnionFind かな、重み付き UnionFind かなと考えていって、いつもの UnionFind を書いたりもしたんだけど、詰めていくと、安全な頂点を始点にして始点により区別されるパスに先着２つまで訪問を許す BFS になった。■D 問題 On AtCoder Conference。実数 x で定義されるけど実際に求めるのは M 未満ゼロ以上のすべての整数についての合計。M が大きい。そうすると N 人の人の立っている地点と地点のあいだをすべてひっくるめて処理する必要がある。隣り合った人と人のあいだを始点とする X はどれも同じ値になるので。人と人のあいだと日本語で書くときはいいけど、実際に書く処理ではどちらかを含まない半開区間にする。どちらかっていうか、仲間はずれは区間の右端なのでそれを含まないようにする。A 数列は M を足した２周目を加えて倍加して計算しやすくする。複雑だけど 17 分でサンプルがあったから提出したら TLE×3 (#70444180)。手元でいくつかの種類の最大ケースを作ってみたけど再現できず。たぶんだけど C 人先の人が C-1 人先の人と同じ値のときはもう一人先を見る、という繰り返し処理を毎回律儀にやっていたのが良くなかった。尺取りなんだけど一端を進めたときにもう一端を(添字に C を足して) C 人先にリセットするとそれが手戻りになることがあり重複処理がかさんで TLE になっていたのだと思う。６分で修正して AC (#70446347)。■コンテスト成績証。運営者 検証され信頼できる運営者情報はありません」にもかかわらず「
安全な接続 このサイトとの接続は安全です。認証局: DigiCert Inc」って表示されるな。誰も接続先の確かさには興味がないまま無責任なことを言っているみたい。ユーザーが無事に新ドメインにアクセスしたときも、ユーザーが認証情報を管理していないのだからどうすることになってるんだろう。■ユーザーがパスキーを管理する例。「パスワードの代わりにパスキーでログインする - Google アカウント ヘルプ」のページに「
パスキーを削除 / オプトアウトする パスキーを作成したデバイスを紛失したり、共有デバイスでパスキーを誤って作成したりした場合は、Google アカウントで使用するパスキーを無効にする必要があります」とあって、Google アカウントでの操作が案内されている。それで紛失したデバイスや共有デバイスからのアクセスをブロックできるとしたら二段階認証の段階で可能なことに思える。逆にそうでないとパスキーとは盗聴のための仕組みなのかと、自分が関知しない通信をどこへどれだけ行っているのかと疑う。パスキーはあくまでも１要素目(パスワード)の代替ということでよろしい？ そしてやっぱり思うのは、認証情報のデバイスをまたいだ一元管理とオンライン同期は別の話であって、Google に一元管理させる一手はない。管理主体は自分自身以外ありえないし、それができない仕組みなら欠陥がある。■第三のサーバー。「パスキーの仕組み・設定方法・注意点などを知る (キヤノンMJ セキュリティ on ASCI)」。自分はこのページの図の９番に対応した FIDO サーバーの存在を認知していなかった。現在のパスワード認証でも外部のサーバー(Google、Apple、Yahoo とか)に当たり前のように認証を投げていて、口座情報や住所を押さえていて自分にとってよりクリティカルな地位を占めているサービスが第三者のお墨付きを鵜呑みにするのでいいのかと思わないではないし利用しないんだけど、してみるとパスキーはこれの延長上にあると見える。クレジットカードもそうだけど、無駄にプレイヤーが増えて関係が複雑になりコントロールが容易に自分の手から離れていく状況は避けたいと思っている。便利さならシンプルさのために捨てていい。次から次へと、未だパスキーの全貌が把握できたと思えないので、自分がパスキーを使うのはまだ早い。一見安全だろうが一見便利だろうがよくわからないコントロールできない長いものに巻かれたくはない。
n^C mod n = X とはどういう意味か。とりあえず X<n が必要だけど、これは別に答えを規定しない。n^C が n より小さくなるとき、n^C = X であり、n = X^C。これが答えの候補の１つ。では n^C が n より大きくなるとき、n^C = n+X であり(本当？ n+n+X は？ 知らない)、当然のこと X<=C であるはず。X<C の場合は知らず X==C のときはテキトーに大きなフルビットの数((1<<31)-1 とか)^X が答えの候補になる。これが２番目。これが ABC の問題や 300 点 400 点の問題ならもう提出してしまうけど、700 点なのでまだ手を尽くす。数ビット程度のランダムケースと愚直解を眺めていると、他にも答えの候補があるが見つけられていないとわかる。いくつかのケースでどうすれば C と X から N が導き出せるかビット列をずーっと眺めていたら、C-X が偶数のとき、つまりこれが X<C のケースなのか、(C-X)/2 にテキトーに大きなビットを補ったものが答えの候補になるらしかった((1<<30)+(C-X)/2 とか)。これが３番目。残り時間が５分だったので時間切れにならないように注意しながら数分を使って愚直解と答えを突き合わせてももう未知の答えはないらしかったので提出して AC だった。A 問題が全く望み薄だったおかげで B と C に使う時間が十分に確保できたのが良かった。■コンテスト成績証。1803 の青パフォでした。各頂点の出次数が１以上」というのは行き止まりがないという意味だった。構造がよくわからないままメモ化再帰でがんばった。■F 問題「Not Adjacent」。E 問題と点差が 25 点しかないなら点数の高い方を解かない理由がない。解けるも解けないもどれだけ時間がかかるかもほぼ同じだと仮定すればね。直前の要素を使った場合と使っていない場合の２種類に分けて DP をするのだと思った。提出 #70054346 (TLE×31/AC×22)。21 分かけて完成したものが TLE だった。答えを出すのにいっぱいいっぱいで高速化のアイデアはないので E 問題に行った。E 問題を 21 分で通してから戻ってきたら残り 10 分で、最大ケースを書いて進捗を表示してみたら半分くらいまではまともな時間で動いているようだった。半分全列挙だな。と思ってコンテスト終了前後に３回提出したけど、どれも WA だった (#70062539、#70064082、#70064700)。この日記を書いている最中にひらめいて提出した４個目でやっと AC (#70067158)。３回も何をしていたかというと前半後半のマージをするのに２×２の組み合わせの何が有効で何が無効かを判断しなければいけないのだけど、有効にしすぎ、無効にしすぎ、ちょうどいいという変遷をたどっていた。ちょうどいいのに WA になっていた原因はというと、DP をする順番に意味があるのです。ただ個数を半分にするのではいけない。前半は前から DP をし、後半は後ろから DP をすることで、最後に両者をマージしたときに正しい答えが出る。「
A の（連続するとは限らない）部分列」についての問題を解いているなんてことはもうとっくに頭の中から抜けているので順序が大事だということにきづかない。ちなみに、一方の値が 0 のときにもう一方にある M の倍数を作るペアが M-0 ではなく 0 (=(M-0)%M) だという罠にははまらなかった。これが初めてというわけではないので。■E 問題「Wind Cleaning」。144 ビットでグリッドを表現して BFS をしたけど、これは Ruby に甘えていたのかも。128 ビットに収まっていたなら C++ でも書けたと言い訳できるけど。上下左右への移動をいざ書いてみたら思いのほか簡単に、シフトしてからマスクとのアンドを取るだけで移動後のグリッドが得られた。提出まで 21 分。■点数にならなかった F 問題への寄り道で E 問題の AC が 20 分遅れたにもかかわらず 1509 パフォが出ていることに驚いている。コンテスト成績証。AI 新ルールによる追い風が絶大では？