2023/1/28に開催された、ユニークビジョンプログラミングコンテスト2023 新春(AtCoder Beginner Contest 287)に参加しました。
先週はABC、ARCと立て続けに残念な結果になってしまい、レートの方は1100台を切ってしまう状態に。。
今回も負けを喰らうと、4桁レート維持も厳しくなるかというところ。ここいらで連敗を止めようという気持ちで臨む事としました。
Rated参加します。５完取って、先週の負けを取り戻せるように頑張ります✊
— devgenjin77 (@devgenjin77) 2023年1月28日
ユニークビジョンプログラミングコンテスト2023 新春 (AtCoder Beginner Contest 287) - AtCoder https://t.co/2Zq4YjAaCf
今回の結果
有言実行！今回は、なんとか５完を確保することができましたとさ。
タイムは結構早めだったので、水パフォが出てくれました。これで先週の負けを大分取り戻せました。
５完で勝ち😂😂
— devgenjin77 (@devgenjin77) 2023年1月28日
devgenjin77さんのユニークビジョンプログラミングコンテスト2023 新春 (AtCoder Beginner Contest 287)での成績：1028位
パフォーマンス：1452相当
レーティング：1097→1138 (+41) :)#AtCoder #ユニークビジョンプログラミングコンテスト2023新春(ABC287) https://t.co/0KKXJx39Um
振り返り
B問題で少しやらかしましたが、概ね早いペースで５完まで行くことができました。
A問題
Forの数を２倍した値が、より大きければ
Yes、それ以外はNoという感じで実装。
問題なく、提出一発でACが取れましたとさ。
1分35秒で1完。
提出コード
https://atcoder.jp/contests/abc287/submissions/38375909
B問題
パターンの全探索を行なっても、十分足りるような制約のため、シンプルに
endsWithメソッドがTrueになるかの全探索で実装。
ここで、変数のnとmの配置をミスってしまい、初回提出で１ペナ。そのあと修正してなんとかACが取れましたとさ。
6分20秒1ペナで2完。最近、ポカミスが増えたような気がする。反省しないとなあ。
提出コード
https://atcoder.jp/contests/abc287/submissions/38383315
C問題
最初、パスグラフというのが何のことかよくわからなかったので、とりあえずググってみる。で、ようは一本道になっているグラフのことだということで解決。
本題に戻って、パスグラフの判定方法としては、
- 次数が1の頂点が2個であること。
- 次数が2を超える点がないこと。
- 連結であること。
でいけそう。
連結かどうかは、Union-Findで行うという実装で提出。問題なくACが取れましたとさ。
13分44秒1ペナで3完。
提出コード
https://atcoder.jp/contests/abc287/submissions/38389972
D問題
制約からすると、各の値について
で判定する必要がありそうだ。
ということで、と
を前から照合した時に何文字までマッチするかと、後ろから照合した時に何文字マッチするかというのを前計算しておけば、各
について素早く結果が計算できそう。
ということで、上記の考え方で実装。本番で通るかどうか少し心配でしたが、なんとかACを取り切ることができましたとさ。
35分44秒1ペナで4完。
提出コード
https://atcoder.jp/contests/abc287/submissions/38401736
E問題
なんか難しそうな見た目をしており、以前やった文字列アルゴリズムを知らないと解けない問題かという印象。
ただ、他の文字列と、前からどのぐらい一致するかというのを全探索するのは変で、文字列をソートしてあげればだいぶ効率化できるのではないかと推察。
一応、サンプル２で検証してみると、やはり文字列でソート後、前後の文字とのを取れば答えと合ってくれるみたい。
ということで、文字列とその出現順でソートし、前後ののMaxを答えとする実装で提出。TLEだけが心配でしたが、なんとか通ってくれました。
61分39秒1ペナで5完。
提出コード
https://atcoder.jp/contests/abc287/submissions/38411214
F問題
だいぶ時間が余った状態でF問題に取り組みましたが、これはよくわからず。
見た目から推察するに、典型９０で少し触った木DPなのかというところと、計算量はなのかという印象だが、肝心の遷移をどうすればいいのかわからない。
結局、この問題の考察を進めているところで時間切れになりました。
のちほど解説を見ると、たしかに木DPだった模様だが、遷移については難しいという感じでした。後ほど復習します。
G問題
問題すら見れておりません。
Ex問題
問題すら見れておりません。
これまでの実績
先週減らしたレートを取り戻しました。ここからさらに上に行けるといいんだが。。
総括
順位表の状況を見ると、今回はE問題までの難易度が甘めだったのかというところでした。
タイムは少し良かった方でしたが、肝心の高難易度の問題を解くというところがまだできていないかと。この結果には満足せず、次に向けて今回解けなかった問題を中心に復習していこうと思います。
ということで、また次回も頑張ります。
