解説と全然違うことをして通したので書く。各ステップは難しくないが相当の考察腕力を必要とする。実装はほぼ無。 問題概要 最初 にいて、 上の確率変数 を xor していくランダムウォークを考える。各状態について、はじめてその状態に至るまでの遷移回数の…

今年のはじめ頃に AtCoder 埋めをしたので、感想を書き連ねます。問題を選ぶ基準は、すでに埋めた全員 rated のコンテストの 1300 以上とあと若干の気になったものたちです。(ネタばれ防止用空白) (空白ここまで)AGC 001 E: 当時は非典型だったけど一回出ち…

この記事は何か 2015 年から 2018 年にかけて活動した、チーム Cxiv-Dxiv(Hujiwara, hogloid, DEGwer) のコンテスト中の立ちふるまいについてです。 メンバー紹介 Hujiwara: 幾何とか非典型実装をやる hogloid: データ構造とか文字列とかをやる DEGwer: 数え…

この記事は、「『競プロ!!』 競技プログラミング Advent Calendar 2017」の 20 日目の記事として書かれました。「数え上げテクニック集」を pdf として公開しました。最近の数え上げの問題を解くテクニックを体系的にまとめた資料です。想定している対象読者…

解説に少し頼りました。 問題概要 http://agc012.contest.atcoder.jp/tasks/agc012_f 思考の道筋 ある操作で作りうる列を数えるときは、同じ列ができる操作列の同値類から代表元を一個取ってきてそれを数える(できた列に対して、何らかのgreedyで操作列を一…

twitterで「たとえ頭が良くても、相手の気持ちを汲み取らず、正論を振りかざして相手を傷つけるのは許されない」という主張を見たので思ったことを述べる。 まず、主張自体はよくあるものであり、我々がよくやるように「ただの僻み根性」として一笑に付して…

Petrozavodsk campの北朝鮮セットであった問題で知見を得たので書き記しておきます。 問題 分割数の N 番目を求めよ。 解法 まず、DP[N][K]: K個の和でNを作る場合の数 とする。 1を使う場合と使わない場合に分けると、DP[N][K]=DP[N-1][K-1]+DP[N-K][K] が…

こんにちは。たまには有機的な投稿をします、DEGwerです。twitterで基本情報技術者試験、というものが話題に上がっていたので、過去問を解いてみることにしました。 筆者紹介 大学3年。中学3年のときに競技プログラミングを始める。開発経験なし、開発意思な…

解説を読んで実装した。FFTの練習。 問題概要 愚直DPを高速化してください 解法 DPの遷移の係数を求める式を見ると、DP列とある列との畳み込みになっている。FFTして一件落着！と行きたいところだが、DP[i]を求めないとDP[i+1]が求まらないので、オンライン…

問題概要 {1,2,...,N}^K の点を頂点とした K 次元超直方体を重ならないように M 個置く方法は何通りあるか。 解法 超直方体同士が重ならない どこかの次元でその超直方体が占める区間がdisjoint なので、1次元の場合に区間がどういう重なり方(M 区間のそれぞ…

見た目が解けるものに見えないが、実は解ける。見た目とのギャップがすごい。 問題概要 平面上にN点与えられるので、N点全てを一回ずつ使うサイクルを作って、隣り合う2点間のマンハッタン距離の総和を最大化せよ。 解法 x座標の中央値とy座標の中央値で切っ…

前4問は何だったのかという感じの良問。問題概要: 区間がN個与えられる。この区間たちに 1 or -1 を割り当てて、どの座標でもそれを含む区間の値の和の絶対値が 1 以下になるようなものを構成せよ。解法: まず全座標がdistinctなときにできるなら適当に順番…

最近、おかしな夢をよく見る。居眠りをしているときに、よく見る夢だ。 その夢は、それを見たのかどうかすらも分からないほどに抽象的で、一切の物理的な動きを、五感の働きを、焦りを、緊迫を含まない。一切の具体的な印象は、残らない。ふと目が覚めると、…

何かに熱心になること、そのことしか考えられないほど熱中すること、そして、純粋に好きという気持ちだけでそれを続けられること。 それは素晴らしいことだと思うし、皆そう思っている。寝るのも忘れてバットを振る野球選手は美しいし、ただひたすらに作品を…

変な問題だけど解法はそこそこきれい。パス長とサイクル長のペアたちが満たすべき条件は、 各サイクル長に対し、パス長0の点の数はサイクル長の倍数(サイクルをいくつつくるかの条件) 各サイクル長に対し、パス長xの点が存在しないならパス長x+1の点も存在し…

新年初AC。GoodByeのボス。今年(去年)のは骨がない。s-t間に2本の辺素パスが取れるという条件は、Mengerの定理より1点を取り除くとs-tが非連結になるという条件と同値なので、1点白いマスを除いてs-tを非連結にできるか判定すればいい。これは、追加する黒い…

参加記です。Hziwara, hogloidとCxiv-Dxivで参加していました。 一日目 家を出る。まだTXにすら乗っていない時間にもうつくばについている人々が大量にいて集合時間を間違えていないか不安になる。調べたら大丈夫そうなので北千住でラーメンを食べる。https:…

組合せ最適化で最大マッチングのところを読んで実装したので、解いた。 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2347問題概要: グラフがある。頂点1を含む長さ3以上の奇サイクルをとり、残りの頂点で完全マッチングを作れるか判定せよ。…

問題概要 k進法で0からn-1までの各桁の和mod kという数列があるので、異なる部分列の個数を求めよ。 k 解法 珍しくデータ構造系でない。良問。まず、部分列の個数は、各文字について、現れる次の位置に配るDPをやると重複なく数えられる。これでO(nk)のDPが…

問題概要 頂点数1000以下の単純無向グラフがあり、辺には番号がついている。辺の番号のある区間の辺のみ使って二部グラフをつくるとき、使えない辺のコストの最大値の最小値を1000回くらい求めよ。 解法 10^9を実装しても通るらしい。許さない。区間を平方分…

問題概要 文字列がたくさんある。次のクエリを処理せよ。クエリ: k個目文字列の中に出てくるr番目からl番目までの文字列のoccurrenceの合計を求めよ。 解法 安心安全の筋肉系文字列 & 平方分割。長い文字列に関してはSAで答えを前計算(Aho-Corasickをつかっ…

見た目に反してかなり面白い。わからなかったので解説を見たが、行間が異常に広かったので埋めるのに苦労した。この記事ではちゃんと行間を削った解説を書きます。 問題概要 1~Nまでの番号がついた頂点からなる木がある。各辺の両端の頂点番号の桁数のみわか…

問題概要: 区間をソートした後重複を取り除き、さらにそのi項目にフィボナッチ数列のi項目をかけたものの和を求めるクエリを30000個くらい処理せよ。解法: 最初に思いついたのが、区間を平方分割して、クエリを終点でソートし、sqrt(N)個のsegtreeを始点をず…

http://codeforces.com/contest/668/problem/F問題概要: サイズkのクリークから始め、サイズkのクリークの全点と新たに結ぶことで頂点を増やしていって作ったグラフの全域木の個数を求めよ。解法: 解説は木分解とかしてるしantaさんも意味不明なライブラリを…

VK Cup Round 3のボス問。 問題概要 区間を埋めるクエリと、区間のうちp%以上を占める数をすべて出力せよというクエリに答えよ。クエリ数, 数の範囲は150000, 20 解法 区間のうち1/5以上を占めるものしか出力しなくていいので、区間からランダムに何回か選べ…

問題概要 n人の人がいる。箱がたくさんあり、そのうち1個があたり。 毎日、各人は箱のうちいくつかを見て、その中に当たりが入っていた場合消える。p人まで消してよい。 i: 1~qについて、日数がi日のときに当たりの箱を特定できるような箱の個数の最大値を求…

問題概要: 文字列Sと、文字列X_1,...,X_Nが与えられる。次のクエリをQ個処理せよ。クエリ: l,r,p,qが与えられるので、X_lからX_rのなかで文字列[s_p...s_q]が部分文字列として一番多く現れるものとその回数を求めよ。 解法: suffix array+LCP+sparse tableで…

http://codeforces.com/contest/528/problem/E問題概要: 平面上に直線が3000本くらいあるので、その中の3直線をランダムに選んだ時の囲まれる面積の期待値を求めよ。 解法: 三角形ABCの面積は、原点をOとすると三角形OAB,OBC,OCAの面積の符号付和で書ける。O…

各クエリに対し、LCAが深い順に点を消していくgreedyをやる。setで隣り合うものに関する何かを管理するのは完全に闇。 こういうのどうやったらコンテスト中に通せるんだろう。 #include<stdio.h> #include<vector> #include<algorithm> #include<set> using namespace std; typedef pair<int, int>pii; t</int,></set></algorithm></vector></stdio.h>…

見かけに反して結構面白い。まずはじめに、420個から7個選ぶ場合の数はlong longに収まるので、条件を満たす場合の数を数えることにする。主要アイデアは、「ランクiまでのカードのうちj枚を使い、a,b,cの3つの系列がカバーされているかされていないかの組(8…