記録
yukicoder contest 359 - yukicoder
まったり参加で3完, 約100人中55位でした
解法・反省
A
No.2063 ±2^k operations (easy) - yukicoder
提出 18:25 (0)
これは1問目としてはなかなか難しかった.
だが, 2進数で与えられるのでそこらへんの面倒くささはない.
もし10進数で与えられたら
Pythonを使いましょう.
Pythonではこのような巨大な数でも(ry
この問題の考察としては, かなり
エスパーに頼ったところがあった. 100000 - 100 = 11100 というパターンか, 10000 + 100 = 10100 というパターンの2つがあることを特定する.
それ以外で, 1000000 のようなパターンでは
, 他は
となる.
確実な考察としては, プラス, マイナスの操作を4通り考える. 操作は可換だから, 本質的には3通りしか考えなくてよい.
2回ともプラスのとき, 100000 + 100 = 100100 のように, bitに2つだけ「1」が存在するようになる. 100 + 100 = 1000 のようなパターンもあるが, このとき
が簡単に分かるので駄目.
2回ともマイナスのとき, これは
となるから考えないでok.
プラス・マイナス両方のとき, 100000 - 100 = 111000 のように, 途中まで1, そこから全部0というパターンを持つ.
これを適切な実装で判定すればよい（ここは茶Diff程度の難易度）
提出
Pypy3
#794648 (PyPy3) No.2063 ±2^k operations (easy) - yukicoder
B
No.2064 Smallest Sequence on Grid - yukicoder
提出 42:59 (1)
マス目の移動はいつものやつで, めっちゃDPっぽい.
辞書順は前の文字の小ささを優先するが, 複数の候補のうちに決め打つと後の文字の小ささで裏切られる場合がある.
複数の候補を全部持ち, BFSのように遷移するようにするとそのパスは全部目的の文字列のものと同一である.
だから, 最終地点
から探索した地点をたどるように復元していけば, 目的の文字列が得られる.
解いていて気持ちよかった.
提出
PyPy3
#794793 (PyPy3) No.2064 Smallest Sequence on Grid - yukicoder
C
No.2065 Sum of Min - yukicoder
提出 72:32 (0)
シンプルな問題文でいい感じ. もし
区間が全体であったら, 二分探索を使えば簡単である.
まず,
をソートして,
より小さいものの個数を
として, 答えは
となる.
ABC255-Dのような問題だと上のようなアプローチが使える.
しかし, 今回ではそのようなアプローチが使えない.
しかし,
平方分割を使うと, 上のアプローチが平方で分割された
区間内に適用できる.
これは蟻本のpp.168-170のアプローチと同一.
数列を
くらいの大きさの
区間（
バケット）に分割し, あるクエリについて, そのクエリで要求される
区間がある
バケットを含むなら, その
バケットに対して上のアプローチで問題を解く.
残りの部分は1つずつ愚直にやっていく.
バケットの大きさを
として,
バケットに対する解は
で求められる. 残りのやつの愚直も
だから, 最終的に
.
結局
で求められる. 前処理は, ソートをいっぱいするので
.
ぼくはそれに気づかず
として次のぼくの記事のような平方分割を書いた.
日記 平方分割を実装してみた - しょぼんブログ
提出
C++
#794912 (C++17) No.2065 Sum of Min - yukicoder
反省
どの問題も面白かった. D以降も解けたらここに追記していこうと思う.
ぼくの平方分割が少しバグりやすい形をしていた.（平方分割記事は修正した）
