いつも頭に問題を

競技プログラミング中心で思ったことを書いてく

AtCoder Regular Contest 077(ARC077)

AtCoder Regular Contest 077 - AtCoder Regular Contest 077 | AtCoder
出ました、出ました
自宅で4人でオンサイトごっこしながら出ました
結果は1完の終了後にDも通しました

C.pushpush
数字がn個与えられる、これを

1,数字を後ろにくっつける
2,逆向きに並び替える

という操作を繰り返していく
最初は文字列にして処理してやろうかと思ったけど、よく考えたら
1,2,3,4,5,6と与えられた場合
6,4,2,1,3,5
という風になる
出力順を見れば後ろから1個飛ばしで出力したのち前から1個飛ばしで出力している
これをループさせてAC
終わった後で友達がTLEを吐いていたので聞いてみると先頭に追加していたが、その部分ですべての要素を1ずつずらす処理が入るためだった
dequeueを思い出したので勧めたらACしていたのでよかった
思考放棄かとも思うが速いので

D.11
n+1の数列が与えられる、その要素はn以下の数をすべて使っているので1つだけ2回登場する数がある
これらの部分列の個数を1~n+1までそれぞれ求めて出力
しばらく考察をした
同じ数を見つけてそれの左にある数字の個数と右にある数字の個数をそれぞれ数えて組み合わせを全体から引けばいいと思った
組み合わせだと思ったのでとりあえずABCの問題を探した
C: 経路 - AtCoder Beginner Contest 034 | AtCoder
フェルマーの小定理を使わないと1e9+7で割ったあまりをうまく求められないことを覚えていたので(今後当たり前になるらしいのでテンプレ化予定で)
なんとなく理解しそれとなく実装しておいた

で、実装するとかなり惜しい答えが出たが合わない
あちこち見直し頭を抱えてたらタイムアップ
終わったらY氏が華麗に解説してくれた

例えば
1234567489を考える
4が同じ数なので左の4の左に数字が3つ、間が開いて右の4の右に数字が2つ
2数からなる部分列でダブるのは14,24,34,48,49となる
この場合は私の実装でもうまくいく
しかし3数以上を考えるときダブるのは124,134,234,489まではいいが、4の外を両方使ったを使った148,149,248,249,348,349が数えられてない
なので正しくは左から選ぶ通り、右から選ぶ通りではなく、左右の合計から選ぶ通りを引けばよかった

実装したら通らなかったのでTwitterに投げたら、c++では負の値の余りを計算すると正にはならないらしく、負のまま出力されていたらしい
1e9+7を足したうえで余りをとるように変更したらAC
ありがとうございました

学ぶことが多くていい回だったなぁと思いました