第二回日本最強プログラマー学生選手権参加記(~E問題)
脳みそ、うごけー!(動かない)
A - Competition
難しすぎないか…?最初に考えた方針が「両方の肉を同じだけ買ったときの金額で考える」ものだったが上手くいかず、一度B問題を解きに行って戻ってきた。スーパー高橋で売っている肉のgあたりの価格はで求められる。同様に、スーパーすぬけで売っている肉のgあたりの価格は(解であるg当たりの価格をとすると)で求められる。この二つの式の大小関係を式で表すと、
となる。さらに式変形して、
となる。この式の左辺は定数なので、は一通りに定まる。割り算の扱いに注意。計算量は、。
B - Xor of Sequences
制約より、数列に含まれる整数の範囲は以上以下である。この範囲に含まれる整数が解の条件を満たすかを全探索する。
数列に同じ整数が重複することはないという制約があるため、整数をとすると、数列に含まれるの個数がちょうど個なら条件を満たしているといえる。(ちなみにこの処理を、整数を見つけるたびに真理値型のフラグに対してtrueとのXORを取るという処理に変えると、最終的なフラグの値がそのまま解となる。)
これを回繰り返す。計算量は、。
C - Max GCD 2
ユークリッドの互除法での2数の関係から考えてみるとわかりやすい。
整数の最大公約数がであるとき、はともにの倍数である。以上以下の区間内にの倍数が個以上存在すれば、との最大公約数がとなるようなを選ぶことができる。これは、「以上の整数のうちの倍数の最小値」にを加えた値が以下かどうかを判定すればよい。
として考えられる値の最小値は、最大値はであるので、制約よりこれらの間にある整数を全探索しても間に合う。計算量は、。
D - Nowhere P
これ以降の問題は解けていない。
何か簡単な数式で解を表現できるらしいが、そこまで至らなかった。
コンテスト中の方針としては、「とても良い列」ではない列のほうをカウントして全体から引く作戦で考えていたが、数列を重複して数えてしまう沼にハマって抜け出せなかった。
E - Level K Palindrome
レベルの回文として考えられる文字列の長さの最小値を考える。最小の長さを持つレベルの回文は、レベルの回文a
を、間に何も挟まずに組み合わせていくことで作れる。この時の長さは、である。よって、高橋君が持っている文字列の長さをとすると、を満たしている必要がある。ついでにいうとが以上だと確実にimpossible
である。
さらに、レベルの回文を2つのレベルの回文に分解するとき、が偶数なら2分割、が奇数なら間に一文字挟んで2分割、となるしかないので、その文字列を構成するレベル()の回文の長さは一意に定まる。レベルの回文の長さも決まるが、このときどの文字を変えるのが最適なのかがよくわからなかった。レベルの回文は回文であってはいけないという制約が邪魔だった。
感想
レートが50下がって気分も下がったが初めてお酒を飲んで全部忘れたのでOK