競プロ進捗報告(6月)

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

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


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

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


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

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


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


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

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

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

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

7月の目標

AtCoder入水!!

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

まずはICPC国内予選!

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

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

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

ARCの過去問解きを増やす

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

ABC-EFの考察をする

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

ITP2コースを埋める

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

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

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

クソなぞなぞをする

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

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

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

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

期待値問題、確率問題のDPをほんのちょっと勉強した

初めに

自分はこの記事で勉強しました(まだ読み切ってないけど、必要な分だけ)
https://compro.tsutaj.com//archive/180220_probability_dp.pdf
期待値と条件付確率 - math314のブログ

特に上のほうのリンクの「初級編」の話(以下、初級編)の話が中心です。

  • 自分が記事を読んで解釈したこと(やそこから発展した妄想)から、AtCoderの過去問を一問解説します。記事には不十分な点があると思います。ごめんなさい。
  • 間違いがあることに気づいた方は一報くださると幸いです。修正します。
  • 自分もまだまだ勉強中です。新しいノウハウを手に入れたらまた記事にしたいですね。

この記事では理論的な話や証明はほぼほぼ無しで、感覚的な話のみで構成されています。そういうのが苦手な方はブラウザバックか、別の記事で理論を補完するなどお願いします。

  • 理論的な部分は上で紹介したリンクや、「条件つき期待値」等で調べると役に立つかもしれません

今回の問題

ABC194-D Journey
atcoder.jp

ABC194バチャやりたい人とかいたら困るのでここで「続きをみる」さんに登場してもらいます。

続きを読む

【色変】個人的すきすきn問【灰・茶編】

はじめまして!!!

最近競技プログラミングをしているざわカスタネットと申します。

twitter.com


(この後すぐARCで茶色に戻るのですが・・・多分この記事が投稿されるころには緑に戻ってます・・・!)(追記 戻りました)

競技プログラミングを(本気で始めて)3ヶ月、ABC249で緑色になりました!!

(大学やTwitter等で)周囲に強い人が多く、「うえ〜〜い!!私最強〜〜〜〜〜〜!!」だなんて手放しには喜べませんが、比較的短期間(? 自分の能力値にしては早いと思う)でここまでこれたのはかなり嬉しく感じます!



今回は、AtCoderの灰・茶・緑下位レベルで個人的に好きな問題を集めました!(追記 戻緑するまでに解いた問題で好きな問題も混ぜました。後半はちょっと難易度高め?です)


(【灰・茶編】なんて書かれていますが緑編以降は多分ないです。そもそも水コーダーになれるの自分?!)



最初に自己紹介ですね・・・スペック↓↓

  • 競プロのusername
  • プログラミング歴
    • 1年(大学の講義からです。3ヶ月前から始めた競プロ以外の実用・応用は殆ど無いです)
  • どうして競プロを始めた?
  • 使用言語
    • C++ (最初期はCを使ってました)
  • 好きなこと
    • 食べて寝ること (う、虚無・・・?)
    • 最近はTwitchでストリーマーのエルデンリングの配信を見るのが好きです

一応普通の色変記事らしいQ/Aも

  • どんな精進をした?
    • AOJ_ALDS(ほぼ全部、↑の講義の課題でやらされた、Cで・・・) ITP1(ほぼ全部) APG4b(見ただけ) アルゴ式(入力、全探索、ビット演算、動的計画法) ABC過去問(灰、茶diffだけ) 典型90(☆2、☆3)、EDPC(入門編)
    • 他の人より全探索の練習を多めにしたかもしれない。ABC-Bの早解きに役立っています。
  • どれくらい過去問解いた?
    • 入茶時点で300問程度(多分)、入緑で498問です。
  • どんなことを意識していた?
    • 一問から多くの知識を得ることを意識していました。過去問の最初の200問はScrapboxに思考の流れ、解法、解説、新しく学んだテクニック等を毎回書き留めていました。(今はやってないけど)
      • 自分はこれが結構効果があったと思っていて、灰-> 茶まで一度過去問で犯した実装ミス・知識漏れを本番でしたことは多分一度もなかったと思います。
      • でも他の方(自分よりもレートが高い人)で「序盤は何も考えず数だけこなせば良い」という意見もちらほら聞きます。
  • コンテスト前のルーティンは?
    • シャワー浴びて歯を磨く

それでは早速本題に入りましょう
問題の選考基準

  • 自分が好きな問題
  • 自分にとって思い出深い問題
  • 他の人におすすめしたい問題
  • 比較的最近の問題(自分過去(ABC4問時代)の問題はほとんど解いていないので・・・)
  • 難易度はAtCoder Problemsのdifficulty基準で0~1200程度
  • 典型90、ABSは皆やっていそうなので除外


それぞれ
問題リンク (自分語り)
の様に書いています。
カテゴリ分けされていますが、その中でも(個人的な)難易度昇順になるよう努めました。



問題集 Easy (diff 0~500 競プロをやるうえでの基礎体力的なところ?)

ABC221-A Seismic magnitude scales (自分のABC初参加 & 初AC問題)
ABC183-A ReLU (機械学習系で良く耳にする単語気がする。ReLU。)
ABC235-A Rotate (本格的に競プロを取り組み始めて初のABCがABC235)
AOJ_ITP1 7_C SpreadSheet (for文と配列の練習にピッタリ!)
AOJ_ALDS 3_B Queue (PythonでQueue.queue.enqueueみたいなクソみたいなクラスとそのメソッド作った思い出)
AOJ_ITP1 10_C Standard Deviation (sum記号や小数の出力など色々ポイントがあります)
ABC227-B KEYENCE building (ぼこぼこにされた問題・・・今でも悔しかったの覚えている・・・)
ABC225-B Star or Not (割と序盤では見慣れないグラフ系の単語)
AOJ_ALDS 6_B Partition (PEに気をつけて!)
AOJ_ALDS1 1_C Prime Numbers (なんやかんやめちゃくちゃ使うイメージある)
AOJ_ALDS1 B Greatest Common Divisor (世界最古のアルゴリズムのひとつらしいです。うおおお)
Codeforces Round #784 (Div. 4) G Fall Down (実装問題!)
ARC131-B Grid Repainting 4 (な、なぜARCのB問題がこんなところに・・・)
ABC-209-C Not Equal (考察の練習!)

問題集 Difficult A (diff 200 ~ 1200 実装に重き)

ABC-232-C Graph Isomorphism (問題文だけを見ると難しそう・・・)
ABC169-B Multiplication 2 (3はちょっと有名な問題だったりしますが、2はどうでしょう)
ABC189-C Mandarin Orange (想定解びっくりした記憶がある)
ABC129-C Green Bin (変なデータ構造でゴリ押して通しちゃて笑った記憶がある問題です)
AOJ_ALDS 13_A 8 Queens Problem (実装楽しいぃぃぃ)
ABC249-D Index Trio (自分はこの問題を解けたことで入緑できました!)
Educational Codeforces Round 50 (Rated for Div. 2) B Diagonal Walking v.2 (めちゃくちゃ自分のためになったグリッド問題。)
ABC181-D Hachi (分からなくて始めてTwitterで他人に質問した問題。自分の盛大な勘違いってオチで恥ずかしかった)
ABC226-D Teleprotation (実装楽しかった上に別のABCの問題でこの問題の知識が凄い役立ったってホクホクした)
Educational Codeforces Round 126 (Rated for Div. 2) B Getting Zero (Difficult Bよりの問題だけど自分は実装でゴリ押したのでこっち)
ABC236-D Dance (自分この問題実行時間1995msでACしました・・・超ギリギリ!)
ABC239-E Subtree K-th Max (戻茶してから再緑する間にやって、楽しかったです)

問題集 Difficult B (diff 300 ~ 1200 アルゴリズムや考察テクニックに重き)

ABC182-C To 3 (じーっと睨んだり睨まなかったりするとあれが使えることに気づく)
ABC-185-C Doudecim Ferra (苦手な人はとことん苦手なす◯◯く系)
ABC194-C Squared Error (◯うが◯系連続だ〜)
ABC129-C Typical Stairs (めちゃくちゃ典型やないかい!!)
ABC131-D Megalomania (脳内でゲームミュージックが流れてしまう問題(選考理由それだけ・・・))
ABC199-C IPFL (自分この問題が解けてからクエリ問題が得意だと感じはじめている(だからなに・・・))
ABC240-D Strange Balls (最近このアルゴリズムトレンドだと思うんですよ(本当?))
ARC135-A Floor, Ceil - Decomposition (自分が結構好きな問題です!(本番で解けなかったけど!))
EDPC-E Knapsack 2 (うううううううDPだあああああ)
ABC172-C Tsundoku (最近のABC-CDにでそうな解法の問題だと思いました)
Codeforces Round #782 (Div. 2) B Bit Flipping
ABC245-D Polynomial division (またす◯が◯だ〜。そして自分が緑diffで始めてACできた問題です!)
AOJ_ALDS 4_D Allocation (ALDSコースもD問題はコンテストにでてきそうな雰囲気してますね)
AOJ_ALDS 7_D Reconstruction of a Tree (ALDS_D問題で一番好き)

雑談的な

ABCトレンド
Twitterでみんながいっていることのn番煎じですが、最近のABCはかなりパターンが決まっているようにかんじますね!

  • CはDP!Dはにぶたん!ってやつ

自分もこれには同意なんですけど、他にもABC序盤でトレンドになっている気がするものをひとつみつけたんですよ〜

  • それは・・・・・ランレングス!
    • AAAABCCCみたいな文字列をA4B1C3みたいにしようぜ的な

ランレングスする!ってよりランレングスする途中で文字列や数列に操作をしてあげるとうまくいくね〜とかACに使った実装を見返すとランレングスだった〜みたいなのがちらほら・・・

  • そんなことない?・・・それはごめん・・・・・

ARCへの苦手意識さん
ARCの成績が安定している人尊敬です!
自分は灰diffの問題でも安定して解けない状況なので・・・・・

  • 最近はコドフォなどにもでてアドホックを鍛えているのですが、自身持ってRatedにできるのはいつだろう・・・・
    • ARCの精進をしろ?・・・・ごめん

アルゴリズム・イントロダクションさん
学校のアルゴリズムの授業の指定教科書だったのですが・・・・
この教科書のおかげで成績良かったんですよ〜

色んなアルゴリズムやデータ構造がわかりやすく説明されていて、ライブラリ整備などでも役にたちそうです。
ただ自分も読めていない部分が多く、第三巻にいたっては持ってすらいないので、夏休みあたりにがーっと読み進めたいですね〜



セグメント木さん
うー知らない子です。
値の変更と区間和を得るを対数時間でできるんでしたっけ・・・?
ABC-ABCDで区間和を得たいって時に値を変化させることがほとんどないので、累積和でいいじゃんってなってしまうんですよね

っておもっていたんですけど、

最近のコンテストの説明で「セグメント木で区間xorをとる」みたいな文言がでてきて?!になった・・・・

  • これができれば解けそうな問題を一問ストックしているので、そろそろ履修かなぁ〜

学校の周りの人、競プロできすぎ問題
これ何。
しかも競プロだけじゃないんですよね。開発とかできたりする。
これ何



Twitterの人、暖色多すぎ問題
よいことだと思います。



ライブラリ整備したい
したいですが、構成に悩みます。一応リポジトリがあるのですが、カスです。色んな人のライブラリを覗きながら唸っている。
一度書いたものをただ使っていると仕様を忘れてしまうので、ドキュメントとかも一緒に作りたい
github.comが気になっている




眠い
眠い。毎日が眠い。眠くなくなるシュワシュワジュースを12本買ったけど、缶だから午前授業の日は授業前に飲みきれない懸念があって困っている。