CODE FESTIVAL 2017 qual B
作成日：2017.10.09
カテゴリー：競プロ 参戦記録
目次
コンテスト前の計画
配点が$100-200(100)-500-700-1600-1600$なので、D問題までの早解きをまずは目指す。
早解きに失敗、すなわちD問題までを40分前後で解けなかったらE,Fのいずれか簡単そうな方に時間をつぎ込む。
コンテスト中
A問題、B問題は簡単なのですぐ解けた。[A 03:13 AC][B 07:47 AC]
次にC問題を見たが、すぐに解けなかったのでD,E,Fの問題文を順に見た。
D問題がDPで解けたと思ったので提出。しかし間違っていた。[D 34:05 WA]
思考をリセットするためにC問題に戻ると、この問題の解釈を間違えていたことに気付いた。
ただ、解法はすぐ思い浮かんだので実装した。[C 46:35 AC]
そしてD問題を見ると、DPで持つべき状態を持っていなかったことに気付いた。
直して提出するも1ケースだけWAが出た。[D 64:27 WA]
F問題は頑張って貪欲っぽく構成すればできそうな気がしたが、非常に小さい制約である意味が怖かったので考察をやめた。
E問題も解けそうになかったのでD問題に戻ったが、バグが取れないまま時間切れ。
コンテスト後(結果)
3完800点の268位。パフォーマンス2058、新レート2337(-28)。
D問題のバグの原因が-INFとして何も考えずにとった$-123456$が小さすぎたことだった。
このような本質でないミスだとなかなか気づかない。
コンテスト中ではもう一度実装し直すか、その問題を捨てるかのいずれかをすべきだった。
そもそも最初のWAは考察を雑にやったためのものであるから、その点は猛省しなければならない。
各問題の(軽い)解説
- A : XXFESTIVAL
- B : Problem Set
- C : 3 Steps
- D : 101 to 010
- E : Popping Balls
- F : Largest Smallest Cyclic Shift
A : XXFESTIVAL
問題文
FESTIVALは8文字なので、入力として得た文字列の終わりの8文字を出力しなければ良い。
B : Problem Set
問題文
配列$D,T$をともにソートし、$T$の先頭の要素を選ぶ。$D$の要素を順に見ていきその時に選んでいる$T$の要素と一致したら、選ぶ$T$の要素を1つ次のものにずらす。
選ぶ$T$の要素がなくなったらYES、その前に$D$の要素を見終わったらNOである。
C : 3 Steps
問題文
頂点$u,v$間に辺を張ることで$v$からちょうど辺2本を辿っていける頂点$w$と$u$との間にも辺を張ることができるようになる。
これは$u$から$w$へは辺をちょうど5本辿ることで行けることを意味する。
同様に考えていくと、最終的に頂点$u,v$の間に辺が存在しない条件は、奇数本の辺を辿って$u$から$v$に辿り着けないことである。
そのような頂点の組が存在するのは元のグラフが2部グラフである時である。
このことを考慮して最終的に存在する辺の数を求めて、そこから初めからある辺の数を引けば答えとなる。
D : 101 to 010
問題文
$1$が$x$個並んだ後に$01$とある時、操作を$x$回行える。
また、$10$の後に$1$が$x$個並んでいる時も操作を$x$回行える。
そこで与えられた文字列の先頭と末尾に$0$を加えたものを、$0$と$0$の間にある$1$の数を先頭から列挙した数列$\{a_i\}$に変換することを考える。
この数列の要素を順に見ていき、その要素に対応する$1$を何個残すかを考えると、$0$,$1$,$a_i - 1$,$a_i$の場合を考えれば十分であることが分かる。
これは中途半端に残しても得しないからである。
これによってDPで答えが求められる。
E : Popping Balls
問題文
赤のボールを$R$、青のボールを$B$と表すとする。
まず$s,t(s > t)$を固定して考える。
操作で$R$を渡すために1番目のボールを選ぶと決めても問題ない。
よって、$s,t$番目のボールが$B$である時だけを考えれば良い。
するとRが$(s-1)$個以下かつボールが合わせて$s$個以上ある時に限り、操作で$s$番目のボールを選ぶことがあるとして良いことになる($t$についても同様)。
そこで、$s$を$B$を初めて渡した時の$R$の残りの個数、$t$をボールが$s$個以下になった後にはじめて$B$を渡したときの$R$の残りの個数にすると決める。
$s$個残った時の$R$と$B$の個数を決めると、各場合は互いに独立であり、その時の場合の数は二項係数とその累積和とさらにその累積和を用いることで$O(1)$で求められる。
F : Largest Smallest Cyclic Shift
問題文
以下はsnuke氏のコードの説明である。
はじめ$X$個の$"a"$、$Y$個の$"b"$、$Z$個の$"c"$からなる文字列の集合を用意する。
文字列の集合で辞書順最小のものは答えで先頭にあるから、考えるべきはその後ろにどのようにつなげるかである。
これは辞書順での最大を求めることから、文字列の集合で辞書順最大のものをつなげるのが良さそうである。
そこで集合内の文字列が1つになるまで、集合内から辞書順最小及び最大の文字列を取り出し、これを最小、最大の順で連結し集合に戻すことを繰り返すと解になりそうである。
＜(古い記事) CODE FESTIVAL 2017 qual A
関連
CODE FESTIVAL 2017 qual C (新しい記事)＞