競プロ進捗報告（６月）

報告します。色変した時にこういうの振り返ると楽しそうだし、知識のアウトプットにもなるので・・・・（間違ったこと言ってたらごめんなさーーい）

レートの成長
AtCoder 916 -> 992
Codeforces 1160 -> 1175

うーんしょぼい！！！

まずAtCoderね。あんたね。なんで一回冷えてんねんって話やねんな（エセ関西弁）

  • 線形上昇が目標ならもっと精進がんばらんとね
  • 実装スピードが同レート帯と比べて遅いという課題が見つかった
    • テンプレートを使わなくなった弊害かもしれない。すこしずつ元のスピードに戻して行く

Codeforcesはあまり出なかった

  • 集中力が保てないのが原因
  • ICPC国内予選までは元気だったら出るスタイルで、予選終わったら毎回出席します

変化
AOJの問題を解く様になった

  • challenge問題からたまに摘むように
  • ICPCを考えるとまぁ妥当

チームバチャというものを経験した

  • 青コーダーと、中難易度問の考察が上手なチームメイトでプレーが完結しているので、自分は割と暇になってしまうことが多かった。
  • 貢献できる時とできない時の差が酷い。（JAGでは足を引っ張ってしまった）
  • 問題数こなしたり解き直しを徹底して慣れていく練習をしている・・・

水diff問に手を付け始めた

  • ついにって感じですね。
  • 1ヶ月で仕留めた問題は16問。大体毎回5分~2時間くらい考察しています。
  • 本番中にも水diffを仕留めることができたり（一回運良く青diffをしばいたり）、ABCの考察は割と好調です。

他人のコードを読み始めた

  • 実装テクニック、勉強になります・・・

ARCで1完できる回がちょくちょく

  • 直近は2完した。
  • ある程度ARCも過去問埋めたらRatedにしてみても良いと思う

艦これを始めた

  • え、競プロは
  • 小学生の時にニコニコ動画で艦これ実況動画を見たことを謎に思い出して始めた。初日に雪風引いてめちゃくちゃびびった。
  • 結局最近やってない。好きなキャラとか多いからそこそこやりたいんだけどな・・・

知識

この記事読んでくれいている人は多分ここがメインコンテンツになると思います。

Kadane's Algorithm
数列の部分連続列の総和の最大値とそのインデックスを数列の要素数に対して線形時間で求めるアルゴリズムです。
例えば4 -1 2 3 -9 2という数列だと2 3で総和が5 です。
scrapbox.io
端折って説明するといい感じにDPするとできます。

この問題の感想戦で知って勉強しました。
素朴な問題はAOJにあります。

0-1 BFS
この問題の解説で知りました。自分は知らなかったのでダイクストラでやりました。ダイクストラは遅いので、0-1 BFSができる時はそっちを使いたいです。
端折って説明すると、コストが0か1のグラフはdequeを使って、0ならpush_front、1ならbackすればpriority_queue(ダイクストラ)と同じことできるよねってことらしいです。

  • コストが0か1のグラフは早々ないね
  • 重みなしグラフの探索で、「グラフ上の探索で行う特殊行動」をコスト１にすると0-1 BFSが使えるケースが良くありそうです。


射影
この問題で初めて出会いました。知らないよという方、projectionという単語ならピンと来るのでは？
有る点から有る直線に垂線を伸ばした時にどこで交わるかをいい感じに求められます。
直行するベクトルの内積が０であることを利用すれば割と簡単に求められます。
今まで避けていた幾何問題もちょくちょくと手をだしつつある・・・・・

Min-Max法
ゲーム系の問題で、片方がスコアをmaxに、片方がminを目指す時にできるDPらしいです。
特に意識せずに書いていたものにMin-Max法という名前がついていたようです。
名前がつくとoutputがしやすくて良いですね。
この問題で名前を知りました
EDPCのとある問題でも使った覚えがあります。


四角形のテクニック
平面上に与えられたN点のうち４個選んで四角形を・・・云々という問題。
今まで茶diffのこれが解けなくて放置していたのですが、大学の講義中にふと分かってしまったのです（良いこと）
対角線の２点を全探索すればO(N^2logN)ですね！！
いつか本番でも使えそうでワクワクです。

hypot
C++の標準関数の一つで、ユークリッド距離を出せます。オーバーフローが無いのが良いね！


構文解析（簡単なのだけ）
ICPCよくでるらしいし、バチャでよく出るのでいい加減履修。
string::const_iteratorが結構便利で、数式処理以外にも使えた。
定義式を睨んでそのとおりに実装すればいいので、慣れれば難しい問題にも太刀打ちできそうです。
みさわさんの根付き木という問題のパースが楽しかったです。
自分の実装例


なもりグラフ
N 要素について、自身以外の誰かしらに対応付けるとすると、なもりグラフというものにみなすことができる。

これはつい最近のこの問題で初めて知りました。

自己ループがないN頂点N辺のグラフです。
N頂点N - 1辺のグラフが木であることを考えると、なもりグラフは必ず一つ以上のサイクルを持つことが分かりますね。

「あ、これってなもりグラフだから、グラフっぽく考えると性質見えるかも」とかあるかもですね〜〜〜

７月の目標

AtCoder入水！！

  • 200レートあげるのしんどそう。今月の倍・・・・
  • 1300 ~ 1500のパフォーマンスを連続で出すのが最低条件、厳しい・・・
  • 7月中旬で競プロ真面目に始めて半年。半年で入水するerは結構いるイメージなので自分もこれに乗りたい（結構な時間競プロに割いているつもりなので、他人より成長が遅いと凹んじゃうから・・・・）
やること

まずはICPC国内予選！

  • 上で上げた新しい知識とかもICPCバチャで得ることが多いし、なによりチームに貢献したい！

蟻本の中級編をやり切る！

  • BIT、平方分割、フロー等の名のしれたものをいい加減履修する。

ARCの過去問解きを増やす

  • そろそろRatedにしても良いような自信をつけたい

ABC-EFの考察をする

  • 本番中手がつかなかったものも、コンテスト終了後１時間は考察してみる
  • ６月中旬からやっているが、ABC256-Fがだいぶ考察進んだりしていて楽しい思いをしている
  • ABC-Eが安定したりFを仕留めれるようになってくれば、かなりQOLが高くなりそうだ

ITP2コースを埋める

  • 単純に実装テクニックを知りたい

グラフ理論の本を読み進める

  • 1冊積んでいる
  • やることに挙げたが、今月も積むことになりそうだ。

クソなぞなぞをする

  • 今月か先月自分の中でブームが来て収束してしまった。今月もブームを迎えたい。

艦これと学校の課題をする

  • したいしたい言いながらTwitter眺めるのやめたい。
  • 吹雪の改二グラを拝むのはいつになるんだろうか

www.youtube.com
「夢を満たすのに多忙なのか？目標に対して多忙なのか？この世に『多忙すぎて』とか『出来ない』ことなんて存在しねえよ」
らしいので、学校の課題とか人間関係とかに負けずにやりますぅぅぅぅぅぅぅぅぅぅぅぅぅぅ