ferinの競プロ帳

競プロについてのメモ

AOJ

AOJ2297 Rectangular Stamps

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

AOJ2425 全探索お姉さんの休日

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

RUPC2018 day2 J Matrix

問題ページ 解法 ある矩形範囲(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)の個…

AOJ2441 FizzBuzz

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

AOJ2009 Area Separation

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

AOJ1176 輪番停電計画

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

AOJ1182 鉄道乗り継ぎ

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

AOJ2298 Starting Line

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

AOJ2601 Evacuation Route

問題ページ Evacuation Route | Aizu Online Judge 考えたこと そのマスから各出口へ到達できる最後の時刻を求めたい その出口に右から入るとき、その出口よりも右にある防火扉が閉まる前に超えられればok dp[i] = (区画iから左へ進んだときに出口に到達可能…

AOJ1248 The Balance

問題ページ The Balance | Aizu Online Judge 考えたこと aグラムがi個、bグラムがj個のとき ai + bj = d, ai + d = bj, ai = bj + d を満たせばdグラムを測れる iを決め打てばjは自動的に決まる iは何通りくらいあるのか? a=1,b=2,d=50000みたいなときに5*…

AOJ2303 Marathon Match

問題ページ Marathon Match | Aizu Online Judge 考えたこと i人目が走るのにかかる時間は (休んだ回数)*T[i] + L/V[i] 休憩所M個中r個で休む確率は C(M,r) P(i)^r (1-P[i])^(M-r) になる したがってi人目がj回休む確率とそのときのタイムを求められる i人目…

AOJ2157 Dial Lock

問題ページ Dial Lock | Aizu Online Judge 考えたこと 状態数が最大10^10あるから愚直は無理 回転させる数だけ気にすればいい気持ちになる i桁目について (t[i]-s[i]+10)%10 回回せばいい +1 +2 +4 +2 みたいなのが来たときに+2から+2の区間をまとめて回せ…

AOJ1320 City Merger

問題ページ City Merger | Aizu Online Judge 概要 要素数がNの文字列集合Sが与えられる。連続した部分文字列にSの要素を全て含むような文字列のうち最短のものを求めろ。 N<=14、(文字列の長さ)<=20 考えたこと suffixとprefixが一致しているような文字列の…

AOJ 1161 覆面算

問題ページ Verbal Arithmetic | Aizu Online Judge 解法 アルファベット10種類について考えるのが面倒なのでとりあえず座圧をすることにする。したがって以降に出現するアルファベットは'A'~'J'までの範囲であるとして考える。 ACE + DBE = DCFC 100A + 10…

AOJ2182 Eleven Lover

問題ページ Eleven Lover | Aizu Online Judge 考えたこと ある数が11の倍数の条件を考える 算数を思い出しながら考えると a[1] + 10a[2] + 100a[3] + 1000a[4] + … = a[1] + 10a[2] + a[3] + 10a[4] + … + 11(9a[3] + 90a[4] + …) なので a[1] + 10a[2] + a…

RUPC2018 day3 F: 最短距離を伸ばすえびちゃん (Ebi-chan Lengthens Shortest Paths)

問題ページ Aizu Online Judge Arena 解法 s-t間の最短経路に使われない辺をいくら伸ばしたところで最短経路は伸びない。したがって最短経路に使われる辺だけを抜き出したグラフを考えればよい。辺を抜き出す部分の判定は dist[i][j] = (iからjの最短経路) …

RUPC2018 day3 E: ブロッコリー?カリフラワー? (Broccoli or Cauliflower)

問題ページ Aizu Online Judge Arena 解法 部分木についてのクエリなのでオイラーツアーをしたくなる。オイラーツアーをした列に対して遅延セグ木を使って更新するいつものをしたい。updateが区間xor、queryが区間和の遅延セグ木を使えばその木にGとWのどち…

RUPC2018 day3 D: 素因数分解の多様性 (The Diversity of Prime Factorization)

問題ページ Aizu Online Judge Arena 解法 dp[i][j] = (i番目までで今までに使った最大の素数がj) みたいなDPを書きたくなる。しかしこれでは状態数がO(N*(max(q)以下の素数の数))となり間に合わない。ここで連続した2数が指数の方になることはありえないこ…

RUPC2018 day3 C: AA グラフ (AA Graph)

問題ページ Aizu Online Judge Arena 解法 やること自体は簡単で与えられた二次元グリッド上でつながっている頂点同士をつないだグラフをつくり、あとはdijkstraなりワーシャルフロイドを貼るだけ。ただし実装が非常にバグらせやすいので要注意。 以下に示し…

RUPC2018 day3 B: 階層的計算機 (Hierarchical Calculator)

問題ページ Aizu Online Judge Arena 解法 答えが1以下になるようならば式を一つも評価せずに1とするのが答えが最大でなおかつ最も短い部分列となるので最善となる。つまり、a[i]=0を使う意味はない。またa[i]=1を使ったとしても値が変わらずに部分列の長さ…

RUPC2018 day2 G: Combine Two Elements

問題ページ Aizu Online Judge Arena 解法 1つ目の削除方法が可能なペアに2つ目の削除方法を適用する意味はあるのか考えると、操作回数で得できるわけではなく無駄にペアが多く消えているので得することはなさそう(要証明)。なので、1つ目の削除方法が可…

RUPC2018 day2 F: Ghost Legs

問題ページ Aizu Online Judge Arena 解法 あみだくじで最終的にどこにたどりつくかのみが重要なので途中の横線の位置を気にする必要はない。縦線3本のあみだくじでは 3!=6通り の置換にまとめられる。 恒等写像にならないような置換の組み合わせを考える。(…

RUPC2018 day2 E: Light

問題ページ Aizu Online Judge Arena 解法 拡張dijkstraをする。頂点を(i番目の街灯,コストj)とする。 遷移について 始点から街灯 始点と街灯のマンハッタン距離のコストをかけて街灯を明るくする必要がある 街灯から終点 街灯と終点のマンハッタン距離のコ…

RUPC2018 day2 D: AABABCAC

問題ページ Aizu Online Judge Arena 解法 1回操作すると文字列の長さは少なくとも半分になるので操作回数はO(log|S|)程度になる。 x回操作するために文字列s中にどのような文字列が必要か考える。x=1では文字列sの部分文字列としてtが存在していれば操作が…

RUPC2018 day2 C: Ball

問題ページ Aizu Online Judge Arena 解法 価値が低いものを価値が高いものより優先する意味はない。各色iで取る可能性のあるボールは価値が高い上位l[i]のみに絞られる。さらにこのボールの中から価値が高いボールをM個選べば答えが求められる。 ナップザッ…

RUPC2018 day1 F: ごちうさ数

問題ページ Aizu Online Judge Arena 解法 桁DPをする。dpテーブルを dp[i桁目][j,下3桁][k,N未満確定か][l,ごちうさ数か] とする。次の桁の数をnxtとしたとき下3桁は j%100*10 + nxt となる。N未満かは k || nxt < lim とする桁DPのよくあるやつで確認でき…

RUPC2018 day1 E: いたずらされたグラフ

問題ページ Aizu Online Judge Arena 解法 a,b,c の3頂点で閉路となっていてこのような閉路がN個ある。閉路の3辺から1つの辺を選んで構成したグラフでのs-t間の最短経路を求めたい。 経路a->bよりも経路a->c、c->bとたどっていくような経路の方が短くなるこ…

RUPC2018 day1 D: 水槽

問題ページ Aizu Online Judge Arena 解法 dp[i][j] = (i番目まででj個の区画を作った状態での水の高さの合計のmax) とする。 dp[i][j] -> dp[k][j+1] へ配るDPとして書くと、漸化式は dp[k][j+1] = max(dp[k][j+1], dp[i][j] + (区間(i,k]の平均)) となる。…

RUPC day1 C: 一致

問題ページ Aizu Online Judge Arena 解法 sigmaさんのコードを参考にさせてもらった。 multi_setの同型判定をハッシュを用いて行う。a[i]に対応するハッシュ値を乱数で決める。multi_setのハッシュ値を (存在している値のハッシュ値) * (存在している数) の…

RUPC day1 B: 写像

問題ページ Aizu Online Judge Arena 解法 写像fが全射であれば問題の条件を必ず満たす。 もし全射でなければf(x)として現れない数が必ず存在している。そのような数zについてg(z) != h(z)となるように構成すればよい。 ソースコード #include <bits/stdc++.h> using namesp</bits/stdc++.h>…