ABC100-D Patisserie ABC - なんか考えたこと

解けませんでした。コンテスト中に何を考えていたのか、どうすれば解けるようになるのかという自分用メモです。

[本番中の思考過程]

まず、マイナス、プラスに関してmaxそれぞれ求めて、あとでmaxをとればいいの発想(Chocolate bar が頭をよぎった: いくつか候補があるなら、それをすべて求めて最後に比較という考え方)
dp[i]: i個選んだ時のmax。これは、プラス→マイナスの遷移を考えると、dp[i個め][xの総和][yの総和][zの総和]を持っておかなくてはならないという気持ちになり無理筋と判断(RGB Coloring を思い出した: DPのインデックスで無理が出て、DP以外の解法を探す)
x-,y+,z-みたいなときめんどうだなぁという気分になる
ここで、すべての基本は全探索を思い出して2^Nとか思うけどN=1000だからうーん、N² logNくらいまで許容だなぁという気分になる
+-めんどうなので、8通りすべて試したい。そもそも|x|+|y|+|z|=max{ax+by+cz | a,b,c=-1,1}
マイナスが面倒だなぁ
そもそも400なので、貪欲とか累積和とかでは？→貪欲を実験してみるとサンプルと合う
変な貪欲をしていた。

[どうすれば解けたのか]

の2点が大事。

あと、8通り試すのか？という気持ちになったが制約、回せるところを考えると(今回だと+-の8通り、入力の10³通り、x,y,zやその総和10¹⁰)小さいところで回すのが基本なので、8通りくらいならやるかーという気持ちになる必要があった。

あと、シンプルに考える。実装や思考が複雑になってきたら、そもそもの自分の手持ちのカードをよく確認する。

[感想]

結構気づけているのに通せてないのは複雑に考えすぎている気がする…。