脳log[20221008]

2022年10月08日 (土) [AtCoder] 精進。今日あった ABC272-E「Add and Mex」(水 diff)。時間中には TLE 解しか作れなかった>提出 #35502733。それを作るのに１時間近くかかっていたこともあって、それ以上詰めることができなかった。改善の目途は TLE が出た直後には立っていて、さっきの提出の 9 行目と 10 行目、操作回数と A の初期値の差が A の添字の倍数ではないときにループをスキップする処理が無駄で、添字と同じだけのインターバルを空けてループの処理対象にすれば条件判断もスキップもいらない。■提出 #35510000 (AC / 421 Byte / 726 ms)。解答の筋道がなかなか立たなくて時間を無駄にした。２、３の要素を組み合わせるにあたり計算量的に間に合うやり方がなかなか見つからなかった。最終的には、答えるべき「A に含まれない最小の非負整数」を 0 からカウントアップしていって、その数字が答えになる操作回数を逆に求めた。それを効率的にやる。