CODE FESTIVAL 2017 Final 参加記録+解説もどき

本戦は行けなかったけどRatedなので参加。

AGCを2倍に拡張したみたいな感じ。

早解き3完出来たから良しとしよう。

cf17-final-open.contest.atcoder.jp

 

A問題 (300点)

KとIの間、IとHの間には文字が一切なく、Kより前、HとBの間、BとRの間、Rの後にはAが高々1個有るかどうかを判定すれば良い。

B問題 (400点)

2文字以上の回文を含むということは、次のいずれかを含むということである。

oo(ただしoはa, b, cのいずれか)

oxo(ただしoはa, b, cのいずれか、xはa, b, cのいずれか)

1文字目がaの時、2文字目にaを持ってくると「aa」という回文が含まれるのでbかcにする。ここでは、仮にbにしたとする。3文字目にaを持ってくると「aba」という回文が含まれ、bを持ってくると「bb」という回文が含まれるので、cしか持ってくることが出来ない。このまま繋げていくと、

a → ab → abc → abca → abcab → abcabc → abcabca   .....

となる。つまり、文字列Sの中に含まれるa, b, cの個数を数え、3つの文字の中ででてきた回数が最多のものと最少のものの差が1以下になれば良い。

 

C問題 (500点)

 

愚直に再帰をすると、全ての参加者の都市に対して時差が+の場合と-の場合を計算しなければならないので、最悪O(2^N)になり、N<=50なので間に合わない。

しかし、N>=24の時、高橋君の都市も含めてN+1個、つまり25個以上の都市になるが、1時間刻みの時差は高橋君の都市を基準として+0時間から+23時間までの24通りしか無いため、鳩の巣原理により時差がどうであろうと2つの都市の時刻が同じペアが最低1組は存在し、よってどのように時差が+か-かを決めてもsは0になってしまう。

つまり、N>=24の時は必ずsの最大値は0になるので、N<=23のときだけ全ての参加者の都市に対して時差が+の場合と-の場合を計算すれば良いので、最悪O(2^23 ≒ 0.08 * 10^8)で済ませることが出来る。実際は全ての場合について判定するのにO(N)だけかかるため、最悪計算量はN=23の場合のO(2^23 * 23)となる。私は1316ms(実行時間制限は2000ms)で通したが、もっと早く出来るだろう。

D問題~ (700点~)

 無理。