結果
苦しみながらなんとか４完。
A問題
市松模様の配置になっている時のみ、Noを出力します。
B問題
各桁ごとに見て、和が10以上なら繰り上がりありです。
C問題
1gあたりの美味しさが高いものから順に見ていきます。これまで食べたチーズの重さを保持していって、境界となるチーズは、食べられるだけ食べます。
D問題
まず、"."がk個以下の時、全てを"X"にできます。それ以外の時は、操作はk回行うべきです。現状の左端の位置を保持しつつ、左から貪欲に見ていって、"."の出現回数がk回を超えたらans=max(ans,現在の位置-左端の位置)としていけば、O(n)で求めることができそうだという考察ができました。
ここからの実装が地獄でした。敗因は左から見ていって操作をk回行う以前と行った後を一緒のループで処理しようとしてしまい、実装が複雑になったことだと考えます。私の弱々頭はごちゃごちゃになってしまったので、2WAを経てもっと簡単に実装する手を考えました。
最初に"."の位置を全てqueueにぶちこみ、左端の情報を管理しやすくすることでなんとかACできました。自分の思考を言語化するのって本当に難しいことだなと感じます。D問題の理解度が低いため、言葉でうまく説明できないのでしょう。拙文of拙文で申し訳ございません。
E問題
n,n-1,...,,2,1の順でグラフを構築していき、Union -Findでその都度連結グラフの個数を数える道筋しか思いつかず、提出したところTLE。その後、頑張って計算量を軽くしたつもりでもTLE。pypy3をpython3に変えて祈りを捧げるもTLE。あえなくタイムアップ。今月もまた５完ならずでした。
思いついた解法と公式解説の道筋がほとんど同じでした。嬉しさ1%悔しさ99%です。頂点を追加するときに、num+=1。辺を追加するときに、それまでに連結していなかった成分同士を連結させたならnum-=1。とすることで連結成分数を容易に保持できるという考えに至れていませんでした。なるほどなるほどなるほど。
総括
11月はレートがずっと横ばいです。泣きそうです。取り組み方を見直さなければいけない気がします。
余談
今後、「くじかつ」というものに最低週１は参加していきたいと思います。
