差分: -14

3完
前回のABC参加から2週間コード全くコード書かなかった結果がこれ。
LoLが忙しすぎた・・・。
という言い訳建前はあったとしても、このレベルでレート下がるのは雑魚でしかなくてショックを隠せない。

現状でD問題まではACして、EFはまだ残っている。
一応過去コンテストはAから始めてFまで通すようにしているのだが、だんだん残っている問題が増えてきた。

A問題

かんたんじゃなかった・・・。
久しぶりの緊張のせいか問題の理解が浅すぎた。
ここで1WA。

B問題

こっちはかんたん。

C問題

復元とか言われるといかつい感じがするけど案外かんたん。
ここまで大体1問5分で17分くらい。
今回はここまで！(絶望)

D問題

解く方針は1～2分で思いついたんだ・・・。
その方針というのは、「公約数の中で素数のものを選べば良い」というもの。
実際その方針は合っているので、正しく実装できればよかったんだけど全く出来なかった。
なんでこんなに間違うんだという程合わない。
コンテストが終わって数日してからだいぶWAを重ねてACしたのだが、原因は公約数を正しく求められていないというものだった。
2週間ぶりというのがたたってか、色々細かい(致命的な)ミスはやらかしていたが、一番の原因は、平方根までループを回して順に割っていく際、最後に残った平方根以上の数も約数になる、というのを忘れていた点である。
この平方根以上の約数の問題と大量に跋扈する細かい(致命的な)ミスが織りなすバグのハーモニーが僕を苦しめた・・・。
少し考えれば、解説の「最大公約数の約数の中で素数のものを選ぶ」と同じであるというのは分かるのだが、別にそちらに変換せずとも解けるため、そのまま前者で実装を試みた。
もし最初に思いついたのが後者だったらわりとACできてたのではないかと思っている。

E問題

Dに詰まって少し見たが、さすがにDの方が簡単だろうと手をつけなかった。
後は2週間ぶりでEは無謀だろういうのもあった。
制約がかなり小さいのでbitDPとか部分的に全探索したりするのかなとか考えた。

F問題

誘導部分グラフってなんやねん。
調べて理解したが、この問題を考えるべきではないと直感が告げた。


2週間ぶりでもDは間違いなく解けた問題だ。
反省しかない。
もうちょっと落ち着いてコードとやりたいことを広く見られるようになりたい。

ABC142からまた1週間空いて、今週はあるのかどうかまだ分からないが、あればなんとか頑張って参加したい。
というのも今週土曜日はWCSグループステージ開幕！
観戦しながらとか舐めたことしてまた3完にならないように気をつけたいが、見たいものは見たい。

順位: 1394
パフォーマンス: 1152
新レーティング: 281
差分: +225


まだ灰色。
次あたり茶色になれそう。

前回に続いて4完。
EをやめてFから解いてたら解けてそうかもしれない。
前回もそんなこと言って実際解いてみたら時間内は無理そうだったので今回もそれかもしれない。
別の問題でRMQの実装に戸惑ってEもFもまだ解いていない。

A問題

かんたん。

B問題

問題文がややこしい・・・。
理解と実装のスピードを高めないといけない。

C問題

書いたら添字も関係性がすぐ分かるやつ。

D問題

問題文読み間違えた！
やってしまった！
その結果飛ばしてE問題を考えて時間を浪費した。
RR,LLが幸福じゃなくて、RLみたいに向き合ってるのが幸福かと思ってしまった。
普通の人は前の人が同じ向き向いていても幸福だと思わない・・・。
E問題から帰ってきてもう1回考え直したら条件違うじゃん！ってなって5分か10分くらいで解けた気がする。
最後の処理ちょっとミスって1WA。
この間違った条件でも似たような感じで解けそうではある。

E問題

結構考えたけど解ける気がしなかった。
ABC128 E Roadworkを思い出してO(NQ)のどちらかを二部探索でlogにできるのではと考えたのだが、どっちもnじゃあどうしようも・・・という感じ。
何を考えればO(n^2)から片方のnを二部探索に持っていけるのか全く分からなかった。

解説を見るとシグマを外してある数との掛け算の形に直していて驚くしかない。
新しいパターン。
こういう考え方もあるのか。

F問題二部平衡木では？となぜか直感。
二部平衡木がどんなものかあまり詳しく知らないし、関連アルゴリズムも全く知らない。
セグメントツリーくらいか。
ということで深く考えるのをやめてEを解くことにしてFはあまり考えていない。

コンテストが終わってから軽く考えたら普通に解けそうだなぁと思ってきた。
コンテスト中は焦っているのでかなり時間を費やしたEを解こうと頑張っていたが、Eに時間を費やし始める前にFに取り組めば良かったかもしれない。
前回もしかり、EFは難易度が逆転することも結構ありそう？

初めてコンテストに参加したぞ！

順位: 2665
パフォーマンス: 813
新レーティング: 56
差分: -


結果はABCDの4完。
最初だしレート変動もほとんどないから良かったものの、Cで2WA、Dで2WAしてしまった。
どちらも考え方も実装もほぼ問題なかったのに小さなミスが原因だ。
しかもそれになかなか気づけずに合わせて15分程浪費してしまった。
ミスのペナルティはもちろん、15分あればE問題をACにできた可能性が無くもないので細かいミスには気をつけていきたいところ。

A問題

簡単

B問題

普段のB問題と比べて難しくない・・・？
最初単純に3^nかと思って解いたら全然違う答えが出て、問題文しっかり読んでないじゃん！とちょっとパニックになって紙に書き起こした。
合計5分以上かかった。

C問題

B問題より簡単。
初回提出もB問題より早かったのだが、ミス潰せなくて20分近く使って合計25分くらい。
特に2番目のミスはなかなか気づけなかった。

C問題のミス

1. ループ内で計算した一時変数を全体の最大値と比較代入する処理を繰り返した後、最後の出力の部分でカウント用の一時変数を出力してしまった。
2. if文で一時変数の増加、else文で一時変数と最大値との比較、一時変数の初期化を行っていたが、ループの最後にelse文が実行されない条件式になっていたため、最後の一時変数が最大値に代入されることがなかった。

D問題

これもかなり簡単だった。
今の所B問題が突出して難しくて、CDはそれより早く正しい実装に取りかかれた印象。
簡単な問題にはミスがつきもの。
C問題より遥かにひどい・・・。
ちょっと前にこれ最近だけで3回くらいやったから気をつけようって言ったところのやつ。
初コンテストの同じ問題で2回やるかね。
なんならこれから全部long long型でやっても良いまである。

D問題のミス

1. 答えのint型がオーバーフローしていた。
2. 答えをlong long型にするも、そもそもint型同士の計算途中でオーバーフローしていた。

E問題

テストケースが1つだけTLEで他はACという状態だった。
曰く最悪計算量がO(n^3)になっているらしい。
自分の中では、ループ文の最初でcontinuteしたらそれはオーダーに入れなくて良いからO(n^2)という計算で、なぜTLEするのかまるで分からなかったのだが、そういうことではないらしい。
どこかのなにかの解説で、ループの最初でcontinuteするからオーダーは～みたいなことを書いていた記憶があったのだが・・・。
もっと重い処理を書いていて、continuteの部分はO(10^8)に届かない範囲で気にしなくても良いねっていうことだったのかもしれない。

F問題

D問題が終わった段階でE問題とどっちから解くか比べて、どっちもそこそこ解けそうだけどF問題はハマったらヤバそう、という考察でE問題を解きにいった。
結局解く時間はなかった。
書いてたら方針思いつくかと一応入力部分だけ書いたのだが、先に解くかどうか決めてから取り掛かった方が良いのかな。

コンテストが終わってからも考えてみたものの全然分からなかった。
象限ごとに分けて考えたいなぁと思ったまでは良いものの、その先に進めなかった。
解説動画を見てなんとか納得。
偏角ソートは幾何の問題ではそこそこ出てくるみたいなので覚えていこう。
どうやって実装しようか悩んだ結果結局実装しなかったのだが、ベクトルAとベクトルBが反時計回りに180度以内ってどう判定しようか。
ベクトル周辺の知識あんまり覚えていない。


案外ABCDは早く解けてまた成長感じた。
Eも本当にあと一歩だったので全完もそんなに遠くはないのかなという気がする。
目標の黄色に年内に届くかどうかは全く分からない。
競技プログラミング始めて休止して始めて休止して、なんだかんだでのべ3ヶ月くらいなのでまだまだ伸びしろはあると信じたい。
今週も参加したいね。