htkb-proconの日記

初心者がPythonで問題解いた記録

Hello 2019

ooo----- 1466 -> 1510

A. Gennady and a Card Game

AC: Submission #47904524 - Codeforces

それぞれについて1文字目と2文字目に分けて比較しましょう。

B. Petr and a Combination Lock

AC: Submission #47909911 - Codeforces

N <= 15なので215=32768の全列挙は余裕なのでビット列を利用したそれぞれについてプラスとマイナスを全通り試す全列挙をしましょう。どうやらTL情報ではmod 360を取ってない人をhackし放題の釣り堀だったらしいが…?そんなんpretest通るんかいな?

C. Yuhao and a Parenthesis

AC(3WA): Submission #47925456 - Codeforces

validかどうかわからない括弧列を2つ組み合わせてvalidな括弧列をできるだけ多く作ってねという問題。ただ左右のネストの深さだけ見ればいいんだったら簡単なんだけど、問題はどうやっても使いようのないゴミの存在。この問題は2つの文字列を組み合わせることしか許可されないので、)(のような左からも右からも閉じてもらえないとvalidにならない文字列は絶対にペアに含めないので取り除かなければならない。この条件に手間取って3WAを叩いた(むしろ中途半端に通らなくて良かったが)。

ポイントとしては、)を-1,(を+1と考えたとき、左から累積を取っていって途中で一度でも累積値がマイナスになった場合、左向きのネストを後の文字列で解消することができないため、その括弧列は必ず左から(で閉じてもらわないとvalidになり得ないということ。なので累積和を取った数列のminがマイナスになった括弧列は、必ず負(左向き)の括弧列としてしか採用できない。じゃあmin(累積値の数列) < 0 and 最終的な累積値 < 0ならばOKかというとまだ条件が足りない。)))(は累積値の最小が-3で最終的な累積値が-2だが、両向きに閉じ括弧を必要とするゴミだ。累積値のマイナスが最も大きいところからプラス側にいくらか戻して終わった場合、最小の地点から見て右向きの括弧のネストができているということなので、それを除くには負のネストが最深の状態で括弧列が終わらなければならない。

結局条件はmin(累積値の数列) == 最終的な累積値 < 0(左向きの括弧列)もしくはmin(累積値の数列) >= 0(右向きもしくは単体でvalidな括弧列)となる。あとは0は0同士、それ以外は符号を反転した数字の出現数同士を比べてペアを作る。

他の人のpythonのコードはもっと綺麗だったけどなんかもっとうまく条件付けられるのだろうか(ちゃんと読んでない)。なんか重そうな処理させそうだったので一応pypyで投げたけど、コンテスト後python3で投げ直したが余裕だった。