AtCoder Beginner Contest 243

　ABCDGで五完でした。

コンテストへのリンク

コンテスト後のツイート

AtCoder Beginner Contest 243　ABCDGの五完
A Aとしては難し過ぎませんか？
B 2-1はsetで
C yごとに、Rの左端、Lの右端を見る
D R/LとUを相殺させる。シミュレーションしようとして2TLEしました。
G 実験すると（√xについて）https://t.co/RpyStxYvEH　が出てくるので頑張る

— titia (@titia_til) March 12, 2022

E - Edge Deletion

　解説AC。

　制約からワーシャルフロイドをすることは思いつくけど、その後が難しい。

　解説の条件で良いことを思い付くのも簡単ではないし、証明も容易ではない。

　ただ、コンテスト中全く考えなかったか？　と聞かれると、頭を掠めた気はするので、試すことはできたかもしれない。

F - Lottery

　解説ACしたが、解説を見てもしばらく分からなかった。

　N種類のどれが既に手に入ったか？　を持ってDPしたくなるが、それだと間に合わない。「くじを一回引く」ごとに更新していくようなDPではダメ。これに捉われていると解説を読んでも全く分からなくなってしまう。

　発想を転換して、K個のマスに1～Nの数字を埋める、と考える。

　「各商品について考えて、その商品は何回目のくじで当たったか？」でDPテーブルを更新していく。これだと、「残っているマスx個のうちy個にi番目の商品が当選した」のなら、(x, y)という二項係数を掛けることで更新できる。

　詰まったら発想を転換しよう、という気持ちでいれば難しくないはずなのだが。

AtCoder Regular Contest 131

　ABCEの四完でした。

コンテストへのリンク

コンテスト後のツイート

AtCoder Regular Contest 131 ABCEの四完でした。
A B*5とAをくっつけた
B 可能なら一番小さい数字を入れるだけ
C 一手目だけ調べてあとはNの偶奇（一応証明できたつもり）
E 各xからx+1～Nへは同じ色を塗るとすれば良い。
Dは三分探索しようとしたがコンテスト後にWAでした。

— titia (@titia_til) December 5, 2021

D - AtArcher

　解説放送を見てAC。

　ポイントを挙げると、

・全ての幅がDちょうどだと思って良い

・N本の中心が原点あたりに来るようにした方が良い。なので、そこから0～Dずれているものを全て調べれば良い。

・一回ごとの矢の打ち方を考えるのではなく、「0～Dずれているものたち」をまとめて考えることができる。x本目の矢が刺さる位置はDしかずれないので、累積和を使える

　という感じか。

　一点目はコンテスト中分かっていた（というか、誤読してそういう問題だと思っていた気がする）。二点目も、そんなに深く考えなかったけど当たり前。

　さらに累積和を使いそう……とは想像がついたが、その使い方が分からず解説を見た。つい、一回ごとの点数を考えたくなる（Dおきで累積和を取ろうなどと思ったが上手くいかなかった）が、まとめてやれば累積和を使えるというのが重要ですね。

　これも主客転倒系の発想の転換か。

　

Hello 2020

　今後、参加したコンテストにはできるだけメモを残しておこうと思います。（既に五日も経ってますが……）
　一応、解けた問題は解法を書きますが、厳密さは重視せず、箇条書きっぽく書きます。（解法ツイートの文字数制限ない版、という感じで）

　この回は、Dが解けず、Cまでの三完でした。

コンテストへのリンク

A. New Year and Naming

　実装問題

B. New Year and Ascent Sequence

　n個の配列から二つを選び連結したとき、$a_i<a_j (i<j)$ となる箇所が存在するものが何個あるかを全探索（$O(n^2)$）せずに求める問題。

・そもそも、一つの配列に$a_i<a_j (i<j)$ となる箇所が存在すればどれと連結しても条件を満たす

・そうでないとき、その配列は大きい順にソートされている。

ので、条件を満たすためには、$a_1>a_2>a_3>...>a_n<b_1>b_2>...b_m$のようになっていれば良い.
→あとはソートして、二分探索を使うか、尺取り法でOK。

C. New Year and Permutation

　解法として思い浮かぶのは、

・DP or 数学的にcombinationなどを使う (or OEIS)

　といったあたりか。

→今回はDPは上手くいかないので、数学的に考える
→幅を固定すれば求まる

　幅$k$の配列がhappyになるとき、

- どの数字を選ぶか
- どの位置を選ぶか
- 中身の組み合わせ
- 残りの数字の組み合わせ

　を調べればOK

D. New Year and Conference

　D, Eはアルメリアさんのブログが詳しいです。私はこれを見て通しました。

・とりあえずソート

　は、良いとして、今回は、「開始時間でソートして区間を順番に見ていく」のほかに、「開始、終了時刻をまとめてソートして時間ごとにみていく」という方法があり、後者が正解。

・区間のままみるのではなく、時間ごとにみる

　という発想の転換が重要。

（区間のままでも解く方法はあるかもしれないけど分からなかった。遅延セグ木を使ったり、リストのHashを調べたりする解法もあったけど、この発想の転換は必須？）

E. New Year and Castle Construction

　偏角でソートは思いついていたけど、その後が考察できなかった。
　解説を読んで実装してみたけど、TLEが取れず。Pythonじゃ厳しい？