ABC335の所感

今日はAtCoderのABCに参加しました。
ここ1年位緑色で停滞しているソフトウェアエンジニアです。

yuforest - AtCoder

各問題の所感などを書いて行きます。
自分が見たのがE問題までなのでそこまでとなります。
https://atcoder.jp/contests/abc335

A問題

最近のA問題の中ではかなり簡単だと思いました。
最後の文字を4にして出力するだけ。

B問題

制約が小さいので、3重ループの全探索で簡単に解けるとわかると思います。
150点問題はあまりみないですね。
最近の200点問題は難化傾向にあると思いました。

C問題

結構手こずりました。
C++なのでdequeを使えばすぐ、もしくはvectorでも問題なく解けると思いますが、最初の方の移動を場合分けしてしまっていたので無駄に時間がかかりました。

面白い問題だと思います。
愚直に全部の座標を管理すると計算量が間に合わないので、じゃあどうするかという考察が重要な問題だと感じました。
過去にはあまりみたことがないかも。
それもあり、答えまでの道筋が明確なD問題の方が多く解かれていたようです。

D問題

例を見ると外側から渦巻き状に数字を埋めて行って、真ん中にTを配置すれば答えになることがわかります。

この配置を出力するのには意外と手こずるかもしれません。
模範解答を見た時は鮮やかだと思いました。
今度からはこの方法でやろうと思います。

E問題

水色上位diffで結構難しい問題だったようです。
愚直にやろうとしましたが、TLEして終わりました。
解答を見るとなるほどなと思わされました。
下記の事項がポイントではないかと思います。

• 頂点に書かれた番号ごとに辺を管理する

• 頂点に書かれた数字を小さいものから大きいものになるように辺を張る

• 頂点に書かれた数字が同じ番号であれば同一視する、それをUnionFindで管理する

• DP的な感じで前の頂点までに出てきた整数の種類数+1が次の種類数となる

総合的な振り返り

2週間ぶりの競プロだったこともあり、少し腕が鈍っているかもと思いました。
C問題で時間をかけ過ぎたと思います。
E問題くらいの難易度まで解けるようになれれば、水色コーダーになれると思うのですがそれは精進しないと難しそうです。