Codeforces Round #517 (Div. 1 + 2, based on Technocup 2019 Elimination Round 2)

@tempura_pp わーい（これちゃんと証明できてれば天才なんですけどね）

2018-10-21 23:19:46

「この貪欲，ほんとかなぁ～？(ゴロリ)」となって思考パートに入ってる間に先に意識が終了して夢の中に行ってしまうの，身体の圧倒的欠陥を感じる

2018-10-21 23:24:00

@CuriousFairy315 あ、一定保持してみたいな感じか累積和でどこまで遡るかを持てば各文字O(1)だなって思ってた

2018-10-21 23:25:22

さっきの解法でYESが出るケースは良くて、操作回数が足りることもちゃんと評価すれば証明できると思うけど、あれでNOが出た時に本当にどうやっても不可能なのかの証明が思いつかない

2018-10-21 23:26:47

iwashi31 @iwashi31

なんか期待通り入力受け取れないな～と思ってたら cin 書き忘れてひたすら右シフトするだけを書いていて笑った

2018-10-21 23:34:20

@armeria_betrue これ， 1 1 0 1 0 1 0 1 ... となるケースだとn/2+α回くらい操作必要になりませんか？

2018-10-21 23:35:52

@satanic0258 なりました（）これダメなやつですね… pic.twitter.com/EU2AWzeRa0

2018-10-21 23:40:06

拡大

@armeria_betrue 135が123と234と345でつくれることからn<=6だと実質3連続の操作だけ考えればよくてまぁそれなら無理だなって感じがします

2018-10-21 23:43:56

@armeria_betrue ケース弱かったんですね(にゃーん) コメント見たら同じこと言ってる人も居ましたね… codeforces.com/blog/entry/625…

2018-10-21 23:46:35

7 1 0 0 0 0 0 0 でNOといってしまうものも通ってるとかなんとか codeforces.com/blog/entry/625…

2018-10-21 23:48:11

@satanic0258 ですねー… Hackありがとうございます

2018-10-21 23:48:54

色んな人がweak weak言っている

2018-10-21 23:50:06

・端2つに寄せること自体は正しそう・操作回数削減はもっと賢くやる必要がある

2018-10-21 23:51:54

@armeria_betrue ちゃんと証明します。マスを赤白青の順にぬります。3連続の操作しか許されない場合｢赤マスの1と白マスの1の個数の差の偶奇｣など3通りはすべて変化しません。ということでn<=6ではどれかの偶奇が壊れてるもの、n=7では白と青の偶奇が壊れてるものはNOです(n=7のとき赤は147で補正できる)

2018-10-21 23:53:09

@tempura_pp おおお、ありがとうございます！ YES/NO判定はこれで正しそうですね

2018-10-21 23:59:21

@armeria_betrue 逆にn>=8のときはアルメリアさんの方法で(最小回数を無視すれば)構築は可能です。 [n/3]+12の達成については1回で3マス進めることを言えばよいです。前3つが110のとき以外は自明。 110111→159,246 1101else→147 適当 1100**→159 適当で十分大きいなら2回で6マス進めるのでOK

2018-10-22 00:07:39

@armeria_betrue あ、ちょっと嘘で1100**はもうちょっと場合分けいりますね。とにかくこれでn<=12までは削れて、ここからはアルメリアさんの解で最低2マスずつ縮める(最大6回)、端2マスの調整(最大4回)なので足りそうです

2018-10-22 00:10:25

@tempura_pp 解説が6個単位だったので私もそこを考えてました。場合分けがつらそうだなーと思ってましたが、良い感じにまとめればちょっとマシになりそうですね…

2018-10-22 00:13:18

@armeria_betrue 場合分けが虚無なのはそうなんで素がまぁこどふぉなので

2018-10-22 00:25:26