AtCoder ABC138 参戦記

AtCoder の ABC 138 に参戦しました。

atcoder.jp

結果は 35 分で ABCDE が取れ、早解きできていたためパフォーマンス 1948 となりました。
パフォーマンスは伸びていますが F 問題がとけなかったので非常に悔しいです。

感想

A 問題

やるだけ。

B 問題

やるだけ。一見複雑そうだが頭から舐めて行って逆数作って和をとっていけばいい。

C 問題

1 回合成するごとにその数の最終結果への寄与は 1/2 になるのでなるだけ小さい数をたくさん合成すればよい。
つまり、入力を昇順にソートして頭の 2 個の数をとってその数の和 / 2 に置き換えていけばよい。

D 問題

明らかに頂点に値を足された直後に伝播しようが全部の値を足してから伝播しようが結果には影響ないので

• すべての頂点について値を足しておく
• あとは根からたどっていってたどるごとにその頂点の値を足して次の探索を行う

で答えになる。

E 問題

• t に使われている文字のうち s にないものがある -> 不可能
• そうでなければ可能。必要な文字数は、t を頭からたどっていってそれに対応する s (リピート可) の文字をとっていけばよい
  • そのまま計算するととんでもないことになるので、以下で計算量を削減する
    • t に出てくる文字について s の何文字目になるかを計算しておいて同じ文字に関して昇順にソートしておく
      • 同じ文字が複数個ある
    • 実行時には t[i] が a 文字目だとすると t[i+1] は a+1 文字目から探す。何文字目があたりかはあらかじめ用意した出現文字目を 2 分検索すればよい
      • なければ s の先頭にもどる

F 問題

• と の最上位ビットが同じでないと とならない
  • の最上位ビットが小さい場合は に の最上位ビットが残る一方、 からは の最上位ビットが消える。
• このとき は となる。
• となるのは のビットがすべて でも立っているとき。
• 上記より に対して条件を満たす は の範囲だと で立っているビット数を としたときに 個となる
• については
  • の最上位ビットが同じ数だけ考えればよい。

ぐらいまで考察できたがそれ以上続かない...