3匹の猫

みみねこの競プロ精進メモ

第二回日本最強プログラマー学生選手権参加記(~E問題)

脳みそ、うごけー!(動かない)
f:id:mmnkblog:20210417182131p:plain

A - Competition

難しすぎないか…?最初に考えた方針が「両方の肉を同じだけ買ったときの金額で考える」ものだったが上手くいかず、一度B問題を解きに行って戻ってきた。スーパー高橋で売っている肉の1gあたりの価格はY\div Xで求められる。同様に、スーパーすぬけで売っている肉の1gあたりの価格は(解であるZg当たりの価格をAとすると)A\div Zで求められる。この二つの式の大小関係を式で表すと、
\dfrac{Y}{X} \gt \dfrac{A}{Z}
となる。さらに式変形して、
\dfrac{YZ}{X} \gt A
となる。この式の左辺は定数なので、Aは一通りに定まる。割り算の扱いに注意。計算量は、O(1)

B - Xor of Sequences

制約より、数列A, Bに含まれる整数の範囲は1以上1000以下である。この範囲に含まれる整数が解の条件を満たすかを全探索する。
数列に同じ整数が重複することはないという制約があるため、整数をxとすると、数列A, Bに含まれるxの個数がちょうど1個なら条件を満たしているといえる。(ちなみにこの処理を、整数xを見つけるたびに真理値型のフラグに対してtrueとのXORを取るという処理に変えると、最終的なフラグの値がそのまま解となる。)
これを1000回繰り返す。計算量は、O(N A_{\max})

C - Max GCD 2

ユークリッドの互除法での2数の関係から考えてみるとわかりやすい。
整数x, yの最大公約数がdであるとき、x, yはともにdの倍数である。A以上B以下の区間内にdの倍数が2個以上存在すれば、xyの最大公約数がdとなるような(x, y)を選ぶことができる。これは、「A以上の整数のうちdの倍数の最小値」にdを加えた値がB以下かどうかを判定すればよい。
dとして考えられる値の最小値は1、最大値は\dfrac{B}{2}であるので、制約よりこれらの間にある整数を全探索しても間に合う。計算量は、O(B)

D - Nowhere P

これ以降の問題は解けていない。
何か簡単な数式で解を表現できるらしいが、そこまで至らなかった。
コンテスト中の方針としては、「とても良い列」ではない列のほうをカウントして全体から引く作戦で考えていたが、数列を重複して数えてしまう沼にハマって抜け出せなかった。

E - Level K Palindrome

レベルKの回文として考えられる文字列の長さの最小値を考える。最小の長さを持つレベルKの回文は、レベル1の回文aを、間に何も挟まずに組み合わせていくことで作れる。この時の長さは、2^{K-1}である。よって、高橋君が持っている文字列の長さをNとすると、N \ge 2^{K-1}を満たしている必要がある。ついでにいうとK19以上だと確実にimpossibleである。
さらに、レベルKの回文を2つのレベルK-1の回文に分解するとき、Nが偶数なら2分割、Nが奇数なら間に一文字挟んで2分割、となるしかないので、その文字列を構成するレベルk0\le k \le K)の回文の長さは一意に定まる。レベル0の回文の長さも決まるが、このときどの文字を変えるのが最適なのかがよくわからなかった。レベル0の回文は回文であってはいけないという制約が邪魔だった。

感想

レートが50下がって気分も下がったが初めてお酒を飲んで全部忘れたのでOK