うーん、書きたい内容はいっぱいあるんですけどね。 特にABCで「これは時間取れたら説明記事書きたいな～」って思ったものはいっぱいあるんですが、全然着手できてませんね。でもなんか書けるノリが生まれたんでそのノリは大事にしていこう。
この間非常に勉強になったと思った木の直径の組み合わせの問題とか
超超得意分野のボーナス問題としか思えなかった等脚台形の問題とか
VRChatの感想会での話題になって「これか！」ってなったのでその説明とか
別にする必要はないですが、一応言い訳みたいな近況報告しておくと、最近「やってみたい！」って思ったことを少しずつやってみようとしている感じです。 とはいっても元から楽しい以外の理由で自分の為に行動できる人間じゃないので、なかなか慣れないことしてます。特に活字読むの死ぬほど苦手なんで…。
とりあえずいい加減読まずに貯めてる本が増えてきたので、仕事の隙間を塗って読み進めたり。今はデザインパターン読んどります。
「ああ、知ってる知ってるわかるわかる」と思いながら、訳特有のちょっとよくわからない言い回しに翻弄されています。あめんばーさんは考えて正確に文字を読み書きするのがとても苦手です。
あといろいろあってPrewriteになっていたとある文書をちょっと真面目に書くことになりました。あめんばーさんは考えて正確に文字を読み書きするのがとても苦手で英語は冗談にならないレベルで壊滅的です。
あと直大さんがこんなこと言い出すもんだからちょっとお仕事の進む道考え直したくもなってしまっているとか。普通に超余裕で下回ってるし、前職だったら競プロは微塵も触ったことなかったけど少なくとも青レベルのアルゴリズム＋十五次曲面の微分方程式の幾何学解析でいろんな理論構築してプログラミングして品質も速度も倍以上にしててもその半分くらいだったんだよなぁ…
一週間くらいクオリティとかどうでもいいので推しをひたすら描くイラスト習慣がほしいだとか。
このブログでもAtCoderのお話だけでもなく、前にも言ったちょっと前職で考えてたアルゴリズムを言える範囲で語ったりだとか、VRの技術とかについても語ってみたいですね。twitterで性癖語ってるばっかりじゃないんです。
あと前から行ってるPythonで典型90も結局ほぼやってないし、最近精進が甘めなのでしっかりやりたいっすね。
あとメンタル安定してない（いつもの）
正直デザインパターンを最優先事項にはしてるけど、知っといて損はないと思いつつもそんなにモチベ湧いてないし、さっと流し読みして実践交えながらもう一回辞書的に読み直すのが一番よさげなパターンの内容に思えてきたので、どっかで一気に履修終わらせたいですね。
さて、身の丈の事ばっかり話すんじゃなくてちゃんと解説です。
例によって自分の理解の為の解説ですので適当です。あめんばーさんは考えて正確に文字を読み書きするのがとても苦手です。
激遅1完で激冷でした。とことん自分AGC慣れしてないのを感じました。こどふぉの低難易度問題で具体性のある実装をちょこちょこ見るので、やっぱりいっぱい問題解きたいですね。
この問題最上級にいやらしいのが6回と書いておきながら、どう来たって5回で終わる。
6回と言われた瞬間に「ABC、ACB、BAC、BCA、CAB、CBAをいい感じに全部試す感じでやるんだろうな」と思ったのが間違いなく第一の敗北原因だった。
左から取っていくと右のほうに大量に余った文字が出てしまうし、右からもまた然り。では左の文字は左から、右の文字は右から取ればバランスよさそうだが、真ん中は…？と、またダメである。
途中、「ABC、ACB、BAC、CAB、BCA、CBA」のようにA、時点でBが左に来るようなものからどんどん削っていく方法なんかも考えたんですが、これまたどんな取り方してもCが左に偏りAが右に傾くパターンでも死ぬ。
というわけで回答の通り、左N個、真ん中N個、右N個のグループから「ABC、ACB、BAC、CAB、BCA、CBA」のどれかを決めて、同じ文字は同じグループから取ることだけで考える。
ここから取れるものを取ることだけ考えていけば、常に３グループの決めてないものの個数は常に同じ。さらに決めてないABCの文字別の個数の３グループ合計も当然同じ。
これで詰むパターンがあるかと言われると、無い。
ある状況で左、真ん中、右のグループにk個ずつ残っていて、A,B,Cの総数もk個残っている状況になるとする
- AA / AA / AAのような、全てのグループから同じ文字しか取るパターンが無い状況
⇒ABCの総数が同じなはずなので、どこかのグループにBかCはあるはずである - AA / AA / BBのような、２つのグループから同じ文字を取らなければならない状況
⇒例の場合なら左と真ん中のグループにCがない状況なので、右のグループに全てのk個のCがある ⇒右のグループにBがある余地なんてあるはずないので、矛盾
というわけで、どう足掻いても何かしら取れる状況には絶対なってる。
で、なんで５回で終わるのかというと、例えば最初に取ることになったのがBCAだとしよう。
そして取れるだけ取るので、それぞれの「左のグループのBの残り個数」「真ん中のグループのC残り個数」「右のグループのA残り個数」の最小の数だけ取れることになる。
そしてそれを取った結果、今上げた3つのグループの3つの文字の残りの個数どれかが0になるわけである。
一般性はあるので、仮にAだとする。
この瞬間、BCAと同時にCBAが次から候補に挙がることはなくなる。
それ以降は、例えばその続きとしてABCを取り除くことになって真ん中のBが残り0になるとABCと同時にCBAも候補からなくなるが、それは重複しているので5回かかることは十分ある。
6回は、ありえない。
以上。
うん、前置き長すぎた。また頑張っていこう。
