atcoder.jp 各連結成分のサイズの最大値がちょうどという条件なので、最大値が以下の場合の数から最大値が以下の場合の数を引くことを考える。 を「サイズ以下の連結成分の集合で、頂点数が個、辺の数が本であるときの場合の数」とする。これに個の残りの頂…

atcoder.jp よくある典型問題。あるマス目についてカウントされる回数を数える方法を考える。すると、そのマス目から上下左右に行った所に1個でもライトがあればそのマス目がカウントされるということがわかる。素直にマスごとに上下左右の散らかってないマ…

atcoder.jp 400点にしては難しいと感じた問題だった。 まず上下左右の自由度は独立して考えられること、及び全体から重なっている場合の組み合わせを引けば良いことに気づくのが重要。X軸方向にA, Bが重なっているとき、AとBの重なる幅 について全探索するこ…

community.topcoder.com int32の範囲のが与えられる。 の商の下位3桁及び小数点以下の上位3桁を求めよ。 問題では0埋めするとかしないとか余計な考察がついてるので若干あれだが、問題の本質はこんな感じ。小数点以下の上位三桁はなるPを計算してやり、を切…

atcoder.jp 今更書くまでもない超有名問題だけどかなり手こずったのでメモ。基本的に系は和ととても相性が悪い。 問題の性質を考えると、 を満たすとき、常に であるため、 だけ考えればよい。また、足し算の有名な言い換えがあります。これはつまり、とのbi…

atcoder.jp 数列 が与えられるので、 のすべてのxorを求めよという問題。解法は愚直にやればよいので、 程度の解法を求める必要がある。 xorの値を求める問題はbitごとに独立して行うというのが鉄則。そこで下位bitから求めていこう。最下位ビットはの偶奇で…

atcoder.jp が与えられるので、 を求めるというシンプルな問題。はいずれもからを動くとしてよい。(tex: i = j]のときは簡単に計算できるので、後から引けばよい) 一般に、 という形式の値を求める場合、 が間に合わないなら、 の形にしたいなと思うのが定石…

atcoder.jp 1,2,3->0,1,2と読み替えて良い。(N>=2、かつ2段目以降は+1分が相殺されるため) こういう問題はまずは偶奇を見る。 するとパスカルの三角形的に考えて、Σ n-1Ck a[k] の偶奇であることがわかる。これが奇数なら答えは1であることが確定する。 次に…

yukicoder.me ちょっと複雑な累積和。次のような状況を想定する。 [左の荷物群の初期位置] 運びたい位置X [右の荷物の初期位置] 累積和を取ることで、「左の荷物群をその荷物群の中での右端まで異動するためのコスト」のテーブルが構成できる。 あとは「左の…

yukicoder.me ダブリングの練習。 まず「次の場所 % n」の値をダブリングテーブルを前処理しておく。 for (int i = 1; i < m; i ++) { for (int j = 0; j < n ; J++) { table[i][j] = table[i-1][table[i-1][j]] } } ダブリングテーブル自体はこんな感じで更…

atcoder.jp 二次元のある長方形領域 (r1≦y≦r2, c1≦x≦c2) の中の yCx の和を計算する問題。 とりあえず2次元の中の何かの和を考えるときは、包除原理を使うことにより 0≦y<≦r, 0≦x≦c で計算するルーチンを書いておき、あとから余計な部分を引くのが定石。 で…

atcoder.jp 桁DPの典型的な問題。非常にNの大きい問題で、N以下で条件を満たすものの数を数えよ、という場合はだいたい桁DPでやるのがよい。 DPは上位の桁(文字列でIndex 0の文字)から見て、状態として「ある桁まで見たとき、0以外の数がK個」「ある桁まで見…

atcoder.jp 構築ゲーなので「こうすればいい」ではなく発想法をメモ。 まず2でも5でも連結サイズが小さいことに着目する。HやWが大きい場合、例えば角や辺以外に2を配置するとその周囲8マスには2が1個しか置けないことから残りが5であることが確定する。する…

atcoder.jp N!の総和系なので、確率・期待値でやるべき問題。 まずは1回のコストの期待値を考える。答えはこれにN!をかけてやればよい。すると、ブロックj を取り除いたときに、ブロックiが連結である確率をP(i, j)としたとき、1回のコストの期待値はΣa[i] *…

atcoder.jp xを有理数(つまり、整数とは限らない)として、x(x+1)(x+2)...とみなすと、剰余代数系ではある整数yが存在して y(y+1)(y+2)... を計算するのとおなじになる。これが最重要。 x(x+d)(x+2d)... = d^n * y(y +1) ... (y+n-1) (ただしy=x*d^(-1) mod 1…

atcoder.jp なんとかこういう問題の本質がわかった気がする。 まず状態遷移を考えると、今までにAがi回勝って、Bがj回勝った、という状態をS(i, j) とおく。これに引き分けがk回あった、という状態を考えてしまうと引き分けは永遠に続くことがあるので、状態…

atcoder.jp トポロジカルソートして 「dp[i] = max(dp[i], dp[i + 1] + 1)」を後ろから計算する。これは何をやっているかというと、葉を0とし、各頂点から一番遠い葉までの距離が入っている。 問題文で追加されているという辺は必ず子へのショートカットとな…

atcoder.jp 日経のコンテスト出ましたがこれが通せなかったため解法をマスターしておく。この手の問題は得意だったはずなのに通せなかったのは少し反省。 「辺をいくつか除いたときの連結成分ごとのほにゃらら」は逆から考えてUnion Findで処理する。ここま…

No.777 再帰的ケーキ - yukicoder たまに目にする2次元LISなやつです。 まずシーケンスa[i]に対して、a[i_1] < a[i_2] < ... < a[i_k] となるような部分列の長さはLIS等の典型アルゴリズムで簡単に求められます。ここで、更に別のシーケンス b[i] も追加して…

Solidityとはなんぞやという話なんですが、このあたり見てもらえばわかるかなと。つまりは仮想通貨で有名なEthereum上で今の言葉で言うならDAppsを作成するための言語です。 Solidity — Solidity 0.4.24 documentation ちなみにこれ、独自言語ではあるのです…

beta.atcoder.jp あるNに対して、Nをb進数で表した時の桁の和をa[b]とおく。a[2]～a[30]までが与えられるので、Nとしてあり得る数として10^12以下のものを求める問題です。 受験数学とかでNが9の倍数かどうかの判定として各桁の和で判定できる、という知識は…

蟻本を見ているとあまり知らないアルゴリズムが結構あったりするので、ちゃんと読み返しています。というわけでスライド最小値のメモ。 長さNの数列 a[i] に対して、長さkの連続部分列 {a[i], a[i + 1],... , a[i + k - 1]} の最小値を b[i] とします。この …

円周率チャレンジ 平方根を取る or 2を足すを繰り返してπ=3.1415...に近い値を生成してくださいというゲームです。上位はスコアinfがでていますが、これはdouble型の最大値を超えてしまったためのようです。 戦略としてはTwitterでも一部言われていますが半…

最近会社のSNSに競プロ関係の記事は書いていたので更新は止まっていたのですが、こっちも再開しようかなと。というわけでいもす研の「ブロックチェーンという言葉にだまされないために」の紹介です。 https://imoz.jp/note/blockchain.html 「ブロックチェー…

code-festival-2017-qualb.contest.atcoder.jp グラフが与えられる。辺をちょうど3回通ってたどり着ける2点間に新たに辺を引く、という操作をできるだけしたい。ただし、既に辺がある場合は引くことができない。最大で何回操作ができるか？ グラフが二部グラ…

csacademy.com ツリーと色数kが与えられる。この時、あるノードに対して、そのノードから距離1のノードと、距離2のノード両方と色が異なるように頂点を彩色したい。彩色の仕方は何通りあるか。 あるノードに着目する時、距離1または距離2のノードがすべて異…

csacademy.com 整数d1, d2, d3が与えられる。2次元格子点座標の3点であって、各点のマンハッタン距離がd1, d2, d3のいずれかになるような3点を構成せよ。できない場合は-1を出力せよ。 マンハッタン距離は距離と名付けてあるだけあって、距離公理を満たす。…

csacademy.com レースを行い、1～N位までの仮順位をつけた。ただし、それぞれの順位の人はa[i]回違反をしており、ペナルティを受ける。x位の人がk回違反をした場合、x+k位になる。最終順位を求めよ。 仮順位＋ペナルティ回数でソートする。ただし、仮順位＋…

csacademy.com a[i], b[i] のN個のリストが与えられる。それぞれ、食料iに対して、a[i]個のポーションが原料として使われており、その中でb[i]個が毒ポーションであるという意味である。最も毒の割合が少ない食料を答えよ。同じ割合の食料がある場合は、一番…

code-festival-2017-quala.contest.atcoder.jp 距離dが与えられる。マンハッタン距離がdの点同士は異なる色で塗られるように格子点を塗り分けたい。塗り分けを一つ構成せよ。 マンハッタン距離を考えるときは、必ず45度回転を考える。そうすると、x軸またはy…