3完3WA2TLE。レートは上がったが、気分的には大惨敗。
ところで、今回はAR(以下自主規制
各問題
A - Two Sequences 2
nが増えていくに連れて増える組み合わせは、a_1 * b_n
, a_2 * b_n
, ... , a_n * b_n
のn個です。これをn-1までの最大値と比較して、大きいほうを取っていけばよいです。
しかしこれを毎回全部計算しているとTLEしてしまいます(しました)。ここで必要なのは最大値のみですから、累積maxを取ってa_1
からa_n
の最大値が分かるようにしておけば、掛け算の回数はn回で済んで、無事間に合わせることができます。
B - Mex Boxes
こどふぉではおなじみのMexさんです。
これは0から順番に敷き詰めないと隙間ができてしまいMexが減ってしまうので、できるだけきっちり敷き詰められるようにします。
例えばボールに書かれている数が0->3個, 1->2個, 3->1個で、k=4
だった場合、0が3個しかないので余った1つの箱のMexは0で確定、残った3つのうち1は2個しか入れられず、足りない1つの箱のMexが1で確定、2はないので残りの2つの箱のMexは2で確定、といった具合です。
実装的には、mapなりvectorのバケツなりに各数字の出現数を取っていけばよいです。
この考察はこどふぉで慣れているため瞬時に終わったのですが、細かい実装をバグらせ続けて3WA出してしまいました。
C - Robot on Grid
文字が確定していない部分H*W-K
個のマスについて、文字を入れる組み合わせは問題文にも書かれている通り3^(H*W-K)
ですので、全て確定している部分を通った場合の1通りは数え上げる際に3^(H*W-K)
倍されます。そして確定していない部分を通るごとに、X
と、R
かD
のどちらかのみが許容されるため、場合の数は2/3になります。
それを踏まえて、初期値を3^(H*W-K)
としてDPで数え上げしていけば答えが出ます。
ACLのmodintの割り算を無邪気に使ってしまい1TLE・・・。ちゃんとinvを前計算しておきましょう。(戒め
D - Choosing Up Sides
ARCの700点だからまさかありえないよなーと思いながら、純粋にAの位置をスライドさせる実装を書いてみたところやっぱりだめでした。そこで時間切れ。
まとめ
ペナ吐き続けてしまったため、手元にあったはずの青パフォを取りこぼしてしまうという残念な結果に。つまらない実装ミスとか、mod計算で割り算してしまうみたいなもったいないペナが多かったのでなおさら残念です。
とはいえ、水色中位より上のパフォーマンスでレート1300台が見えてきたのでまあいいかな。