いろいろな記録

大学院生やってます

2020年の競プロまとめ

1年間お疲れ様でした。

今年競プロでやったことをまとめます。

数字

レート変動

996→1479 (+483, Highest : 1509)でした。

 

パフォーマンス

AtCoder Chartsさんから。平均は上がっていますがばらつきが大きい。

f:id:bustle0309:20201231223337p:plain

 

 

取り組み

記録

streakを1年間つなげました。2020年1月1日に、旅行先の上海からふと思い立ってスマホACしたのを覚えています。

水色に入る直前の4月中旬から、1日4ACをノルマとするようにしました。4ACにした理由は、ヒートマップが一番濃くなるというだけです。適当ですね。

5月末から、4問中1問はdiff1600+のものを解くようにしました。

f:id:bustle0309:20201231225032p:plain

 

f:id:bustle0309:20201231225115p:plain

 

f:id:bustle0309:20201231225341p:plain

 

f:id:bustle0309:20201231225427p:plain

f:id:bustle0309:20201231225732p:plain

 

所感

かなりキツかったです。

推移でわかる通り、途中で灰茶緑水をほとんど食い潰し、後半はdiff推定なしの問題を中心に解いていました。

高難度について。自力で通せた青diffは4割くらい、黄diffは1割くらいでした。1日1問の高難度は、移動中などを含めて30分ほど考察し、解けそうなら進める、わからないなら諦めて解説ACという形を基本に進めました。

このやり方が効果的かどうかはかなり怪しいです。解いた問題数的にはもっとレートは上がりうると思っているので、成功か失敗かはまだわからないですが、やはり倍以上は考察の時間をとったほうがレート上昇には効くと感じました。

ただ、それだと確実に実生活に支障をきたすと思ったので、挫折してやめるくらいならどんどん解説ACしてでも食らいついておいた方がいいと判断し、この方針をとりました。途中リアルが忙しすぎて、モチベがかなり落ちてコンテストに出ない時期がちょくちょくありましたが、火だけは消さないでおこうと思いstreakはつなげていました。

ただ、今年で解けそうな問題はかなり解き潰した感があるので、来年からは数を落としてじっくり解いていこうと思います。他にも、復習、解法体系化、ライブラリ整理などやります。

 

来年の目標

  • 社会人になる前に青コーダーになる
  • 4月からは自分のペースで続ける・やめない

 

 

以上です。最近低浮上ですが来年もよろしくお願いします。

2020/09/10

寝坊した…

研究

  • 作業2h

競プロ

D - Greedy customers

解説AC

無念…

実はそんなに難しくなくて、前から順にその手前の数を保持しながら、可能な限り減らすという操作を順に行っていくだけ。こういう愚直が通りそうな問題はとにかく試してみるという姿勢を忘れてきている。

英語

  • 特になし

そろそろやらないとまずい…

その他

  • 外資系金融の終わり 読了

外銀の内情を描いたベーシックな本と言えるだろうか。2012年の話なので、もうすこし現在は丸くなっていると思うが、鮮烈な外銀の話を読めて面白かった。

2020年現在、ユーロ圏も衰退し、コロナショックもGDPに少なくない影響を与えているが、長期的に世界金融市場は持ち直すのだろうか・・

2020/08/25

AtCoderのネタバレを避けるため、書く順番を最後にしてみた。

英語

  • DMM英会話

競プロ

  • AtCoder 6AC
  • ABC176バーチャル参加(1時間のみ)
D - Wizard in Maze

解説AC : 40分

地獄のようにペナを出し続けた。基本的にはBFSで問題ないが、コスト1で移動した先からコスト0の移動で追加された頂点がもう一度挿入されてしまっていて、無限ループにはまってしまっていた。

コスト0の移動をした点を先に扱う、01-BFSというアルゴリズムを学んだ。やること自体は極めてシンプルだが、優先的に0のものをdequeで処理することで最短経路が出るというのは目から鱗だった。

参考になったサイト:

01-BFSのちょっと丁寧な解説 - ARMERIA

E - Bomber

解説AC : 15分

一瞬考えて別の用事をし、そのあと解説をみてしまった。勿体無いからこういう問題の使い方はしないこと。

愚直が通らない問題は視点を変えるというのが基本。絵を描いてみると、行に乗っている点の数の最大値をC_{max}、列に乗っている点の数の最大値をR_{max}として、答えはC_{max} * R_{max}C_{max} * R_{max} - 1になることがわかる。どちらになるかは、乗っている点の数がC_{max}となる行、R_{max}となる列の全ての組み合わせにおいて、その交点がもともと爆弾が存在する地点であれば-1である、と判定できる。

 

---

ぼちぼち本読んでるから読書ログつけたい。このブログにまとめようかな。

明日ABC175のバチャをやります。

2020/08/24

競プロ

C - タコヤ木

自力AC : 20分

さらっと解けたが1WA。気をつけたい。

-1となっているたこ焼きの連続数をrとして、その前後のたこ焼きの数の差分をdとすると、単純に {}_{(d+r)} \mathrm{C} _rを掛け合わせていけば良い。が、ここでdが最大10^9ほどになりうるという問題が発生する。がしかし、dが最大でも2000ほどなので、実際にコンビネーションの式をシミュレーションすればよい。これは逆元を前計算しておけば間に合う。

 

---

研究でも時間を浪費してる感じがあってよくない。

2020/08/23

競プロ

B - Powers of two

解説AC:60分

とっかかりはつかめていたが、疲れていて粘れなかった。勿体無い。

ペアを作る問題は、最大のもの or 最小のものから貪欲に作っていくと個数を最大化できることがある、という定石を使う問題。

今回は2べきのペアを作る問題だが、手持ちのボールのうち最大のものをみると、加えて2べきになる数は一意に定まるということがわかる。setに突っ込んで、あればカウントしてペアを削除、なければ最大のものだけを削除、という操作を行っていけばよい。

 

---

遊んでた。楽しかった。

2020/08/17

競プロ

E - Tr/ee

解説AC 30分

NG条件はわかったが、木の具体的な構築方法がわからなかった。親から順番に決めていくというのは割とテンプレ行動だと思うので、記憶に焼き付けておきたい。

英語

  • DMM英会話

その他

  • 応用情報教本 1章まで

---

夏休み終わり。今日から頑張っていきます。

2020/08/16

競プロ

B - Median Pyramid Easy

自力AC 20分

実現可能なものが2\cdots N-1であるところの見切りも、構築法もすぐに思いついて実装できた。反応がいい。

青diff、こんな感じの中堅考察1つの構築問題が多い印象。

英語

  • DMM英会話

その他

  • 応用情報教本 1章途中