【色変】個人的すきすき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本買ったけど、缶だから午前授業の日は授業前に飲みきれない懸念があって困っている。