テルの競プロメモ

競プロに関するメモ

簡単&便利! C# × .NET Blazor で AHC ビジュアライザ作り

この記事は、競技プログラミングのヒューリスティックコンテスト*1で用いられるビジュアライザを C# と ASP.NET Core Blazor*2 で自作しよう! というものです。C# が分からない方でもできるよう、全手順を解説しています。また Visual Studio というエディ…

ありがとう、競プロはタイピングの役に立つ ~「プログラミングの目的化」のおかげで人生がより楽しくなった話~

まえがき 最初に謝っておきます。 この記事、目的はほぼ自作ゲームの宣伝です…… ただ競プロに感謝してることも事実。 ちょくだいさんがよく言及している「プログラミングの目的化」が良い意味で刺さって、人生がより楽しくなっている話をさせてもらおうと思…

競技プログラミングに関係する数学の整理 ~文系出身や数学苦手erが、もっと競プロを楽しむために~

まえがき この記事の目的 意図する対象読者 今回の整理の仕方(記事の見方) 注意 競プロに関係する数学(本題) 言葉(文系でも多分聞いたことはある)編 言葉(文系だと聞いたことないかも)編 言葉(離散数学)編 「式変形」編 「図形っぽいやつ」編 筆者…

「初中級者が解くべき過去問精選100問」「上級者が解くべき過去問精選100+50問」チャレンジシート

@e869120 さんが公開されている、上を目指す競プロerが解くべき過去問精選100問(100+50問)。 水~黄コーダーを目指すAtCoderユーザーが解くべき問題セットとして、多くの人に使われています。 元記事へのリンク ・初中級者が解くべき過去問精選 100 問 100…

東京海上日動プロコン2020 E問題 - "O(rand)" 解説

ARC級のE問題、本番中のACは 88人 / 223人提出 で、Diff 2726 と、かなり難しい判定の出ている問題です。 実際、考察や実装自体は難しかったですが、要求される知識自体は「包除原理」以外には高度なものは無く、緑コーダーの知識でも十分解けるものでした。…

ABC169-F "Knapsack for All Subsets" DPの遷移式について

本番中は解けなかったのですが、苦手なDPに少しずつ慣れてきたこともあり、O(N^2 * S) のTLE解までは書くことができました(それでも十分嬉しい)。解説を読み、O(N*S) の解法が理解できて解説ACできたので、自分の場合のDPの発想手順と、想定解のDP遷移式を…

AtCoder 茶~緑はバケツ(バケット)道を極めるべき!

まえがき 問題の例 バケツって何? 基本のバケツ バケツの有用性 バケツの注意点 ここからが本番! バケツの賢い使い方 連想配列(map)でバケツを作る バケツに bool を入れる バケツにタプルを入れる バケツで「組み合わせ」を見つける バケツに移動先を入…

数弱による ABC168-E "・(Bullet)" 解説

かなり詳しい解説記事は既にあったのですが、 自分は数弱で、ちょっと難しいと思った部分もあったので、詰まった箇所を補足します。余りの計算や連想配列(map)に pair を入れるやり方に慣れておらず苦しみましたが、楽しんで解けました。 この map の使い…

AGC036-B "Do Not Duplicate" の周期性について

問題 B - Do Not Duplicateこの問題は、周期性をO(N)で求めることができて、それを使って解けるらしいが、以前はそれが理解できなかった。 結局、その時はダブリングを使って解いた。悔しかったので改めて考え直し、なんとか証明を理解できた(と思う)。 ネ…

競技プログラミングで使われる英語の定義

競技プログラミング(というか Codeforces)で使われる英語の意味や定義をまとめていきます。 subarray, subsequence, subset, substring 及び contiguous prefix sum subarray, subsequence, subset, substring 及び contiguous なんとなく「部分列」系の用…

ダブリング ~AGC036-B "Do Not Duplicate"~

問題 AGC036-B "Do Not Duplicate" 700点問題 AtCoder ProblemsにおけるDifficulty(コンテスト中にACした場合の最低レート) : 1707 自分のACコード 方針 ダブリングを使う。(ということでダブリングについて書く。とはいえ、あとで「つまずきポイント」に…

このブログについて

方針 解説というよりは、自分用のメモとして作成していきます。 ただ、自分が文系かつ非エンジニアのため、数学的な解説が理解できないことが多いので、同じ数弱の同士の役に立てば嬉しいとも思っています。 作者 名前:テル 競プロを始めたタイパー Twitter…