問題ページ 解法 解説にある通りAを+1, Bを-1に置き換えて累積和を取って標高図を書いてみる。操作を終えたあとの最終的な文字列はA…AB…Bとなる。標高図のminが最終的な標高図のminになるまでとそこから標高図のmaxが最終的な標高図のmaxになるまでの2つに分…

問題ページ D - AtCoder Express 2 解法 区間がたくさん与えられるときはとりあえず終点でソートする。あるクエリ(p[i],q[i])が与えられるとき、数える対象となる路線はr[j]<=q[i]であるような路線のみである。したがって終点ソートしておき尺取法の要領で対…

問題ページ C - Cheating Nim 考えたこと Nimの勝利条件から問題文を言い換えたい 不正者が勝てるのは a[0] xor a[1] xor … xor a[n-1]=0 のときだけ 山の石の数を-1する操作で上の条件を達成する問題になった xorなのでビットごとにみたくなるので2進数の形…

問題ページ H - 白黒ツリー 解法 頂点に関する制約条件を扱うのは大変なので辺のコストの条件に置き換える。両端の頂点の色が違う辺のコストは0、両端の頂点の色が同じ辺のコストは1とする。こうするとクエリ2について頂点uとvの2頂点間の距離が0かどうかの…

問題ページ B - Neutralize 解法 DPをする。dp[i] = (区間[0,i]の最大値) とする。遷移について考えると max(dp[j]) (0<=j<=i-k) dp[i-1] + b[i] 0 (k-1<=i) の3通りになる。上から順に区間[j,i]を0にする、i番目の薬について0にせず足す、区間[0,i]全体を0…

問題ページ A: Happy Birthday! - AtCoder Beginner Contest 100 | AtCoder 解法 a <= 8 && b <= 8 なら条件を満たしているのでYay!、違うなら:(を出力する。 abs(a-b) <= 1 ならとか考えてたら2分かかってしまった。 ソースコード #include <bits/stdc++.h> using namespac</bits/stdc++.h>…

問題ページ B: Ringo's Favorite Numbers - AtCoder Beginner Contest 100 | AtCoder 考えたこと ちょうど0回割り切れるって何だと思ってサンプルを見たら1回も割りきれないことっぽい nの後ろに'0'を2d個つければいいでしょと思って投げる 落ちてて何事かと…

問題ページ C: *3 or /2 - AtCoder Beginner Contest 100 | AtCoder 考えたこと 全ての要素に対して2で割るか3倍するのどちらかをするのかと思う 全てのiに対して3倍するって何のことだと思って数分が経過する 操作1回につき各要素について2で割るか3倍する…

問題ページ D: Patisserie ABC - AtCoder Beginner Contest 100 | AtCoder 考えたこと 与えられる値が全て正だったらx[i]+y[i]+z[i]が大きい方から取ればいいだけ 最大化するのは絶対値で負がある それぞれ正負を試せばいいのでは？ 正負を固定すればソート…

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

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

問題ページ 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] となる。 頂…

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

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

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

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

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

問題ページ 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に近い方がいい パスカルの三角形を考え…

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

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

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

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

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

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

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

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

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

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

問題ページ 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…

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