半年だけ競プロやってみた!!!

コンテストの内容を含むのでネタバレ注意です。半年くらい競プロ続けたらどうなるのかワクワクしてる。

ABC219感想

ABCの3完でした。

 

初めてレートを落としてしまった。

 

先週今週と忙しくて、競プロサボっていたのが如実に現れたと思っています。

 

30分程度でCまで解き切り、残りの70分でE問題を解くことができなかったという内容でした。
3完に30分かけてしまったこと、D問題の解法が思いつかなかったこと、E問題の「村を全部含む」みたいな条件をうまく読み込めていなかったことが敗因だと思います。

 

最近のABCはABCEの完答とかABCEDの順で解くとかD問題を安定して処理できていない気がしているので、D問題を解くことができる実力を身につけるべきだと思いました。

ABC217

ABC217はABCDEの5完で1500点でした。

 

日々の精進のおかげか緑色Diffは安定して解けるようになっている気がする。

 

今週はABCの過去問をコンテスト3回分くらい解きました。

 

人生が忙しいので競プロの勉強があまりできていないが、今週と来週は水色Diffを解ききれる実力をつけるために典型90問の★5埋めをしたい。

 

 

ABC216の感想

ABCEの4問解いて1100点でした。

理想通りの動きができたのではないかと思っています。

 

私はレート620くらいの茶色corderです。

現在の目標は二つあります。

1回でも水色のパフォーマンスを出すことと緑corderになることです。

 

水色のパフォーマンスを出すために必要なことは以下の二つのどちらかを安定して行えるようになることだと思っています。

ABCDの早解き、もしくはABCEの完答です。

これらを行えれば緑corderにも届くと思っています。

 

ABC216ではABCEの完答ができたため満足しています。
しかし、パフォーマンスが1100程度だったため水色パフォには届きませんでした。


ここまでABC216上手くいったと話していましたが、反省点もあります。
A問題で2回WAを出した挙句、解法が思いつかなかったことはかなりの反省点です。
Aで2回WAを出し、A問題を諦めBCを解いたあとにAを解く動きをしました。
結果ABC3完までに30分程度かかってしまいました。
D問題の解法も思いつかずこの時はコンテストでなきゃよかったって思っていました。


これからAとDの時直しをしたいと思います!

ここまで読んでいただきありがとうございました。

 

 

 

 

ABC215の感想

ABCDの3問解いて1000点という結果でした!

D問題、これ見たことあるやつ!!!と思いウッキウキで解いたけど自分のプログラムのミスに気づけず鬱気憂きになった!!!!!!
自暴していろんなケースを入力した結果ミスに気づき解くことができた!ペナルティ含んで120分くらいかかった!!!
ギリギリ緑パフォでした。)
水色パフォを出すためにはもう一つの壁を越えないといけないと感じてます。
コーナーケースに気づけずWAを消すことが出来ないとか、発想力のもう一捻りが足りないとか、もっと早く解ければとか...

先週は「コンテストの過去問5つと典型90問を5つ解く」という目標を立てました。
実際は「コンテストの過去問3つと典型90問を4つ解く」ことに成功しました。
自分に甘い人間なので大満足しています!!!

実力を早くあげたいという焦りと目標を達成しなきゃという焦りから、すぐ答えを見てしまうようになってしまった気がするので鬱気憂きでも焦らず時間かけて問題に向き合おうと思います!

 

ARCの過去問あまり解けなかった。明日のARCには出ません‼️

ABC214の感想【入茶】

ABCの3問解いて600点という結果でした。

初めて4桁のパフォーマンスを出すことが出来ました!
ABCの3問を40分くらいで片付けられたのが勝因だと思います。
D問題はグラフのエッジの部分に注目するという方針を立てたけれど、実装方法がわからなかった。Union-Findを使いこなせるようになる必要がある。

今回7回目の参加にしてようやく茶色コーダーになることが出来ました。
(ブログ開設当時、すでに2回参加していため参加回数は全体で7回です。)

 

今まで行なったこと
AtCoder Beginners Selectionを全て解く
・競プロ典型90問★2★3を全て解く
・競プロ典型90問★4を半分くらい解く
・ABCに参加する(テスト中に自分が解けた問題の1つ上の難易度の問題の解説を聞いてACする)
・ABCの過去問を3つくらいやる

 

次の競プロまでにやること
・競プロ典型90問★4の残り5問を全て解く
・ABCの過去問を3つ、ARCの過去問を2つ解く
・次のABCと(過去問の出来が良ければ)次のARCに参加する
・立てた予定は崩壊しがち人間なので半分くらいできたら満足する。

ABC213の感想【懺悔】

ABCの3問を解いて600点という結果でした。

コンテスト開始から40分後、ABCの3問を処理した私は勝利を確信していました。
D問題は、深さ優先探索...!実装したことはないけれど理屈は知っている...なんとか実装すれば解くことができる。そう思っていました。
そして20分くらいを残して深さ優先探索を実装することができました。
しかしACすることができない...
自分のスタックを用いた深さ優先探索の手法では、探索した点をスタックから消去する手法だったために引き返すという動作に対応できなかったからです。

 

今後は実装したことないけど理屈がわかっているから解けるという思い上がりは二度としないようにします。深さ優先探索にも謝罪の気持ちしかありません。

 

典型90問の★4を半分解くこともまだできていないのでそれについても謝罪します。

 

ABC212の感想

A,B,C,Dの3問解いて1000点という結果でした。

D問題を通したとき死ぬほど脳汁でた!

ABCの傾向が変わってABCDEFGHの8問構成になってました。

新ABC問題が旧ABC問題と同じ難易度で、新D問題が旧D問題よりちょっと易しい難易度に感じました。

C、D問題が解けたのは3週間の勉強したおかげだと思ってるので満足してます。

 

 

C問題 C - Min Difference

N個の要素からなる数列AM個の要素からなる数列Bがあります。A、Bから要素を1つずつ選んだ時に、これらの差が最小になる値を求めてください。

1つずつ要素を選んで最小を求める時は、sortする!という話を聞いたことがあります。

例えば要素が(1, 10, 5, 8, 7)の数列Xを考えます。

唐突にXから2つの数字を選んで差を最小にしよう!と考えました。

頭から(1と10)(1と5)...と比べていくのは効率が悪いです。

なぜなら、10は5より大きいので(1と10)の差である9は(1と5)の差である4よりも大きくなります。1と残りの要素(10, 5, 8, 7)の差(9, 4, 7, 6)を求めて一番小さいのはなんだ...?と考えなくても、(10, 5, 8, 7)の中で5が一番小さいことを知っていれば、1と5の差を調べるだけで済みます。

また、10との差を小さくする数字を選びたい!と思った時も、10の次に大きい数字が8ということを知っていれば、10と残りの要素(1, 5, 8, 7)の差を調べる必要もなくなります。

7との差を小さくしたい!と思った時にも、小さい順で並べた時に7の隣にくる数字と比べた方が良いとわかるでしょう。

(1, 10, 5, 8, 7)を並べ替えて(1, 5, 7, 8, 10)とします。そして、1と5の差4、5と7の差2、7と8の差1...と差をそれぞれ求めて最小なものを求めてあげれば良いです。

並べ替える方法はvector sortとかで調べましょう!

 

今回は数列Xから1つずつじゃなくて数列Aと数列Bから1つずつ選ぶ問題なので、ここから一捻りする必要があります。

しかし、先程の方針は有効に思えるので数列Aと数列Bの要素を合わせて数列Cを作りましょう!

そして、数列Cの中から1つずつ選んで先程の手法で差を最小にすることを試みます。

この時にCから1つずつ選んだ数字C1とC2が、数列Aと数列Bから1つずつ選ばれている必要があります。条件を言い換えると「C1が数列Aに含まれている。なおかつC2が数列Bに含まれている。」もしくは「C1が数列Bに含まれている。なおかつC2が数列Aに含まれている。」となります。この赤色の条件を満たしている時はC1とC2の差を求めて、これを満たさない時は差を求めない(もしくは候補から除外する)ことを実装すればOKです。

 

ある数xが数列Xに含まれているかどうかを調べる方法にlower_boundがあります。

簡単にいうとlower_boundは小さい順に並べられている数列Xに対して利用します。

数列Xのx以上の要素のうち一番左の要素の位置を返します。

例えばX = (1, 2, 3, 3, 4, 5, 7)でxが3だったらXの要素の中で3以上のものは(3, 3, 4, 5, 7)となっています。この中で一番左のものは左にあるほうの3です。なのでX.begin() + 2と値を返します。この時にX[2] = 3となっているのでX[2] = xが成り立ちます。

また、X = (1, 2, 3, 3, 4, 5, 7)でxが6だったらXの要素の中で6以上のものは(7)となっています。この時はX.begin() + 6と値が返ってきます。この時はX[6] = 7となっておりX[6] = xは成り立ちません。

このようにしてlower_boundを用いてX[n] = x(nはlower_boundを使って求めた数)が成り立つかどうかで数字C1, C2が数列A,Bに含まれているか調べることができます。

 

これはlower_boundの雰囲気を伝えるための解説に過ぎないので、実際に実装する時はlower_boundとかで調べましょう!本当に雰囲気だけなのでプロの人が見たら違う解説をしてると思うかもしれません。

 

ちなみに私はこの問題のACを通すまでに50分くらいかかりました。

 

D問題 D - Querying Multiset

なんか色々操作しようぜ!って問題です。

そして色々操作した後に操作3最小値を出力しよう!という問題です。

この問題の肝は全体攻撃は記憶することだと思います。

操作2の中で全てのボールに書かれた数字aにxを足してをaからa + xに書き換えるという動作が入ります。この時に全てのボールの値をaからa + xに書き換えていたら時間が足りません。

このような全体攻撃にはボールの値を変えずにsumxといった変数を用意して対処します。操作2が行われた時にsumxにxを足していくことで記録していきます。

操作3最小値を出力することになります。操作3に対応するためにはsumxの値を考慮しながら全てのボールの値を小さい順に並べておく必要があります。

例えば100と書かれたボールを持っているとします。次に操作2によって数字を50増やすことになりました。この時、ボールの値は100のままですがsumx = 50になります。次に120と書かれたボールを獲得しました。100と120を比べると120の方が大きいですが、sumx = 50を考慮すると実際に書かれる数字は150になるはずなので100の方が大きくなります。120を獲得した際に100を150にすることも考えられますが、持っているボールの数が大きくなった時に全てのボールに50を加えてたら時間が足りなくなります。

そこで、すでに持っているボールにsumx = 50を加えるのではなく獲得したボールの値である120からsumx = 50を引いて70にすることで100との大小関係を維持することを考えます。

操作3で出力する時にはボールの最小の値にsumxを加えることで実際に書かれるはずだった値を出力することができます。

 

 

先週に引き続き真面目に解説してしまった。

いつまで解説のモチベが保たれるのだろうか。

来週までに典型90問の星3と星4の半分くらいを解き終えて今日と同じくらいのパフォーマンスを維持できるようにしたいです。

あと今日はAB問題に20分、C問題に50分、D問題に25分くらいかかってC問題が解けてなかった時間は精神が詰みかけていたのでなんとかしたい。

最近計算量を見積もれるようになった、sortはnlognであることを覚えたのは成長。