ferinの競プロ帳

競プロについてのメモ

AtCoder

AGC023 B - Find Symmetries

問題ページ B - Find Symmetries 考えたこと とりあえずよい盤面を書いてみる 斜めにずらしたとしてもよい盤面であるのは絶対に変わらない したがってB=iとしたときによい盤面であれば斜めにずらしてもよい盤面 O(N^3)なので書くとサンプルが通らない 対称な…

AGC023 A - Zero-Sum Ranges

問題ページ A - Zero-Sum Ranges 考えたこと 問題を読むと200点に見えないので真面目に考える とりあえず累積和を取ってみる i番目を左端とする区間で部分和が0になる区間はa[i]=a[j]となる したがってiより右でa[i]と等しいものの数を数える mapで現れた頻…

ARC096 F - Sweet Alchemy

問題ページ F - Sweet Alchemy 解法 問題の整理 d[i] = c[i] - c[p[i]] とするとドーナツをつくれる個数の条件である c[p[i]] <= c[i] <= c[p[i]] + D を 0 <= d[i] <= D と言い換えることができる。ただし根に関してはdに制限はなく 0 <= d[0] となる。 頂…

ARC096 D - Static Sushi

問題ページ D - Static Sushi 考えたこと 何か既視感を感じる どうせ引き返すのは高々1回 時計回り or 反時計回りに一方向に回るだけならO(N)で簡単に求まる dp1[i] = ([0,i]で得られる最大のカロリー、時計回り) dp2[i] = ([i,n-1]で得られる最大のカロリー…

ARC096 C - Half and Half

問題ページ C - Half and Half 考えたこと 頑張って数学O(1)もありそうだけど絶対つらい 制約を見ると10^5なのでO(max(X,Y))できる ABピザを2i枚使ったとするとAピザ、Bピザの枚数は一意に定まる 全探索をする ソースコード #define __USE_MINGW_ANSI_STDIO …

ARC035 C - アットコーダー王国の交通事情

問題ページ C: アットコーダー王国の交通事情 - AtCoder Regular Contest 035 | AtCoder 考えたこと Sを求めるには全点対の最短距離が必要 ワーシャルフロイドをしたい 辺を追加するクエリの度にワーシャルフロイドしてO(N^3)かけていたらO(N^3K)でまず通ら…

ARC094 D - Worst Case

問題ページ D - Worst Case 考えたこと よくわからないのでとりあえず実験する A<=Bとか仮定しておくと便利そう 一回目、二回目に小さい順位を取った人が条件を満たすようにしたい A=8,B=9 みたいなのが来たら下のように構成できて14個 1,71 71,1 2,35 35,2 …

ARC095 E - Symmetric Grid

問題ページ E - Symmetric Grid 考えたこと 行、列全体をswapするような操作をしてもその行、列に含まれる文字の集合は変わらない 行と列独立に考えたくなる 行を交換する操作について考える ある行を二つ取り出してきたときにその二つの行の組み合わせで点…

ARC095 D - Binomial Coefficients

問題ページ D - Binomial Coefficients 考えたこと C(x,y)はxが大きければ大きいほどよさそう x = max(a) で固定 O(n)でC(a[n-1],a[i])を全部求めればいい気持ちになるがa<=10^9で無理 よくよく考えるとC(x,y)のyはx/2に近い方がいい パスカルの三角形を考え…

ARC095 C - Many Medians

問題ページ C - Many Medians 考えたこと 中央値を取りうるのはa[n/2-1]かa[n/2]の二択 n/2番目以降ならa[n/2-1]、それ以外ならa[n/2] ソートすればいいのになぜか座圧を書く 座圧を書いたあとsampleを見て気づいてソートに書き直す 出すと通る 無駄に時間か…

Maximum-Cup 2018 D

問題ページ D - Many Go Round 解法 普通に部分和を求めるDPをしようとするとsum(a)<=10^8で状態数が大きすぎて不可能。ここで考察をすると持っておくべき合計は高々Mであることがわかる。dp[i][j] = (i番目の燃料までで休憩所jにたどりつくのに必要な最小の…

Maximum-Cup 2018 C

問題ページ C - 嘘つきな天使たち 考えたこと とりあえずグラフを書きたくなる 天使に隣接しているのは悪魔、悪魔に隣接しているのは天使になる 隣り合う頂点を違う色で塗り分けられればいいのでこれは二部グラフをつかって判定できる 二部グラフでなければ-…

Maximum-Cup 2018 B

問題ページ B: 駆け抜けろ!埼大山車部!! - Maximum-Cup 2018 | AtCoder 考えたこと 制約が小さいし全探索 d[y][x][向き][右折した回数][左折した回数] = (通ったか) としてBFSをする 左折がa回、右折がb回なのに逆にしてたり曲がる回数の条件を達成する前…

Maximum-Cup 2018 A

問題ページ A: フィギュアスケート界の貴公子埼大選手 - Maximum-Cup 2018 | AtCoder 解法 距離dの位置にt+10秒のタイミングでm個投げ込まれる。距離dの位置はd秒で通過するのでd<=t+10であればその位置のぬいぐるみを取れる。 ソースコード #include <bits/stdc++.h> using</bits/stdc++.h>…

AGC022 B - GCD Sequence

問題ページ B - GCD Sequence 考えたこと 全部2の倍数にしたいなーと思う 全体のgcdだけでなく要素の値の上限にも引っかかる とりあえず実験 小さい数でいれられるのをいれていってみると 2,3,10,… とかになる この調子だと上限30000なんてすぐに超えて人生…

AGC022 A - Diverse Word

問題ページ A - Diverse Word 考えたこと Sに含まれない最小の文字を後ろにつけたせばよさそう 26文字のが飛んでくるとつらい zyxwvutsrq…みたいなのがsuffixについてるとその部分を大きくするのが不可能そうな気持ちになる 頑張って探索しようとしたけど地…

AGC018 C - Coins

問題ページ C - Coins 考えたこと dp[i番目まで][金をもらった人数][銀をもらった人数][銅をもらった人数] みたいな愚直DP 金をもらった人数 + 銀をもらった人数 + 銅をもらった人数 = i なので銅をもらった人数は状態に持たなくても良さそう だからといって…

ARC092 E - Both Sides Merger

問題ページ D - Two Sequences 考えたこと 構築ゲーっぽいのでとりあえず実験 どうがんばっても隣の要素を足すのは不可能そう 位置の偶奇が違う要素はどうがんばっても足せなさそう 全部正の数なら奇数番目の要素と偶数番目の要素の和で大きい方が答えになり…

ARC091 F - Strange Nim

問題ページ F - Strange Nim 考えたこと 明らかにgrundy数の見た目をしてるので実験 石の数がk個未満になったら操作不可能なのでgrundy数を0とする いろいろ実験していると a%k=0ならgrundy数がa/kになることに気づく さらに実験していると 石の数a個のgrund…

ARC091 E - LISDL

問題ページ E: LISDL - AtCoder Regular Contest 091 | AtCoder 考えたこと 構築ゲーなのでとりあえず試す 昇順、降順で(3,4,5,2,1)みたいに並べてみると A+B=N+1 なら簡単に構成できそう Aに合わせてB=N+1-Aの列をとりあえず作ってみる N=8,A=3 なら (6,7,8…

ARC091 D - Remainder Reminder

問題ページ D: Remainder Reminder - AtCoder Regular Contest 091 | AtCoder 考えたこと a<=k-1だと存在しない bがaより大きければ剰余の結果がaそのままになるので条件を満たす b<=aで条件を満たすのが何個あるかを高速に知りたい とりあえず実験する 0 1 …

ARC029 C - 高橋君と国家

問題ページ C: 高橋君と国家 - AtCoder Regular Contest 029 | AtCoder 考えたこと 最小全域木を求めたくなる 最小全域木で使わない辺はいらなさそう 根をcが最も小さい頂点とした根付き木を考えればよさそう 辺を使わないことにして別の頂点を使うみたいな…

ARC028 C - 高橋王国の分割統治

問題ページ C - 高橋王国の分割統治 考えたこと 明らかに†全方位木DP†をしろという雰囲気をしている d[i] = (頂点iの部分木の頂点数) とする d_par は n-(進む頂点の部分木の頂点数) を渡せばよさそう テンプレに当てはめて書くと通った #include <bits/stdc++.h> using nam</bits/stdc++.h>…

ARC009 C - 高橋君、24歳

問題ページ C - 高橋君、24歳 考えたこと 正しく手紙をいれた人のパターンはC(N,K)でO(K)で求まるので問題ない 問題は誤ったK人の方が何パターンあるか 組み合わせを頑張ってO(1)とか考えるけど思い浮かばない 樹形図を書いて小さいケースについて実験する k…

AGC021 B - Holes

問題ページ B - Holes 考えたこと Rがめっちゃでかいのは別に気にしなくてよさそう 穴pに落ちる範囲の面積を求めて面積比を確率として求めるみたいなのを考える 穴pと他の穴qの垂直二等分線を引き、穴pが属する領域の凸多角形を求めるみたいなのをやりたくな…

KUPC2012 J - 刺身

問題ページ J: 刺身 - 京都大学プログラミングコンテスト2012 | AtCoder 概要 魚が1匹いてこの魚のi番目(1<=i<=n)の部分の重さはw[i]である。この魚をn個に切り分けたい。区間[l,r]がつながっている部分を一つ選びそのうち一箇所を切断するという操作を繰り…

「みんなのプロコン」本選 2017 C - 倍数クエリ

問題ページ C - 倍数クエリ 平方分割はじめてだったので練習として書いた 考えたこと mod m で考えてよさそう 平方分割なことは知ってたので考察をすると各バケツが数字が現れる頻度をもっておくとよさそう まとめてバケツに加算する配列lazを用意しておけば…

COLOCON -Colopl programming contest 2018- Final C - スペースエクスプローラー高橋君

問題ページ C - スペースエクスプローラー高橋君 CHTで解いてたけどmonotone minimaで解けるらしいので解くことにした 考えたこと f(i,j) = (i番のキャノンで区画jを破壊するエネルギー) 最小値がどんどん右下に移動していくのはそれはそう monotone minima…

square869120Contest #4 D - Driving on a Tree

問題ページ D: Driving on a Tree - square869120Contest #4 | AtCoder 全方位木DPに慣れるために解いた 考えたこと 頂点vからどこかの子に移動したら他の頂点vの子には絶対に到達しない d[i] = iを根とする部分木でiからスタートしたときの動く回数の期待値…

NJPC2017 E - 限界集落

問題ページ E: 限界集落 - NJPC2017 | AtCoder うしさんのブログを見て前半2問で全方位木DPを学んだので解説を見ずに解いた 考えたこと 各頂点から最も遠い頂点までの距離を求めて全てDより大きければ到達不可能なので-1 d[i] = 頂点iを根とする部分木で頂点…