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

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

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

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

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

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

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

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

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

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

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

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

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

問題ページ 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]の平均)) となる。…

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

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

問題ページ Aizu Online Judge Arena 概要 N個の自然数a[i]が与えられる abs(a[i]-a[j]) = 0 (mod n-1) を満たすような組(i!=j)を一つ示せ 解法 N <= 1000 でO(N^2)が間に合うので全てのペアについて探索すればよい ソースコード #include <bits/stdc++.h> using namespace </bits/stdc++.h>…

問題ページ Aizu Online Judge Arena 解法 まず、クエリを先読みして時間についてソートしておく。これでクエリについて順番に答えていくことができる。昼と夜の区別に注意。以下の実装では2d+1, 2eとして区別している。 ある区間について高速に値の更新を行…

問題ページ No.669 対決!!! 飲み比べ - yukicoder 考えたこと 取れる石の数の上限がK個のNim grundy数を使えという雰囲気を感じる 実験をすると「0 1 2 3 … k 0 1 2 3 … k …」みたいな周期になる つまり a[i]%(k+1) でそれぞれの山のgrundy数が求まる あとは…

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

問題ページ Restore Calculation | Aizu Online Judge 考えたこと 桁ごとに考えていけばよさそう 下の桁から繰り上がりがいるかとか考えればいける気持ちになる 場合分けが多すぎるので桁DPしたほうがよさそう dp[i][j] = (i桁目までで次の桁に繰り上がりが…

問題ページ Infinity Maze | Aizu Online Judge 考えたこと Lがめっちゃでかい 周期性がありそう x,y,向き について考えると40000通りしかないので鳩ノ巣原理から周期は高々40000 一回ループに入るまでシミュレーションをしてあとは周期性から求める mp[{x,y…

問題ページ Line Gimmick | Aizu Online Judge 解法 ある矢印の並びでi番目の矢印からスタートするとする i番目より左にある'>'とi番目より右にある'<'でのみ移動する方向を反転させる sample1で考えてみる 2からスタートすると1で反転→4で反転→0で反転→5で…

考えたこと 桁別に独立に見てよさそう (0, 0, 0, 1, 1, 1) みたいなのについて考えてみる 0の個数が奇数なら0のところを1に、1のところを0にすれば条件を満たしそう 逆にこれ以外の構成ある？ 0のところに0が当てはまっているものと1が当てはまっているもの…

考えたこと 頂点集合はもてないけど辺集合は持てるねみたいな感じのbitDPっぽさ dp[S] = (Sに含まれる辺は両端が赤い頂点な辺) とかをしたくなる どの辺の両端を赤くしたら他の辺で赤くならないといけない辺があったりいろいろ依存関係がある 1-2,1-3,1-4,1-…

考えたこと 辞書順最小と言われたので'a'を置けるなら置くみたいなのを書きたくなる 連続している'a'が多すぎて与えられた条件を満たせないときは'b'を置くしか無い {6,3,0,0,0,0} とかが与えられると "aabbaa" をつくれるけど上の規則だけだと "aabaab" が…

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

考えたこと 二重連結グラフをよく知らなかったのでググる 橋がないことと同値っぽい 最小全域二重連結グラフみたいな問題 グラフの形がかなり特徴的 頂点1,2が繋がるパスは 1-2,1-0-2,1-3-2 の3通りっぽい どの頂点も次数が2以上あれば条件を満たしていそう …