問題ページ 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)でまず通ら…

問題ページ Twin book report | Aizu Online Judge 考えたこと まず本を読む時間を最小化することを考える 感想を書く時間を無視して読書にかかる時間の方だけ考える とりあえずソートしたい気持ちになる いろいろ試してると大体 sum(r) で読書が終わりそう …

問題ページ Long Distance Taxi | Aizu Online Judge 解法 拡張dijkstraをする。ガソリン量を10倍して1km/Lと考えると楽。 d[都市][残っているガソリン量] としてdijkstraをする。頂点がO(都市数*ガソリン量)で遷移がO(都市数)なので解ける。 入力が面倒だっ…

問題ページ Programming Contest II | Aizu Online Judge 解法 (点数、チーム番号)のペアの集合についてある順序が定められている。この集合に対する更新クエリとk番目の要素を探すクエリが飛んでくる。k番目の要素を探すクエリは平衡二分探索木 or 座圧して…

問題ページ ジグザグ数 | Aizu Online Judge 考えたこと 桁DPなのは知ってたので桁DPを考える dp[i桁目][B以下が確定か][mod M][最後に選んだ数][ジグザグ数になってないか上昇か下降か] を書く mod Mを上の桁から取るのが面倒そうだけどよくよく考えると mo…

問題ページ 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を見て気づいてソートに書き直す 出すと通る 無駄に時間か…

問題ページ Reverse Roads | Aizu Online Judge 考えたこと 有向グラフの辺を反転することでs-tフローを最大化する 与えられた辺を無向辺のように扱って両方の向きに辺を張ってフローを流す 最大フローの値はこれで求まる 反転すべき辺を求めるのには残余グ…

問題ページ King Slime | Aizu Online Judge 考えたこと 縦横で同じ軸にいるスライムは移動1回でくっつけられそう sample1を見ると縦横で同じ軸にいるスライムをつないでいってその連結成分にいるスライムは移動1回でまとめられそう つまり(連結成分の大きさ…

問題ページ Rectangular Stamps | Aizu Online Judge 考えたこと 各マスについてempty,R,G,Bの4種類の状態を持ちたい これが持てると集合を持ちつつ探索していけそう 4^16は無理 考察するとそのマスで必要な情報は最終的な色に達しているかどうかの2種類しか…

問題ページ A Holiday of Miss Brute Force | Aizu Online Judge 考えたこと 六角形のグリッド上を探索する 拡張dijkstraの要領で頂点に時間を増やせばいい気持ちになる 時間の上限ないしそのままつけるのは無理 時間が影響するのはabs(x*y*t)%6の指示される…

問題ページ 解法 ある矩形範囲(a,b,c,d)の最大値はその区間の max(A)*max(B), max(A)*min(B), min(A)*max(B), min(A)*min(B) のうちのどれかとなる。最小値についても同様にどれかになる。 最大値の個数については max(A)*max(B)が最大値であればmax(A)の個…

問題ページ Problem - D - Codeforces 概要 n頂点m辺の重み付き無向グラフが与えられる。このグラフに辺を張る操作をp回行うことで連結成分数がq個になるようにしたい。 辺を張るときは 同じ連結成分内の頂点なら1000 違う連結成分の頂点ならばmin(10^9, 連…

問題ページ Problem - C - Codeforces 概要 n要素の順列が与えられる。この順列に挿入ソートを行う。 この順列のどこか2要素をswapすることで挿入ソートでの交換回数を最小化しろ。 考えたこと ようするに転倒数を最小化すればいい i,j (i

問題ページ FizzBuzz | Aizu Online Judge 考えたこと 数xまでの文字数が何文字になるか Fizz,Buzzの部分は文字数が固定だからいいけど数字部分の文字数がずれるのがつらそう ずれないように桁ごとに分ける 1~9の中の3,5,15の倍数の数を数えると1~9のFizzBuz…

問題ページ Area Separation | Aizu Online Judge 考えたこと ある線を引く時、既に引いている線分との(交点の数+1)個領域が増える ただし一つの交点に3本以上の線分が交差している場合、重複して数えてはいけない 正方形の辺上で交わる場合を交差に数えては…

問題ページ Planning Rolling Blackouts | Aizu Online Judge 解法 func(sx,sy,gx,gy) = (指定範囲で実現できる最大のグループ数, グループの需要のうち最大) とする。その領域を分割しないか、縦に分割するか、横に分割するかの3通りの遷移がある。 分割し…

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

問題ページ 鉄道乗り継ぎ | Aizu Online Judge 解法 各鉄道会社について駅i->駅jに移動するときに必要な距離をワーシャルフロイドを用いて求める。各鉄道会社についてある距離を移動するために必要なコストは求めることが可能なので駅i->駅jへ移動するのにか…

問題ページ Starting Line | Aizu Online Judge 考えたこと にんじんを使うべきタイミングはいつか？ にんじんを食べていない && にんじんを持っている状況で食べずに持っているほうがいいときはなさそう 持ちきれないときも使ってしまった方がよさそう 上の…