ABC211 参加記

ABC211 お疲れさまでした。

思考の流れなど適当に書いていこうと思います。続くかは未定です。

A 問題

double で $A,B,C$ を受け取って計算します。

fixed と setprecision(桁数) を使って小数点の出力を行います。

収縮期血圧と拡張期血圧の最大値 $300$ は、やばいだろ… （生命の維持的に）

提出 https://atcoder.jp/contests/abc211/submissions/24478783

ここまで 0:54 

B 問題

野球のサイクルヒットのことですね。

簡単な実装は、それぞれの文字列が一度だけ現れることを確かめる、つまり、二度現れる文字列があれば "No" 、なければ "Yes" という実装ですね。

コンテスト中はその解法に気付かずダル実装をしてしまいました… (3分かけた)

提出 https://atcoder.jp/contests/abc211/submissions/24485703

ここまで 4:05

C 問題

C問題でこれが出るのか…（困惑）

典型ぽい感じがします。$dp[Sの文字数][8]$ で 、今何文字目を見ていてc,h,o,k,u,d,a,iの内何文字目まで作ったかで DP をします。（累積和を取る？感じです）

これとほぼ同じ問題が 典型90 に出ていたようですね。（私も解いていたようですが、コンテスト中に思い出すことはなかったです。）

 提出 https://atcoder.jp/contests/abc211/submissions/24490976

 ここまで 8:23 良い調子

D 問題

 グラフ問題です。

私これ知ってる！トポソして DAG(Directed Acyclic Graph) 作って累積和ぽいDPして解けるやつでしょ！と思ってやります。無向グラフですが、$1→N$ で最短距離を計算して距離の差が $1$ の頂点同士は辺で結んでアヘることができて、これは DAG になります。よって、この DAG の上でトポソしながらDPをすればよいので、$O(N+M)$ で解けました。

実装で若干ミスったりして WA を出しましたが、無事 AC。

解説を見たところ、どうやらトポソいらないようですね。（13へぇ）

提出 https://atcoder.jp/contests/abc211/submissions/24501476

 ここまで 30:18(+5min)

E 問題

 ここからが本番です。解きたい！

サンプル3を見て最大ケースの答えの数が少ないことから、答え全探索ができそうだなと思います。

ここで、順列全探索ぽいことをして、始点を全探索して $K-1$ 回の上下左右の移動を全探索しようと考え、実装します。

サンプル1が合いません。このやり方だと、十字のような塗り方ができないのです…（気づけ矢）

完全に勝った気分でいたのでちょっと焦ります。

まだ30分あります。ググります。Redelmeierのアルゴリズム というのが見つかります。調べます。再帰ぽい！

実装します。バグらせます。ああああああああああああああああああああああああああああああああああああああああああああああああああああああああ直った！！！！！！！！！！！！！！！！！！！！いやサンプル合わねえ！！！！！！！！！！！！！！！！！！！！！！ああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああせめて実行時間だけでも（サンプル3を試してみる）………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………（10秒くらい経つ）

俺の解法では、実行が、終わらねェ！！！！！！！！！！（ドドン！）

悲しいね。

最終的には 1338位で、パフォは 1329 、温まりました。嬉しいね。