Toy と帽子と ADP BE

主にプログラミングに関わる話をゆるくエモくやっていきます

AtCoder Beginner Contest 140

3完。DとFの見合いで最終的にFで突っ走ったのが結果的には立ち回りミスだったかもしれません。でも見えた気がしたんだよなぁ・・・。

各問題

A - Password

これは単純にNの3乗です。

B - Buffet

問題文の通りシミュレーションすればよいです。満足度Cの加算条件に気をつけるくらいでしょうか。

C - Maximal Value

A1はB1、AnはBn、それ以外のAiはmin(Bi-1, Bi)となります。まあAからBを作るときの裏返しですね。

D - Face Produces Unhappiness

私は、反転した時に同じ向きでつながる人数が最大になるような場所を反転させる、でしたが(それでも間違いではないのかもしれませんが)、愚直に実装するとTLEが見えているので少し考えて実装を断念しました。 editorialをみると、やはり私の考察は的外れでしたか・・・。

E - Second Sum

一瞬考えましたが、すぐスルー。

F - Many Slimes

机上で作りうる最大の数字を生成するようにシミュレーションしてみると、パスカルの三角形が浮かんできたので、集合Sの要素の個数を大きいものから累積したものがパスカルの三角形の累積和を超えなければYes、としてみましたが、おおよそ半分までACでそこから殆どがWAとなりました。結果WAなのでこの方針でいけるのかどうかもわかりませんが、仮にいけたとしても、あとひと押しかふた押しが必要だったようです。

まとめ

Dを考え続けるべきだったのかFにチャレンジすることが正しかったのか、未だにわからないです。

水色復帰がまた遠のいてしまった・・・。まあCまでがすんなり解けても、Dが解けないと水色は遠いということがはっきりわかる結果でよかったかもですね。(ポジティブ

f:id:mdstoy:20190907230901p:plain