2020/8/29に開催されたABC177に参加しました。
前日まで開催が確定してなかったんで少し不安でしたが、なんとか開催していただけたのでよかったです。最近良い結果が出てないので、今度こそレートが上がる様にという気持ちで臨みました。
AtCoder Beginner Contest 177 - AtCoder https://t.co/mgj1bIDwmc
— devgenjin77 (@devgenjin77) 2020年8月29日
参加します。最近停滞気味なのでなんとか4完以上めざします。
今回の結果
で、今回は久々の4完達成でした！
緑パフォーマンスで久々にレーティングが上がりました！
devgenjin77さんのAtCoder Beginner Contest 177での成績：3728位
— devgenjin77 (@devgenjin77) 2020年8月29日
パフォーマンス：826相当
レーティング：540→577 (+37) :)#AtCoder #ABC177 https://t.co/1CuH9EU0Yv
久々の4完でレートも少し上昇。このパフォーマンスを維持できるよう精進します。
振り返り
あわや今回も3完どまりかというとこで、D問題に助けられました。
A問題
ならNoを出力。それ以外はYesを出力する。
問題なくAC。
B問題
問題を一目見た瞬間、難しめの問題か？と思ったが、ゴリ押しでやれば問題なかった。
先ずの先頭から
を比較して、異なる文字数をカウント。あとは
との比較開始位置を1つずつ右にずらして同じことをしていけばOK。
配列外へのアクセスがない様慎重に実装してAC。
C問題
愚直にやるとTLEになる系の問題。整理すれば簡単だった。以下考察。
と仮定した時、求めるべき答えは以下になる。
これは以下の式に変形できる。
よくみると、配列の後ろの要素の累積和とその一つ前の要素を掛けたもので構成されてることがわかる。この性質を活用すると計算量が減らせる。
あとは、modの計算に気をつけて実装してAC。
ここまで開始30分弱で3完。今度こその4完を目指してあとの問題に目を通してみた。
D問題は、Union-Findを使う系という印象。でもUnion-Findを実装したことないw
E問題は、GCDというか、素因数分解で解いてく問題かな？という印象。
F問題は、一読して何が言いたいのかがよくわからんからパス（笑）
以上から、とりあえずE問題に取り組むことにした。
E問題
で、とりあえず考察してみたものの、上手い解法が思いつかず。。
苦しまぎれに、入力の数列をソートしてから、配列の最小値以下の奇数と2で、それぞれ数列内の数字が何個割り切れるかで場合分けすればなんとかなるんじゃないかいう雑な考察で実装し、なんとかサンプルを通すコードを作成。
で、、これが実際投げてみるとTLEとWAのダブルパンチを喰らってしまったw
んで、気づけばもう1時間近くこの問題で浪費している。
ここから修正しようにも、WAはともかく、TLEの回避は無理ということで、あえなくE問題から撤退。
D問題
ダメ元でD問題に帰ってきた。
改めてこの問題を考察すると、とりあえずUnion-Find木を作って連結成分サイズの最大値を返せばいいんじゃね、ということに気づいた。
もう残り時間も少ないので、ここはUnion-Find木を使ってそうな過去問からACしてるソースを漁ってきてコピペするという戦略をとることにしたw
ちょうど当日の昼に考察していた問題がそれに該当したので、あとは使えそうなコードから不要部分の削除と出力の変更を行い、ギリギリサンプルが通ることを確認してから投げたらなんとかAC！
あーD問題先にやっとけば良かったわ（笑）
F問題
F - I hate Shortest Path Problem
コンテスト後に問題を読み返しましたが、未だに問題すら理解できてませんw
まあ、後日時間をとって取り組むことにします。
これまでの実績
総括
今回久々の4完でしたが、問題の難易度が低めだったことが幸いした結果だと思うので、まだまだ努力が必要だなーという感想です。次も頑張ります。
