AtCoder Beginner Contest 177に参加しました。ABCDE5完3WA(71:54)で1635位でした。パフォーマンスは1285でレートは1479→1456。

感想

 いやー遂にやらかしてしまった。13回目のコンテスト参加にして初めて冷えた。直近5回のパフォーマンスが単調減少しててやばい。

A - Don't be late

 丁寧にAC。

B - Substring

 敗因。まず部分文字列を非連続でもいいと勘違いしてタイムロス。順位表見て焦りながら提出したらWA。あとまわしにしてCとDを埋めて戻ってきてからも苦戦。普通にSのindexの位置をずらしながら、Tと何文字一致するかを貪欲に見ていけばいいのに、変な解法で無理矢理通そうとしてはWAを喰らい、結局3WAもしてしまった。Bだからオーソドックスな貪欲解法で大半は解けるのにね。ちなみに3つ目のWAはminがなぜか抜けてしまっていた・・・。

C - Sum of product of pairs

 自分は累積和で通したけど、数式変形して求める人もそこそこいたらしい。そうなると逆元テクが必要になるけど。

D - Friends

 友達って単語が出てきた時点でUnionFindが脳裏に浮かび、案の定UnionFindでした。

E - Coprime

 やり方は一瞬でひらめいた。が、素因数分解ってオーソドックスなやり方だとO(√N)だけど、O(log(N))でできたっけ?自分の持ってるライブラリだと後者でいけたっけ?ってなってググったりしてた時間が非常にもったいなかった。結局、N=1000000でNに対する素因数分解をN回実行した時に一瞬だったことから、Nの素因数分解はO(log(N))と判断し、実装してAC。

追記:あとで気付きましたが、普通にNを1e+6オーダーの素数で回さないとこの判断はダメですし、実際持ってたライブラリは今見たらO(√N)でした。なぜ通った?

ちょっと実装時にムダな条件分岐させたりしちゃってたので、その辺も要改善。あとライブラリ化するならせめて計算量ぐらいはちゃんと把握しておこう・・・。

F - I hate Shortest Path Problem

 セグメント木って奴使うんかなぁ、とか思いながらも解法が思いつかず。結局セグメント木以外に順序付集合でも解けた問題らしいけど、まぁ実力不足。

反省

 最近本当にやばい。ここ2回はいずれも早解きセットで、自分が早解きが得意か苦手かはコンテスト参加回数が少ないからわからないけど、E解いた後のF崖パターンで解き終わった後の虚無な感じはつらい。とはいえF通してる人は通してるわけで、Fが崖と感じるのも実力不足故なので、低難易度帯に対する早解き力を上げつつ、高難易度帯に対するアプローチ力も上げて、Eまでの早解きに失敗した場合のFによる挽回可能性の確保も必要かなぁと感じる。あと未だにB問題で3WA出すみたいなことをしていて、考察→実装までの流れが雑なのかなぁという気もする。最近水色diffを全部埋めてしまったんだけれども、緑色diffで早解き練習をするか、青・黄diffで高難易度帯に対するアプローチ力を上げていくべきか、迷うところ。