AtCoder Beginner Contest217に参加しました。
結果
A,B,C,D問題の4問正解でパフォーマンスが786でした。 Cまでは簡単に解けたけどD,Eが難しかった。具体的には自分的にはこれ以上高速化はできないだろうコードでTLEだったので、どこを修正すればもっと早くなるのかさっぱりわからなかった。
A - Lexicographic Order
問題文の通り文字列の大小を比較して適切な文字列を出力する。
ライブラリを使って比較しても良いし、先頭から順番に比較しても良い。文字列の長さは10程度なので先頭からの比較でも十分間に合う長さ。
B - AtCoder Quiz
これも問題文の通りに解いて答えを出力する。
とりあえずマップを使ってどの文字列が何回出たかを数えて、回数が0だった文字列を出力した。
if文を使ってゴリ押しでも解けるとは思う。
C - Inverse of Permutation
ちょっとややこしいけど、順列Qは番目の値がiの順列になる。
を取得する時
として順列Qを作っていけば良い。
D - Cutting Woods
TLEがなかなか解消できなかった。原因は利用するデータ構造の選択ミスだった...
解法としては切った部分であるの一覧を持っておき、
のときはリストに
を追加して、
の時は
前後のxを求めて差分=木の長さを出力する。
最初はをvectorで管理してて
の時はソートしてから2分探索で
を含む両端を求めてた。それでTLEになってたからソートが重いのかなあと思って色々試してみたけど解決せず、二分探索に無駄があるのかなと思ってlowe_boundを使ってライブラリ任せにしてみたけどこれでも解決しなかった。
最終的にはランダムアクセスできないから2分探索やりづらいなあと思いながらSetを使って
を管理して、二分探索だったところはlower_boundを使って処理したらACできた。
今までは、Setはランダムアクセスできない(=インデックスを指定して参照ができない）からインデックスを指定して参照する可能性がある場合は最初からデータ構造の選択から除外してたけど、lower_bound・upper_boundがあるから探索のためにだけ参照したい場合ならSetも問題なく使えるのか。
E - Sorting Queries
こっちは解けそうで解けなかった。最初に書いたコードがTLEしたのが4ケースだけだったので少し工夫すれば解けるかも思ったのがそもそもの間違いだったみたい。
処理内容的にはqueueを使えば良さそうだけど、queueはソートできないから今回の問題では使えなさそう。かと言ってpriority_queueを使うと最初から勝手にソートされるから都合が悪いなあと思ってvectorを使ってみた。
コンテスト中はqueueとpriority_queueの2つを使って管理するのは考えもしなかったから、たぶん今の自分ではどうやっても解けない問題だった。解き方の引き出しか発想力・考察力が足りなかった...
