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 新ルールによる追い風が絶大では？
全体の計算量は O(K(Q+NlogN)) です」「
K=maxC_i」とのことなので、想定通りの計算量でこの時間らしい。１桁か２桁限定された制約に対して８割くらいの部分点が与えられたら受け入れやすいのにな。
発売されたタイミングから起算して最大4回、最新OSへのバージョンアップが適用されます。適用回数は購入タイミングによって異なります。」が意味わからん。後半はわかるよ、買うのが発売後しばらく経ってからだと購入時点ですでにアップデート済みだったりするのでしょう。わからないのが「最大４回」の部分。これは何も保証してないよね。「
６年間のセキュリティアップデート※8と最大４回のOSバージョンアップ※9に対応し、長く愛用できます」とあるけど、アップデート回数の上限を定めることと長く使えることが繋がらない。好意的に不確かな解釈をするなら、６年間セキュリティアップデートをします、その間に OS アップデートがあれば４回までに限って対応します、ともかく６年間は安心して使用できる環境を提供します、という意味なのかなと思うけど、不確かだ。だって６年間はセキュリティアップデートに関する言及であって、OS アップデートへの言及ではないからだ(注を読めば何が何を修飾しているか区別がはっきりする)。１年目に OS アップデートがあってそれに対応しなくてもリリースは嘘にならない。最大４回は３回や２回や１回はもちろん０回も含むのだから。「最大４回」と宣言されてもこちらとしては何の意味もなさない。後でアップデートをサボったときの言い訳に使えるというそちら側にとっての意味しかない。それが本意ではないなら日本語と論理を学んでくれ。■「
※8 発売されたタイミングから起算して最長6年間、セキュリティアップデートが適用されます」 あらためて読めばセキュリティアップデートも最短６年間が保証されているわけではなかったな。最長６年と言わず最長100年とはったりを効かせてくれても意味がないという点で変わりがないので全然かまわへんかってんで。こちらにとって有益な意味を込めたのなら、伝わるように日本語と論理を学んでくれ。勝手に都合のいいように解釈したら詐欺に遭うのが今の世の中だ。