参加記です。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…