ferinの競プロ帳

競プロについてのメモ

Codeforces

チーム練習 11/29

チーム練で 2018-2019 ACM-ICPC, Asia Seoul Regional Contest をやった.6完961で20位相当 (開始) おるふぇがテンプレを書き,手分けして問題を読む.Lマッチングでフローか?とか言ってた. (11分) Dが簡単らしくおるふぇが書いてAC.Lが通っているので考…

2018-2019 ACM-ICPC, Asia Seoul Regional Contest K - TV Show Game

問題ページ 2SATで解く. 番目の電球がBならtrue というbool変数を用意する.例えば,1 R 2 B 3 R が与えられたとする.このとき ( or ) and ( or ) and ( or ) を満たす真偽値の組合せが存在すればよい.これはSCCを用いると で解ける. #include "iostream…

2018-2019 ACM-ICPC, Asia Seoul Regional Contest J - Starwars

問題ページ ij = human側からスタートして頂点 にいる,not human側からスタートして頂点 にいる という状態が可能か? という配列を持つ.もし に到達可能で が同じ である辺が存在したら にも到達することができる. human側の頂点,not human側の頂点から…

2018-2019 ACM-ICPC, Asia Seoul Regional Contest G - Secret Code

問題ページ の順列6通り全てについてそれぞれ確率を計算し足し合わせることで答えが求められる.以下では について考える. を固定したとき, が出会う確率 は となる. が出会う確率 は となる. がその時刻である確率は で求められる. は独立であるから,…

2018-2019 ACM-ICPC, Asia Seoul Regional Contest C - Disks Arrangement

問題ページ まず答えを とする.ここから円盤を隣接させて被る分を引いていく. と を隣接させるときに減少させられる幅は である.順列をうまく定めることでこの幅の和を最大化したい.グラフで表現すると 頂点の完全グラフで,頂点 と の間に の重みの辺を…

2018-2019 ACM-ICPC, Asia Seoul Regional Contest A - Circuits

問題ページ 長方形のx座標は何も関係がなくて結局区間の問題になる.区間の端点以外に線を引くことで得をすることはない.よって「 個の区間が与えられる.区間の端点のから2点を選ぶ.この2点の少なくとも一方を含む区間の個数を最大化しろ.」という問題に…

Codeforces Round #600 (Div. 2) F - Cheap Robot

問題ページ ボロノイMSTの要領でcentralが頂点となっていて辺の重みが元のグラフのcentral間の最短距離であるようなグラフを構成する. capacityが のときにクエリ を達成可能か? グラフで と のパスの重みのmaxが以下 となる. を決め打つと,使用できる辺…

Codeforces Round #594 (Div. 1) C. Queue in the Train

問題ページ 基本的にやるべきことは問題文に書いてあるのでそのシミュレーションを行う.ただし, の範囲で を1ずつ増やしてシミュレーションをすると当然TLEなので,シミュレーションに関わってくる重要な時刻のみ取り扱う.人が席を立つ時刻 と水を汲み終…

Codeforces Round #594 (Div. 1) B - The World Is Just a Programming Task (Hard Version)

問題ページ まず,開括弧と閉括弧の数が一致していなければ答えは0である.以下では開括弧と閉括弧の数が一致しているとする. s=((())())() x=1232121010 次に,与えられた文字列が正しい括弧列でなかった場合を考える.'('が来たら+1,')'が来たら-1をする…

Educational Codeforces Round 75 E2. Voting (Hard Version)

問題ページ の人を無料で投票させるのには,他の人全員から投票されていなければならない.したがって, の人から1人(最も買収するのにお金がかかる人)以外は必ず買収する必要がある. の人を無料で投票させるには,が未満の人数で買収した人数 人を の人か…

AIM Tech Round 5 (rated, Div. 1 + Div. 2) D. Order book

問題ページ 解法 サンプル2について考える. 4 ADD 1 ADD 2 ADD 3 ACCEPT 2 ACCEPTが正常に行われるには2がBUYの最善かSELLの最善である必要がある.したがって2未満はBUY,2より大きいものはSELL以外にすることが不可能でどちらにすべきか確定する. このsa…

Technocup 2019 - Elimination Round 1 E. Vasya and Good Sequences

問題ページ 解法 まず区間 を一つ固定して,この区間が条件を満たせるかの判定を考える. ビットが立っている数が同じであれば作れる数字の集合は同じなため の値は本質ではなくビットが立っている数が大事. のビットが立っている数とする. とできる方法が…

Codeforces Round #290 (Div. 1) C. Fox And Dinner

問題ページ 解法 2以外の偶数は素数にならないことからa[i]とa[j]の偶奇が一致するときa[i]+a[j]は素数にならない a[i]+a[j]が素数であれば頂点iと頂点jを結んだグラフは二部グラフになる 二部グラフから各頂点の次数が2になるように辺集合を選ぶ問題に帰着…

Codeforces Round #557 (Div. 2) [based on Forethought Future Cup - Final Round] C. Thanos Nim

問題ページ 解法 どのような状態が勝ち/負けなのか考える。n=6で試してみる。0が4個以上の場合操作できないのでその時点で負けである。0が3個以下の場合、0が4個以上になるように操作して相手に渡せばよいので勝ちになる。1が4個以上の場合、どう操作しても0…

Codeforces Round #554 (Div. 2) D. Neko and Aki's Prank

問題ページ 解法 木において最大マッチングを考える場合、葉が隣接する辺から貪欲に取っていけばよい。葉が隣接する辺を取らなかったことでマッチングに追加できる辺の本数は高々1本なので取らないことで得をすることはないからである。よってTrie木で根から…

Codeforces Round #551 (Div. 2) E. Serval and Snake

問題ページ 解法 パスの端点を一つも含まないような範囲 範囲に入った後出ることを繰り返すので返ってくる値は必ず偶数 パスの端点を両方含むような範囲 範囲から出た後入るを繰り返すので返ってくる値は必ず偶数 パスの端点を片方だけ含む範囲 範囲内と範囲…

Codeforces Round #556 (Div. 2) D. Three Religions

問題ページ 解法 まずクエリが存在しない場合にどのように解くか考える。構造が複雑で制約も小さいのでdpをする。 文字列 の 番目までで(文字列1の 文字 && 文字列2の 文字 && 文字列3の 文字)をつくれるか? という愚直なdpがあるがこのままでは状態数が大き…

Codeforces Round #539 (Div. 2) F. Sasha and Interesting Fact from Graph Theory

問題ページ 解法 頂点a,bを結ぶパスの辺をe本と固定したときの組み合わせ数を求める。まずn-2個の頂点からパス上のe-1個の頂点を選ぶ方法がP(n-2, e-1)通りである。次にパス上の辺の重みを決定する方法について考える。mをe分割する方法はm個のボールの間(m-…

Codeforces Round #548 (Div. 2) D. Steps to One

問題ページ 考えたこと gcd=gと決め打つと長さの期待値が割と簡単に求まる気がする 長さnの確率は (gの倍数の確率)^(n-1) * (gの倍数以外の確率) っぽい g=2,3 の両方で 6, 6, 6, 6,…, 1みたいなのを重複して数えてる 約数系包除で数えられそう 期待値をちゃ…

Educational Codeforces Round 60 D. Magic Gems

問題ページ 解法 dp[i]=(i個分スペースを埋める方法が何通りあるか)としたDPを考える。i個スペースを埋めるためにはmagic gemを一つ置くパターンとmagic gemを分割しnormal gemをM個置くパターンがある。したがってこのDPの遷移は dp[i] = dp[i-m] + dp[i-1]…

Educational Codeforces Round 60 C. Magic Ship

問題ページ 解法 i日目に到達可能な場所がどのようになっているのか考える。(x1,y1)=(0,0)、s="UDRL"のときの例を以下に示す。 風が吹く方向と逆方向に移動すればi日目で到達したマスはi+1日目以降でも到達可能なことがわかる。したがってi日目にはi以下の地…

Educational Codeforces Round 48 (Rated for Div. 2) D. Vasya And The Matrix

問題ページ 解法 bitwise xorなのでbitごとに独立に考えられる。したがってbitごとに考えればa,bは0/1の数列に帰着でき、答えの行列も0/1要素しか持たないと考えてよい。1が書かれている行・列には1を奇数個、0が書かれている行・列には1を偶数個置くような…

Codeforces Round #525 (Div. 2) D. Ehab and another another xor problem

問題ページ 解法 xorなのでbitごとに見ていくのが基本的なパターンになる。クエリ回数の上限が62回なので30bit分について2回ずつクエリを飛ばして決めていけばよさそう。大小関係について見ていくので上のbitから順番に決めていくとよさそう。 c=d=0のクエリ…

Educational Codeforces Round 55 (Rated for Div. 2) E. Increasing Frequency

問題ページ 解法 ある区間[l,r]を選択したときに最適なkの値について考える。[l,r]の中で最も出現頻度が多い値がcになるようにkを設定すればよい。したがって区間[l,r]に操作をしたときの答えは([l,r]以外のcの数) + ([l,r]で出現頻度が最も多い回数) - ([l,…

Technocup 2019 - Elimination Round 3 D. Barcelonian Distance

問題ページ 解法 最短経路としてあり得るのは直線ax+by+c=0に高々1回乗るような経路しかありえない。x=sxかy=sy上を移動したあと直線上を移動しx=gxかy=gy上を移動するパターンか直線上を移動せずに距離abs(sx-gx)+abs(sy-gy)を移動するようなパターンをすべ…

Educational Codeforces Round 54 D. Edge Deletion

問題ページ 考えたこと 最短路DAGを考えると無向グラフで最短路に使われる辺だけを抽出すると木になるはず dijkstraの途中で遷移に使った辺を覚えておけば最短路に使われる辺はわかる k>=n-1であれば使われた辺すべてを出力すればよい k<n-1であれば頂点1に連結になるような辺をk本選べばよい 最短経路長が短い頂点の遷移に使った辺から取っていけば非連結な辺を取ることはないはず 最短路に使う辺を列挙して最短経路長が短いものからmin(n-1,k)本の辺を取ればよさそう #include <bits/stdc++.h> using namespace std</n-1であれば頂点1に連結になるような辺をk本選べばよい>…

Mail.Ru Cup 2018 Round 2 C. Lucky Days

問題ページ 解法 g=gcd(ta,tb)とする。各区間についてgずらすことが可能である。la, lbを両方0に近づけるあたりに最適な区間がある。なので0に近づけた辺りをある程度探索すれば答えが求まる。 [la, ra] と [lb, rb] の共通部分はmax(0, min(ra,rb)-max(la,l…

Codeforces Round #523 (Div. 2)

問題ページ 考えたこと 区間スケジューリングっぽい DPができる気がしないので貪欲を考える 区間スケジューリングでは最後に仕事をした時刻を1つ持てばいいが今回は複数ある あるTV番組[l,r]があったとき、前に見たTV番組のうち終端がl未満で最大の区間につ…

Codeforces Round #520 (Div. 2) D. Fun with Integers

問題ページ 問題概要 次の条件を満たすとき整数aから整数b(2<=|a|,|b|<=n)に変換することができる。 (条件) |x| > 1 となる整数xについてax = b もしくは bx = a を満たすものが存在する。a->b、b->aの変換を以前に行っていない。 この変換をすると|x|点の得…

Technocup 2019 - Elimination Round 2 D. Minimum path

問題ページ 考えたこと 辞書順最小なので前から貪欲に取ることを考える 文字列の最初の方で交換可能でaでないものがあったらaに変えたほうが確実に良い 答えの文字列はaa…aabcdaefのように接頭辞にaが連続している 接頭辞のaが何個か考える 二次元グリッド上…