Codeforces Round #810 (Div. 1)

　ABの二完。 だが、Eが既出でunratedになったりして大変なことに。

コンテストへのリンク

コンテスト後のツイート

Codeforces Round #810 (Div. 1) ABの二完。
A 二行以上（もしくは二列以上）が必要。
B (x,p)について、[x-p,x]（傾き1）,[x,x+p]（傾き-1）とそれ以外に分けて処理。それぞれ、y=h-x,y=h+x,y=xの、範囲最大値を取るセグ木で処理。

— titia (@titia_til) July 24, 2022

C. XOR Triangle

　解説AC。難しいが、手順を踏めば解ける問題という気もする。

　入力が01列で与えられているので、桁DPを使うんだろうなぁ、ということは分かる。

　その後の考察は難しいのだが、桁に注目して実験などすれば、a,b,cのある桁での値を000のように三つの数字で表すと、

・011か100の箇所が一ヶ所以上ある

・101か010の箇所が一ヶ所以上ある

・110か001の箇所が一ヶ所以上ある

　という条件を満たせば良いと分かるのだろう。解説に証明は載っており、証明を理解するのは難しくないが、この道筋で導出するのは困難な気がする。

　あとは、これを桁DPする。

・DP[i][j]で、iはa, b, cがMAXと一致しているかの八通り,  jは、011/100, 101/010, 110/010 を使ったかの八通りを持つ

　そして、a, b, cの各桁に0/1がきたときどうなるか、という遷移を考えれば良い。

　言われれば書けるけど、コードに直す部分も難しいなぁ……。