blog.bouzuya.net

2020-07-27 M-SOLUTIONS2020 A, B, C, D / ABC115

M-SOLUTIONS2020 A, B, C, D 考察

M-SOLUTIONS2020 A Kyu in AtCoder

各条件を判定すれば良い。

公式の解説などでは 10 - X / 200 が説明されていた。

https://atcoder.jp/contests/m-solutions2020/submissions/15412462

M-SOLUTIONS2020 B Magic 2

貪欲法で解いた。 A < B < C にしたい。 A B C をそれぞれ 2 倍できるがどれも正の数なので A を 2 倍する必要はない。 K 回 (B or C) を 2 倍する行為を繰り返して A < B < C になっていれば Yes 。 A < B になるまでは B をそれ以降は C を 2 倍する。 K と C の大きさ的にオーバーフローはない。

本番では ↑ で考えたのだけど公式の解説を見て A < B < C になるまでの回数 X を数えて最後に X <= K とするほうが簡単そうだったので書き直した。

公式の解説 PDF には全探索による解放もあって確かにそれでも良さそうと思った。

M-SOLUTIONS2020 C Marks

はじめは愚直にシミュレーションしようかと思った。しかし制約を見ると A_i <= 10^9 だったのでこれは掛け合わせるとまずいことを把握して再検討した。

i 番目の K 個の数字をかけ合わせたものと i + 1 番目の K 個の数字をかけ合わせたものの差はかけ合わせた要素のうち左端のものを削除 (評点は積なので除算) 右端のものを追加 (積算) したもの。 A_i は正の整数なので削除する要素と追加する要素を単純に比較するだけで「真に大きいか」という答えは出せる。

https://atcoder.jp/contests/m-solutions2020/submissions/15422909

M-SOLUTIONS2020 D Road to Millionaire

証明なしの雑考察で解いたら通った。

  • 手数料がないので売り買いによる損はない。

  • 売り買いによって利益が出たらそれを全額突っ込むわけだから、全力で売り買いして良さそう。

  • 翌日に値段が上がっているなら、今日のを全力で買って明日のを全力で売ると良さそう。

  • 長期に寝かしたほうが得するかどうか……途中で売って買い直しても手数料のロスはない＆買った値段と売った値段の差額は変わらなさそう。

    • 本番ではこの判断から買い直さなかった
    • 解説で気づいたことだが売って買い直しても同じなのだから「毎日売る」方針にしたほうが簡素にできた

  • 翌日に値段が下がっているなら、今日のを全力で売って明日全力で買うと良さそう。

  • 最後の日は (翌日の値段がないので) 絶対に売らないといけない。

  • 本番: https://atcoder.jp/contests/m-solutions2020/submissions/15433814

  • 終了後: https://atcoder.jp/contests/m-solutions2020/submissions/15462727

E は集落ごとに線を引けば十分というところまではわかったのだけど計算量を減らす以前にひたすらバグらせてサンプルさえ通らなかった。

ABC115 考察

ABC115 A Christmas Eve Eve Eve

d が 22, 23, 24, 25 のどれと一致するかを判定して出力する。文字列の repeat がかんたんにできるなら 25 - d して repeat しても良さそうだ。

https://atcoder.jp/contests/abc115/submissions/15478851

ABC115 B Christmas Eve Eve

合計・最大値を求める。合計から最大値を除いて最大値 / 2 を足して出力する。 Rust には Iterator に sum および max があるのでそれを使っても良い。 p_i は偶数なので 2 で割り切れるため端数は気にしなくてよい。 O(N) なので間に合う。

https://atcoder.jp/contests/abc115/submissions/15478857

ABC115 C Christmas Eve

h_max - h_min を最小にするためには h_i を高さ順にしたとき連続する K 本を見て左端と右端の差を取れば良い。 O(N) なので間に合う。

https://atcoder.jp/contests/abc115/submissions/15478877

ABC115 D Christmas

まずバーガーを構築して下層から数える愚直な方法が取れるかを考えた。入力例 3 にレベル 50 バーガーが 32 ビット整数を超えると書いてあることからこの方法では間に合わない。

バーガーの構造は再帰的になっている。下手に処理すると何度も同じ計算をさせられそうなので何か前処理をしておくほうが良さそうに見えた。各レベルのバーガーに含まれる層 (バン + パティ) の数 S とパティの数 P は前の層が求まっていれば求められる。 S_L は S_{L - 1} * 2 + 3 。前後のバンと中央のパティで + 3 だ。 P_L は P_{L - 1} * 2 + 1 だ。

再帰的な構造の何階層目かは外側から順にもとめていけば求まりそうだ。 X が両端のバンの上や中央のパティの上ならその階層までで答えが求まる。先程の前処理のおかげで両端のバンや中央のパティかどうかを O(1) で判断できる。上半分なら下半分のパティの数を足して次の階層へ下半分なら次の階層へ進めば良さそうだ。

注意しないといけないのは L = 0 だけ構造が違っていて両端のバンなしにパティがあるのでパティの数を数えるときに注意する (1 WA) 。

解説では再帰関数で一気に求めている。ぼくには真似できない。

https://atcoder.jp/contests/abc115/submissions/15479366

リングフィットアドベンチャー 40 日目 レベル 79 ワールド 9 。

10 s 。actix-web 2.0.0 の Getting Started https://actix.rs/docs/getting-started/ を読んだ。

MyBatis の XML をすこしだけ書けるようになった。 <where> とか <if> などを書く。