この記事は、 プログラマーのオススメのゲームの話をする Advent Calendar 2019 - Adventar の24日目の記事として執筆されました。 競プロerの物理好きと言えば音ゲーですよね、ということで音ゲーの話をします。 といっても、特定機種の布教…というよりは「…

この記事は、 Competitive Programming (1) Advent Calendar 2019 16日目の記事として執筆されました。 今回は、 線形時間、すなわち \(O(N)\) でできる予計算的な処理をいろいろとまとめてみようと思います。思いつくがままに並べているだけなので、ヌケモ…

Problem - C - Codeforces 座標平面上のある凸多角形を構成する\(N\)点の点集合 \(A_1,A_2,...,A_N\)がある。あなたはこの点集合に対して以下の\(2\)種類のクエリを合計で高々\(3N\)回問い合わせることができる。 クエリ\(1\) : 三角形\(A_iA_jA_k\)の面積の…

D - Water Bottle ABC144-Dのおきもちをざっくり1枚にまとめました#AtCoder pic.twitter.com/MFZcLIupaf — 物理好き@新感覚競プロ魔法少女物語「魔法少女ぶつりょな∇」11月9日放送開始! (@butsurizuki) October 27, 2019 https://atcoder.jp/contests/abc144…

F - Fork in the Road 想定解より良いオーダーだったので書きます まず、元のグラフについて、そのノードを通る確率を前から計算していきます。 ノード番号の若いほうから以下の図のような遷移をすると可能です。 今度は、「そのノードからあと何ノードたど…

最近ブログをほとんど更新できていないので、折角なので僕が作問するときに意識していることを書いてみます。 実は、僕はABCに近い難易度と体裁のセットを、1人で(基本的に)1日で作り上げてそれをHackerRankのコンテスト開催機能を活用して有志コンとして実…

まず、合格基準を3/4に定めた理由としては、問題の当たり外れを緩和するためです。中伝、皆伝を除くどの段位でも3問目と4問目の間の難易度の差は極力抑えており、3問目か4問目のどちらかが解ければ「その難易度層は一定の確率で解ける」と認定できるような選…

AtCoder Beginner Contest (001～132) の過去問を利用した段位認定コースです。 僕のABC完全全完記念に作ってみました。 2時間で4問を解いてください。その結果により、実力を判定します。 判定基準 正解問題数 判定結果 0,1問正解 合格にはまだまだ精進が必…

D - 歩くサンタクロース (Walking Santa) まず、状況を整理すると、ある点Pを1点定めて、そこから「指定されたN点のマンハッタン距離の2倍からPから最遠の点までのマンハッタン距離を引いたもの」を最小化する問題です。(点Pは明らかに点が存在する長方領域…

C - Differ by 1 Bit まず、答えが絶対にNOとなる場合を導きます。 操作回数の総合計は回で、これは奇数です。とすると、Aから奇数回操作をかけると立っているbitの本数の偶奇が逆転することがわかります。結局、AとBで立っているbitの数の偶奇が一致してい…

C1 - Triangular Lamps Easy (この記事内では、点灯している点を「黒い点」、消灯している点を「白い点」と呼びます。英語の公式解説内でも同じ表現が用いられています。) まず、この操作は結局どこに何回操作をかけたか、更に言うと、そこに奇数回操作をか…

C - 最小カットと最大カット この問題は、 「N頂点N辺の連結なグラフが与えられるので、頂点を2色に塗分けて、両端の頂点の色が異なるような辺の数を(最小/最大)化せよ(但し、色は2色とも1度は使用しなければならない)」 という問題です。 まず、最小は簡単…

Tasks - 全国統一プログラミング王決定戦 エキシビジョン A:接頭辞たちは、文字列の先頭から何文字か切り出したものなので、辞書順ソートすると接頭辞の長さ順になります。よって、接頭辞配列は{先頭から1文字目まで,先頭から2文字目まで,...,先頭からN文字…

AtCoder Beginner Contest 117 - AtCoder A: Entrance Examination 飛んだ先の世界で時間が時間過ぎると、元の世界では時間は時間過ぎます。 https://atcoder.jp/contests/abc117/submissions/4157588 B: Polygon 多角形の成立条件に関する問題。問題文を読…

H - 包囲 この問題は、いくつか格子点が与えられるので、その格子点の中からいくつか選んで単純多角形を作り、その内部(線上はナシ)に原点を取り囲め、というものです。 まず、少し頭を使って考えると、下図のように、ある3点を結ぶ三角形の内部に原点が来る…

3:59 E<体感400>dp[価値]=その価値を達成する最小コスト。https://atcoder.jp/contests/dp/submissions/3936145 9:44 H<体感400>所謂11解法。dp[a][b]=(上+左)。https://atcoder.jp/contests/dp/submissions/3936760 20:03 C<体感300>dp[日付け][直近の操作A…

F - Lotus Leaves この問題は、カエルが移動する方法をなくす、という時点で最小カット問題を連想すると思います。 次に考えるのは、葉をグラフの頂点とみなして最小カットに似たことをする、という方針ですが、これをすると辺の張り方がわからなくなる上、…

B - Tree Burning この問題の解説の証明部分がよくわからなかったので、自分で証明を考えました。 まず、座標正の向きに移動する行為をFと、負の向きに移動する行為をBと定義します。 そして、操作の列をFFBFBF...のように表記することにします。 ここで、高…

D - No Need この問題は、まずサンプルケース、特にSample 3の 6 2010 4 3 10 25 2 を見て実験すると、どうやら要らなくなるのは2,3,4の3つだということがわかります。 ここで、直観的に「不要な数がk個存在するなら、それは小さい順からk個である」という仮…

はてブロを始めました。 主に競プロの面白いと思った問題をまとめる、みたいなことをすると思います。 宜しくお願いします。