今回は珍しく競プロの話題じゃないです。ただ、自分の趣味の音ゲーに、少し面白い気がした数学的・科学的(?)構造/考察を見出したのでちょっと雑記してみます。 1. きっかけ チュウニズムの GAME IS LIFE(紫) のこの配置を初見でプレイして、ふと「この奥側の…

Discrete Centrifugal Jumps 長さ $n$ の数列 $h$ が与えられる。 $dp[1]=0\ ,\ dp[2]=dp[3]=...=dp[n]= \infty $ とする。 $i

Pairs $1$ から $N$ までの整数の番号がついた、男または女の生徒が合計 $N$ 人おり、 $N$ 人にはそれぞれ「ペアになりたい人」が $1$ 人いる。 $i$ 番目の人の 「ペアになりたい人」は、 $F_i$ 番目の人である。 但し、 $A$ さんの「ペアになりたい人」が $…

この度、数式の囲みについて、従来対応していた \( \) のほかに $ $ の導入に成功しました \(e^{i \pi}+1 = 0\) $e^{i \pi}+1 = 0$ やり方 : 設定 → デザイン → カスタマイズ(スパナのマーク) → ヘッダ → タイトル下にこれを貼る <script src="https://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-MML-AM_CHTML" async="" type="text/javascript"> </script>

Cell Shell 問題: \(10^5\) 行 \(10^5\) 列のグリッドがある。左から \(x\) マス目、下から \(y\) マス目を \((x,y)\) とする。 このうち \(N\) 個のマス \((X_i,Y_i)\) は黒く塗られている。 以下の条件を満たすマスの集合 \(S\) を、「適切」であるとする…

C - Block Game (問題概要は省略) 実装してて頭ぐちゃぐちゃになったので思考整理。 この問題において、 \(B\) がざっくり \(20\) 個強あれば必ずすぬけ君を敗北させられる。(何故なら、すぬけくんの移動可能範囲を \(1/2\) ずつ減らしていけるから) なので…

Problem - F - Codeforces \(N\) 要素からなる数列 \(A\) がある。 この要素からいくつか選んでその \(\gcd\) を \(1\) とする時、選ぶ要素数は最小でいくつになるだろうか。また、そのように選ぶことが不可能な場合 \(-1\) を出力せよ。 \( 1 \le N,A_i \le…

TopCoderで赤くなりました。 ここまで5年半、競技プログラミングを始めて2032日目の出来事でした。 正直まだ現実を飲み込めてない部分もありますが、この5年半、長かった… AOJに入り浸ったり、JOIで楽しいことたくさんしたり、AtCoderで地獄の停滞を経験した…

Mysterious Sequence \(N\) 要素からなる、数列 \(A\) があります。 あなたは、この数列に以下のクエリを尋ねることができます。 Q l1 r1 l2 r2 \( \max(A_{l1},A_{l1+1},...,A_{r1}) - \min(A_{l2},A_{l2+1},...,A_{r2})\) の値を求める。 \( A_1 , A_N \) …

突然ですが、次の問題を解きたいです。(これは Move the Coins - Creating Tests の部分問題です。全部やるとむつごいので次の問題だけ取り出します。) \(1,2,...,N\) をそれぞれ \(1\) 個ずつ含む集合があります。以下の \(Q\) 個のクエリを処理してくださ…

Chefina and Strange Tree <問題概要> \( N \)頂点からなる木と、数列 \( P_i , A_i , B_i \) が与えられる。 木の各頂点には、カウンターがひとつずつ設置されている。全てのカウンターの初期値は \( 0 \) である。 この木に対して、以下のような操作を \( …

先日、私がいわゆる公式な(Ratedな)コンテストとしては初めて、Writerを務めさせて頂いた Codeforces Round #654 (Div. 2) 、お楽しみいただけたでしょうか? 参加できなかったという方も問題に挑戦していただけると嬉しい気持ちになります。 さて、今回はコ…

D - Complexity 解説と少しだけ方針が違ったのでメモ。 ある縦の行の区間 \([i,j]\) と、左端をとる列 \(k\) を固定して、(複雑さ \(x\) を考慮するときに)とれる右端の最大値を dp[行の区間 \([i,j]\) ][左端をとる列 \(k\) ]={可能な右端の最大値(存在しな…

自分は競プロにおいて、2人ゲームの問題が非常に苦手です。Writer各位は僕を潰したければ2人ゲームを出すことを推奨します。 これを反省して、2人ゲームの必勝法の証明の流れと、3種類の「基本的な2人ゲームの勝ち方」(手順復元含め)を紹介していきます。 1.…

Blocks を解くときに使った、新規性のある話題なのでメモ。 長さ \(N\) の文字列 \(S\) があります。 「単位文字列が何度繰り返されているか」を (文字列の長さ) / (文字列の長さの約数である、文字列の周期) の 最大値で定義します。 例えば、 "hellohelloh…

これは Cow and Fields の解説で見たテクニックなのですが、他でも見たことがある気がするのでまとめておきます。 今回解きたいのは以下の問題。 長さ \(N\) の \(2\) 整数の組 \((A_i,B_i)\) があります。 このとき、相異なる \(2\) つを選んだ時の \(min(A…

この記事では、 D - Distinct Boxes の解説の内容をざっくり日本語に翻訳します。 (簡単のために空の箱を1つ作ることを認めておき、最後に解を-1するという前提で議論を行います。) この問題では、「解 \(K\) を先に仮定して、\(K\) が実現可能かどうかは二…

今回は、記事の名前の通り「完全グラフ \(K_{2N}\) を \(N-1\) 個のハミルトン閉路と \(1\) 個の完全マッチングに分解」していこうと思います。 まず、この分解の意味について。具体的には Doofish Matrix という問題を解くときにこれを調べててヒットしなく…

この記事は Dwango Programming Contest 6th でNosubをやってしまったお詫びとして書かれたものです。このコンテストのB問題もこの記事の中で解説されます。 まず、この記事で説明する「主客転倒」とは、 得点 \(A_i\) をいくつか足した和で表される総得点 \…

この記事は、 プログラマーのオススメのゲームの話をする 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 (この記事内では、点灯している点を「黒い点」、消灯している点を「白い点」と呼びます。英語の公式解説内でも同じ表現が用いられています。) まず、この操作は結局どこに何回操作をかけたか、更に言うと、そこに奇数回操作をか…