結果
6ペナルティ４完。年内水色を目指しているにも関わらず茶パフォをかましてしまったと思ったら、ギリギリ緑パフォでした。ac-predictorという拡張機能の精度が分かりません。
A問題
文字列として受け取って、index0とindex2の文字をintに直して掛け算しました。
B問題
かなり時間を要しました。原因は２つ。まず、O(len(s)**2)のプログラムをO(len(s))だと見積もってしまった点。次に、chrやらordやらを考えているうちに頭がこんがらがってしまった点。計算量を見積もりながらたくさんの問題を解くことで成長していきたいです。
コンテスト後、文字列を数値に置き換えて考えたら、もっと簡単に解けたということを知りました。頭やわやわになりたいです。
C問題
n=8なので全探索できそうだと考えました。辞書を使って、青木くんのおもちゃの数字がそれぞれどの数字に対応するかを管理しました。その対応関係に基づいて、構築し直したグラフが高橋くんのグラフと同じならばYesです。
D問題
とにかく苦しみました。まず最初に、右と下だけでなく左と上にも移動できると誤読しており、昨日復習したばかりの深さ優先探索を実装してTLE。深さ優先探索の計算量が分からないので、PypyじゃなくてPythonにしたら通るのではないかと思って提出してTLE。ここで誤読に気づきました。あとはdequeを使って連結判定を行っていきました。ACを確信して書いたコードがTLEを喰らってしまい、なぜTLEなのかを突き止めるのに20分くらいかかってしまいました。原因は同じ点を何度もdequeにappendしてしまっていたことでした。解説ACばかりしているのでバグとりの実力が全くついていないようです。
深さ優先探索は基本的に、全ての頂点と辺を走査するのでO(V+E)ですが、私の実装では同じ点を何度も走査していたので当然TLEが出たようです。
E問題
残り10分。解法が思いつきませんでした。仮にDまで早解きできていても5完は無理だったように思います。
総括
今週はそこそこ精進したつもりだったのでショックでした。精進の方向性が間違っているのでしょうか。わかりません。
余談
Rated Point Sumが200000を超えたらほぼほぼ水色になれる的なことを書いている記事を見てしまい、無能と自覚していながらも深めに傷つきました。
