HUPC(Hokkaido University Competitive Programming Camp) 2023 day1 参戦記

ソロオンライン参加 9完10位

各問題の考察内容

ここでの問題順番はAC順.

B: Merge Sequences

$NM$ 個を全て列挙は当然できない. そこで, 大きい $K$ 個のみを列挙しなければならない.
列挙する必要がある数のうち, 最小の値が分かっていればそれ以上の値になるものだけを列挙すればよくなり, 判定も構築も二分探索でできる.
かなり典型度が高い問題なので実際は考察を挟まず実装に手を付けた.

C: Range Same Query

全て等しいことと, 最大値 $=$ 最小値に気づけるかが肝.
前者は基本的には範囲内の全ての要素を確かめなければいけないが, 後者は最大値と最小値の $2$ つの値のみを高速に取得できればよく, segment木を使えば一点更新とも相性ばっちり.

A: Converse and Inverse

二つの操作を同時に考えると大変なので一つずつ操作を吟味する.

長さが $3$ 以上なら区間上下反転で一点上下反転ができる. ( $s_x$ を反転したければ $\lbrack x,|s|\rbrack\to\lbrack x+1,|s|\rbrack$ のように上下反転を $2$ 回行えばよい. $x$ が大きい場合は反対側に寄せる.)

よって, 文字列の長さが $2$ か $3$ 以上かで場合分けをする.

文字列の長さが $2\to$ 操作を全探索
文字列の長さが $3$ 以上 $\to$ 最後に一点の上下反転ができるのでpとb, qとdを同一視してよい. (以下全てp,qに統一.)

これで扱うべき文字種が減ったので見通しが良くなる.
しばらく, 転倒数や偶奇ごとのp,qの数の方針で攻めたがあまり筋が良さそうでない.
次は操作の可逆性から考える.
左右反転の操作は可逆なので, $s,t$ をそれぞれ操作するとして良く, 特に特徴的な形に変換できるか考えればよい.
今回の考察で特徴的な形として一種類の文字のみからなる文字列を採用した.
すると, すぐに以下のことが分かる.

左右反転については, 同じ文字が並んでいるところがあればそれを中心に全体をその文字にできる. (q"pp"qp→"qqqq"p→ppppp)

後は, pqpqpq... のように交互に並ぶ場合であるが, "pqp"q...→qpqq... とできるので, 文字列長が $4$ 以上であれば交互でない場合に帰着できる.
文字列長が $3$ だと pqpかqpqにしかならない.

これで全ての場合の考察が終わったので場合分けや判定を実装してAC.

F: Euler Query

直感的には $\varphi(z)=x$ を満たす $z$ を探しまわるのは困難そう.
そこで, 操作が可逆な事を利用して, $x,y$ を $\varphi(x),\varphi(y)$ に置き換える操作と考えることにする.
ここまでくると, かなり最小共通祖先の香りがしてくる.
実際, $1\le \varphi(n)\le n$ で, $n\gt 1$ の時は二つ目の不等号の等号部分は外れるので, $\varphi(n),n$ に辺を張れば木になり, まさにLCAとなる.

I: Sum of Tree

問題をみてまず行列累乗かな? と考えた. その後に制約を見て行列累乗だと TLEする場合が有りそうとなった.
経験則からこういう変な制約が見えている時は複数方針を組み合わせれば良く, (cf. ABC032-D: これは大分見え見えな例) 今回も愚直解と組み合わせればよい.
計算量を吟味せず, 行列累乗の方は $N\le 100$ 位だろうの肌間隔で投げたらTLEした.
$NK\gt 3e7$ のように, 愚直が通らないぎりぎり位にちゃんと照準を合わせて無事AC.

K: Power Game

$3$ 枚くらいのカードで試すと, 初手の $x$ 以外の選択は結果に影響しないことが分かる. ( $a^{b^c}=a^{bc}$ なので)
よって, 最初の値の選択さえすれば良い.
カードの数の相乗を $S$ , 最初に選ぶカードを $x$ とすれば最終スコアは $x^{\frac{S}{x}}$ となる.
これは数学としての有名問題で $x$ が正の整数の範囲では $x=3$ で最大値をとる.
実際にスコアを求める時にも少し工夫が必要で, 繰り返し二乗法を使用するにも指数が大きくなりすぎるので, フェルマーの小定理から指数部分は $\mod{p-1}$ で求めれば十分な事を利用する.
~~このゲーム2回で飽きそう~~

J: Range Xor Query

範囲の制約が無ければ, BinaryTrie の典型利用例となる.
BinaryTrie での通常での minXOR の挙動を考えると, ある頂点から存在する子に向かうパートがある. 今回はこの時に, 単に子が存在するかではなく, 範囲内のindexを持つ子が存在するかを見るようにすればしたいことが実現できる.
indexの存在管理最初, 各頂点に直接子のindexの最大最小を持たせようとしたが, 特にlog倍を気にする必要もないので全ての頂点に set を用いれば良い.

M: Fish Tank

問題概要を整理すると多次元カタラン数の雰囲気がある.
カタラン数周りの概念で高次元に応用しやすそうな話題として鏡像法とヤング図形が思いついた.
鏡像法の方が出題されがちな気がするので先にこっちを考えたが, 上手く折り返せなかったのでヤング図形考察に移る.
最初は逆向きに考えていたため微妙に標準タブローでなかったが, 正しい方向にすると標準タブローど真ん中の形になった.
実はこの段階まで $M$ の制約を勘違いしていて実装がちょっと面倒そうと思ったが, よく見たら一個一個ヤング図形のフック長を計算できる制約だったのでありがて～になった. (後からよく考えたら $M$ が大きいと分数の分母にmodの倍数が来ちゃったりしてかなり面倒なことになる.)
フック長公式はもともと知っていたが余り日の目を見ない知識だったのでお目にかかれて嬉しみ.

H: Counting Repdigits

まず $N$ 以下のぞろ目数が昇順に ( $\mod p(=998244353)$ で) 列挙できる量なことに気が付く.
すると座圧のようなことができる. 隣合うぞろ目数の間隔を列挙しておけば, 問題の答えは, これらの間隔の積の和の形で表せ, さらに畳み込みによって高速化ができる.
持っていたNTTが遅かったり添え字があらぶったりしてしまったが, 何とか時間内に通せた.

どの問題も面白かった.
day2以降も楽しみ～～

仮のブログ

仮です