脳log[20230312]

2023年03月12日 (日) [AtCoder] 今日あった ARC158 のふりかえり。■A 問題「+3 +5 +7」(茶 diff)。最初にわかるのは、差を２か４単位でしか詰められないから、３数の偶奇がすべて一致していないと揃えられないということ。偶奇が一致していたら、考えやすいように３つの数をすべて２で割っておいた。そうすると１回の操作である要素に１を足し、別の要素に２を足すことになる。１操作あたり３を単位として最大の要素との差が詰まるので、へこんでいる２要素のへこみ具合の和が３の倍数でなければ揃えられない。ここから２つの場合に分かれる。へこんでいる２要素の小さい方に +2、中くらいの方に +1 をしていくのだけど、最小の要素が真ん中の要素に追いつくのが早いか、真ん中の要素が最大の要素に追いつくのが早いか。簡単なのは２要素がへこんだ状態のままお互いの差が詰まる場合。この場合は１操作あたり３の最大効率で全体を均すことができる。一筋縄でいかないのがありがたくもサンプルのいの一番に提示されている、先に２つの要素が並んでしまって１つだけがへこんだ状態になるケース。１要素に +3 することはできないので、２回の操作で３つの要素に(+2+2),(+1+0),(+0+1)することになり、結果的に２操作につき３の効率で差が詰まる。という感じにステップを刻み、泥臭く場合分けをして答えを出した。提出 #39675549 (AC / 269 Byte)。本当はステップも場合分けもまとめられるものはまとめた方が良い。式が３つあればバグは３か所に潜むし、場合分けにより実行パスがテストケースごとに分かれてしまうと、実行されないパスのデバッグ機会が限られてしまう。たとえば、ツイッターでちらりと見かけたんだけど、操作を +0,+1,+2 と見る代わりに -1,+0,+1 と見ることができるらしい。そうすれば２つの場合分けが、まず２要素が並ぶまで次に３要素が並ぶまでの２ステップに共通化できそう(場合分けがステップに変わっただけで減ってないように見えるけど、さっきの提出ではそれぞれの場合で２ステップの処理をしていたので２×２が２に減る見込み)。提出 #39706817 (AC / 194 Byte)。シンプルになった！■B 問題「Sum-Product Ratio」(水 diff)。すべての要素を１以上に限定して考えてみた。分子は３要素の和で、分母が３要素の積。和より積の方が早く大きくなるから、大きい要素を使うほど分子に対する分母の比率が大きくなり、全体として値は小さくなる。逆の場合は大きくなる。本来の問題に戻ると、ここに負の値が加わってきて、さらに正数、負数の個数が３未満だったりして正負混合の場合も考えなければいけない。具体的に考えるよりも最大値最小値を作りうる極端な値(正数の最大最小値、負数の最大最小値)を 12 個まで取り出してきてテキトーに組み合わせることにした。提出 #39678373 (AC)。正直 B 問題の方が A 問題より簡単だった。■C 問題「All Pair Digit Sums」(青 diff)。解けてないよ。繰り上がりをどう処理していいかわからなかった。具体的な組み合わせを考える N^2 が許されない制約だけど、繰り上がりの連鎖は完全に個別の組み合わせに固有なので。組み合わせを考えるにあたり、ある桁について、繰り上がってきた１がある・ないと分かっている集団の内部では、桁の数字で一括りにして計算ができる。案外１の位から順番に繰り上がりの有無で分岐と分裂を繰り返していくと、組み合わせを考えるべき個々の集団は先細りで消えていったりするのかなとムシのいいことを期待したりもして。でもうまく実装できないのでは祈って提出することもできない。足し算をビット演算に分解できないか考えてみたりもしたけど、足し算は消えない。以前に本から抜き出した文が言うように、足し算は強力なのだ。「キャリーの連鎖が単一のビットをその左側にある全ビットに影響させることができるという事実から、広く認識されていない形で、加算を特別強力なデータ操作演算にしている」■■■@2023-03-13 精進。C 問題。kotatsugame さんの動画を見ていたら k 桁目を見ているときにその桁の数字と同時に 10**(k-1) で割った余りを持てばいいと教えてもらった。たとえば A={1234,9876} だとして 10^2 の位に注目しているとき、(2,34),(8,76) を処理対象にする。余りの部分は小数点以下の数字みたいなもの。言われたら、たしかにそれでできそうではあるけど、でも、そういう発想はたぶん待っていても出てこなかっただろうな。提出 #39714388 (AC / 3055 ms)。自分で書き始めたから動画を見るの中断してしまった。3055 ms は他の人の２倍３倍遅い。まだどこか頭を使わずに指を使って数を数えているところがあるみたい。