久しぶりに筋トレをした。今日は腕立て。

---

最近弛んでしまい、朝起き出すまでが長くなっているので直したい。

---

ARC158に参加した。

A: まず、差だけが重要なのでソートして最小値を引いてx1,x2,x3を0,a,bとして考える。+3,+5,+7は+0,+2,+4ということにする。

この時いくら操作をしても偶奇は変わりようがないので、a,bのいずれかが奇数の場合は不可能。以後はA=a/2, B=b/2ということにする。+0,+2,+4は+0,+1,+2として考える。

操作をするたびに和は3ずつ増えていくが、3つの値が等しいなら和は3の倍数のはずで、もし最初の時点で和が3の倍数でないなら3の倍数にはなりえない。(A+B)%3≠0ならば不可能。

B=2Aのとき: 0,A,Bに+2,+1,+0をA回やればよい。これが最善。

B>2Aのとき: 0,Aが低いのでそこ2つを叩いて最小値からの差が1:2になればよい。+1,+2,+0と+2,+1,+0をすれば+3,+3,+0になるのでそれをしまくる。B-3n=2Aと考えると(B-2A)/3回やればいい。B+Aが3の倍数であることからB-2A=B+A-3Aも3の倍数であることが分かる。

B<2Aのとき: 0だけが低いのでそこを集中的に叩く。+2,+0,+1と+2,+1,+0をすると+4,+1,+1になるのでそれをしまくる。差で考えると+3,+0,+0になる。(B-3n)=2(A-3n)と考えると(2A-B)/3回やればいい。

どうにかして最小値からの差が1:2になるようにすれば良さそうだなと考えてやって実際通ったが、実はちゃんとした証明をしていない。褒められたことではない。そして考察がかなり遅かった。この手のアドホックな考察が求められる問題の速度と精度を上げたい。

なんかアドホックといいつつ頻出な雰囲気の問題ではあって、3つ組の整数に対して足し算操作を繰り返すみたいな問題は見覚えがある。だいたい和とか偶奇とかに保存量があるので、スッと注目していい性質を取り出せると良いのかもしれない。

B: めんどくさそうな式だが、線形で単調ではあるので、実は考えるべき要素は正と負の値の最大最小各3つだけでよく、全探索しても12^3程度なので余裕で間に合う。こういう乱暴な細かいコーナーケースに左右されない確実な手段を目ざとく見つける能力を鍛えたい。先日のEもある意味そういう発想があればよかったのかもしれない。

C: 冷静に考察を進めたら割とすんなり通せたので良かった。ここは成長を感じる。

基本的な方針は単純に主客転倒。10^aの位がbになるような組み合わせはいくつあるか、というのを考えて行けばよい。10^aの位がpのものがA個、qのものがB個あったなら大雑把には(p+q)%10×A×Bを足せばよさそうと考えられる。ここで扱いが面倒になるのが繰り上がりで、そこは上手く扱う必要がある。

10^aの位の総和を計算する場合について考える。繰り上がりが発生するかどうかは具体的な数値次第なので、各数字についてしっかり考えるほかない。各桁についてO(N)ならO(N log(max(Ai)))なので許容範囲になる。

xiの10^aの位がpであるとする。10^aの位がqであるものがB個あり、そのうちxiと足し合わせて10^aの位に繰り上がりが発生するものがC個であるとする。このとき、(p+q)%10×(B-C)+(p+q+1)%10×Cを答えに足せばよいことが分かる。このBの値は前計算すればよい。問題はCの値だが、10^aで割ったあまりを配列に入れてソートして二分探索すれば求めることができる。これで答えを求めることができた。

Cをすんなり通せたのは良かったが、Bにあまりにも時間をかけすぎたのが痛い。Aももっと素早く通せるべきなのだが、こちらはどう練習すればよいのか分かっていない。

昨日のABCと合わせて課題が見えた感じになった。

• 「頭の良い」式変形によって変なコーナーケースが発生することに敏感になるべき。もっと愚直に近い手段で通せる可能性を考える。
• 保存量に素早く注目する。