コンテストページ
Keyence Programming Contest 2020 - AtCoder
解法
✔A - Painting（100 点）
長い方の辺に沿って平行に塗る以外の操作をする必要はありません。
✔B - Robot Arms（200 点）
整数の半開区間だと思っておきます。端点を全列挙して座標圧縮をして、各点について、そこより真に左側だけでいくつのロボットが存在できるのかを DP です。400 点くらいに感じたのですが、かなりたくさんの肩が通していました。もしかして私の解き方がおかしいのでしょうか。
✔C Subarray Sum（400 点）
S を K 個書いて、あとは全部 10 億で埋めるか、S が 10 億ならば 1 で埋めてしまえばよいです。意味不明すぎるのですが……
K ≦ N がなかったら難しかったです。
✔D - Swap and Flip（700 点）
隣同士しか交換できません。← 重要です（泣）
ですから、最終的な場所がわかると元いた場所との距離の偶奇から、裏返されるかどうかが決まります。どのカードを裏返すかを全探索です。これを決めると、各数字ごとに、奇数番目に行くべきものと偶数番目に行くべきものがわかるので、それを順番に当てはめていきます。数が合わないものがあった場合はアウトです。こうして最終形を作ることが出来ますから、あとは転倒数を求めれば良いです。
実行時間
上記で TLE をいただきました。実装によってオーダーは変わってくるものの、私の実装では Θ( 2N * max(N, A)) （座標圧縮をすると A は消せそうです。）になるのですが、不思議です。コピーをたくさんしているとはいえ、余裕がありそうなものなのですが、実装を誤ってしまったのでしょうか…… 結局裏返すものの枚数が偶数枚のものだけを調べることにする 2 倍改善で通りました。
余談
任意の swap が出来る場合を考えていたのですが、かなり闇を感じました。解ける方はすごいです。
感想
読めたは前半のみですが、かなり癖のあるセットでした。特に B と C です。
結果
453 位1842 青パフォです。そろそろ黄色も危うくなってきました。
D の誤読が痛かったのですが、ギリギリ間に合ったので嬉しさ半分という気持ちです。誤読に気づくまでは、こんなにみなさんの通している問題さえわからないなんてと涙を流していたものですが、不注意で良かったという気持ちです。もちろん、誤読も改善していかなければならないのですが、最近は誤読以前に普通に解けなくて振るわない回が続いていましたから、今回くらいは喜んでおくことにしたいです。
