312に参加をしました。結果A-Dの4完、Cで1ペナでした。これから振り返ります。2023B問題が重実装で、時間を多く使ってしまいましたが、最終的にD問題まで解けたので満足ができました。振り返っていきたいと思います。Chordhttps://atcoder.jp/contests/abc312/tasks/abc312_a文字列が与えられて、ACE、BDF、CEG、DFA、EGB、FAC、GBDのいずれかと等しい時にYesと答える問題です。意味ありげな文字に見えますが、単純に6文字を集合に入れて含まれているかで判定をしました。Codeが含まれる領域の左上のポジションを全て出力する、という問題です。Codeのチェックが少し面倒そうです。タックコードは図にすると以下のような形です。###.?????###.?????###.?????....???????????????????....?????.###?????.###?????.###コンテスト中は、以下のようなチェック関数を書きました。Trueテストコードでバグらせながらも、なんとかACができました。Codeをコピって判定に使うという方法があり、なんでコンテスト中に気づけなかったんだろう、と愕然をしました。Codeをコピってしまうと、?以外のところが一致するか判定すればよいので、かなり実装が楽になります。Handhttps://atcoder.jp/contests/abc312/tasks/abc312_cN人のりんごをある価格以上で売りたい人とM人のある価格以下で買いたい人がいます。売りたい人の数が買いたい人の数を上回るような最小の金額を求める、という問題です。ある価格が基準になっているときに、売れる人数と買える人数を計算するのは簡単です。それぞれの配列を走査して、売りたい人の数は、ある価格が売りたい金額以上なら+1。買いたい人の数はある価格が買いたい金額以下なら+1とすればいいです。価格を全探索すると、当然間に合わないです。答えで二分探索をしながら確認を行っていきます。なる空でない文字列として与えられます。(または)に置き換えて新しい文字列を作る。この中で、新しい文字列が括弧列となるような置き換え方の数を求める、という問題です。文字列の長さが3000までと比較的小さいので、凄くDPという感じがします。i番目までの文字を見ているときに、j個(が開いている通り数としました。文字が何もない、dp[0][0]は1です。そこから順番に見ていって...(だった時には一個開いている数を増やせるので、dp[i+1][j+1]+=dp[i][j])だった時には開いている数を一個減らせるので、dp[i+1][j-1]+=dp[i][j]?だったらどっちもできる、というようにします。最終的には開いている(の数はゼロでないといけないので、dp[n][0]が答えです。solve()おわりにD問題までは比較的スムーズに解くことができたのでよかったです。E,Fが何も分からず、ここからの壁が高いなーと感じています。ブレークスルーしないとスコアが頭打ちになるような感覚もあります。