AtCoder ARC122A "Many Formulae"をRubyで解く
レート溶け散らかすやん。
今回解くのはこれです。
写経元
自力ACできなかったので、今回はtompngさんのコードをパク……じゃなくて参考にさせて頂きます。
良い式のパターンを実験
一発で解法を思いつくのは変態だと思うので、「良い式」がどのようになるか実験してみます。
数字がaの1個→良い式はaの1個
数字がa,bの2個→良い式はa+b,a-bの2個
数字がa,b,cの3個→良い式はa+b+c,a+b-c,a-b+cの3個
数字がa,b,c,dの4個→良い式はa+b+c+d,a+b+c-d,a+b-c+d,a-b+c+d,a-b+c-dの5個
数字がa,b,c,d,eの5個→良い式はa+b+c+d+e,a+b+c+d-e,a+b+c-d+e,a+b-c+d+e,a+b-c+d-e,a-b+c+d+e,a-b+c+d-e,a-b+c-d+eの8個
数字がa,b,c,d,e,fの6個→良い式はa+b+c+d+e+f,a+b+c+d+e-f,a+b+c+d-e+f,a+b+c-d+e+f,a+b+c-d+e-f,a+b-c+d+e+f,a+b-c+d+e-f,a+b-c+d-e+f,a-b+c+d+e+f,a-b+c+d+e-f,a-b+c+d-e+f,a-b+c-d+e+f,a-b+c-d+e-fの13個
ここまで実験すれば、大まかな法則が見えてきたと思います。
良い式の法則
元の式に数字を1個追加する場合に、大きく2つの法則があります。
1.数字が1個増えた場合、最後の数字は+で追加するか-で追加するかの二通りしかない。
2.元の式のうち、増えた数字を+で追加するのはすべての場合で可能。元の式の最後が-だった場合、-連続禁止ルールに引っかかるため増えた数字を-で追加する事はできない。
文字だけだと意味不明ですね。例として数字を3つから4つに増やす場合を考えてみます。
数字がa,b,cの3個、良い式はa+b+c,a+b-c,a-b+cの3つ。
そのうち最後の数字cが+されているのは
a+b+c
a-b+c
-されているのが
a+b-c
でした。a,b,cにdを追加して4個にした場合、+dした場合の良い式は
a+b+c +d
a-b+c +d
a+b-c +d
-dする場合、a+b-c-dはダメなので
a+b+c -d
a-b+c -d
DPできそうな気がしてきましたね。
漸化式
数字の追加に必要な変数は「+で終わっている式の個数」「-で終わっている式の個数」「+で終わっている式の総和」「-で終わっている式の総和」の四点です。
DPなのでこれら全てに「古い」と「新しい」の二通りがあるため、ループの中で8つの変数が飛び交う事になります。いや「追加する数」もあるから9個か。
「新しい」「+で終わっている式の個数」←「古い」「+で終わっている式の個数」+「古い」「-で終わっている式の個数」
上の例でも+cで終わっている式が2個、-cで終わっている式が1個。この全てに+dする事ができるので+dで終わる式は3個でした。
「新しい」「-で終わっている式の個数」←「古い」「+で終わっている式の個数」
+cで終わっている式にのみ、-dを追加できます。
「新しい」「+で終わっている式の総和」←「古い」「+で終わっている式の総和」+「古い」「-で終わっている式の総和」+「新しい」「+で終わっている式の個数」*「追加する数」
a+b+c+d+a-b+c+d+a+b-c+dを前から順に計算してたら間に合いません。(a+b+c)+(a-b+c)とa+b-cを足して、そこに3*dを足せばOKです。
「新しい」「-で終わっている式の総和」←「古い」「+で終わっている式の総和」-「新しい」「-で終わっている式の個数」*「追加する数」
(a+b+c)+(a-b+c)から2*dを引けば算出できます。
ACコード
最初の1文字目aは便宜的に+aとして扱います。なので「+で終わっている式の個数」が1個、「-で終わっている式の個数」が0個、「+で終わっている式の総和」がa、「-で終わっている式の総和」が0になります。後は入力された数字を前から漸化式でDPしていきます。
出力は全ての良い式の和なので、「+で終わっている式の総和」+「-で終わっている式の総和」を出力して終了です。
これ茶diff、つまりレート783の人でも5割は解けたの!？ マジで!？
Discussion