http://codeforces.com/problemset/problem/923/DA 良問。どこまで減らせるかが貪欲で求まる。 B 雪山について独立に考えれば。 C よくあるbitのやつ。これtrieでやるのかなぁ…segtreeっぽくしちゃったけど。また使いそうなので貼っときます。 int K = 1; st…

https://beta.atcoder.jp/contests/arc102/tasksC K/2が肝とわかれば。 D 2^nの辺を張って、適当に付け加えれば良さそうと思って実際そうでした。添字がめんどい。 int L; vector<pi> G[20]; void solve() { cin >> L; int N = 1; while(L >= (1 << N)) N++; rep</pi>…

https://arc081.contest.atcoder.jp/tasks/arc081_d まず2*2の正方形に注目して塗られているマスが奇数個だとその正方形を一色にすることはできないことに気づきます。そうしたらそのような正方形を全部含まないような長方形のうち最大のものを求めればいい…

https://cf17-final-open.contest.atcoder.jp/tasks/cf17_final_iだいぶ時間使ったけどなんとか解けました。良問です。順位表が求められればトーナメント上の順番は簡単に求まります。順位表上でi番目がj番目よりも小さくならなければならない条件をi->jに辺…

https://beta.atcoder.jp/contests/agc010/tasks/agc010_eO(N^4)からの高速化が思いつかなかった…。まずAiを頂点としたグラフを考えて、互いに素ではない頂点同士をつなげます。すると各連結成分で一番小さい要素をcとしてcのうち最大のものを取るのが最適だ…

https://agc020.contest.atcoder.jp/tasks/agc020_dお気持ちそのままが解法ですが、実装がめんどくさすぎる…。1発ACだけど詰めるのにすごい時間かかった。 A>Bとします。Bまず文字が何個まで連続できるかを求めます。これは少し考えればfloor( (A+B)/(B+1) )…

https://agc003.contest.atcoder.jp/tasks/agc003_d本質を勘違いした…まず素数のうちa個あるものはa%3個にしてよいです。それでvをcubeにする値uをつなげたグラフを考えると二部グラフになるので、max( (vの数),(uの数) )の合計を求める問題に帰着できます。…

https://yahoo-procon2018-qual.contest.atcoder.jp/tasks/yahoo_procon2018_qual_e検索するとこんなのが出てきます。次数 (グラフ理論) - Wikipediaここにある式をそのまま使えばいいです。1を足す時でも式で考えれば一番小さい次数を1上げれば良いことがわ…

https://agc012.contest.atcoder.jp/tasks/agc012_c12345...12345...みたいに並べて2^n関連でやることは見えたけどそこからが思いつかなかった。 要素入れ替えたりを考えたけど、想定解は挿入でした。やっぱり秩序なくやるよりも、定式化できそうな良い構造…

https://beta.atcoder.jp/contests/agc010/tasks/agc010_dやっぱこういうのは偶奇ですね…。操作を良く観察すると、奇数で割っても偶奇が変わらないことに気づきます。なので列に奇数が2つ以上ある場合、または奇数が1つでもそれが1の場合、結局1ずつdecremen…

https://colopl2018-qual.contest.atcoder.jp/久しぶりの投稿です。いろいろ忙しかった。 やっぱりコンテストだと結構焦ってまともに考えられないなぁ。C 偶数は一緒に使えないので、すべて奇数or奇数+偶数1つという組み合わせしかありません。 あと、35以上…

https://beta.atcoder.jp/contests/arc084/tasks/arc084_c0-originでfloor((X+1)/2)-1番目を求める問題です。Xが十分大きければ、最初の文字は(K+1)/2になり、 Nを１つ減らした時の((X+1)/2)-1-(X%2)番目を求めればいいです。なので、X%2の累積分を考えると…

http://tenka1-2016-quala.contest.atcoder.jp/tasks/tenka1_2016_qualA_d構築ゲー。まずゆるーく考えると適当な頂点を根にして辺の長さを2^n,2^(n-1)...としていけば作れることがわかる。 あとはこれを座標圧縮でキツくすればよい。構築ゲーで大事なのはお…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2427全探索といえばこの問題だよね。最初を除いたどの馬車も最小値をとりうる場合、次のうち二つの条件のうちどちらかを満たします。 1.終点or少し広いところで交わるほかの馬車が存在する。 2.1…

http://code-festival-2017-quala.contest.atcoder.jp/tasks/code_festival_2017_quala_d45度回転をするとマンハッタン距離|x1-x2|+|y1-y2|がチェビシェフ距離max(|x1-x2|,|y1-y2|)に言い換えられて見通しが良くなります。 45度回転したGrid上でD*Dの正方形…

http://codeforces.com/contest/843/problem/C重心を根としてウニみたいなグラフを構成します。具体的な方法は http://kmjp.hatenablog.jp/entry/2017/09/05/0900 ここに書いてあります。 重心が複数個あるときもほとんど同じです。(複数といっても高々2つな…

http://codeforces.com/contest/860/problem/D解いたあとだとめっちゃ自明に見えるけどかなり苦労した。dfs木を作った後、2辺ずつ木の下からとっていく。 ある点vを中間の点としたpathがとれるときはとる。 取れない場合はvの親pに向かう辺(v,p)を残す。 そ…

http://arc077.contest.atcoder.jp/tasks/arc077_d実験的にやるのがたぶん正攻法だけど、もうちょっと文字列の周期のこととかに気を配れるとよかった。解説にも書いてありますが、g(n+2)=g(n+1)+g(n)になります。これは実験をすると比較的簡単に気づけます。…

http://agc019.contest.atcoder.jp/tasks/agc019_dなんとなくの解法はわかるけど詰めるのが結構難しいと思う。Sをiだけ右にshiftした場所でTと一致させることを考える。 移動したSとTを比較したとき、Si == 1 && Ti == 0のとき、その場でSiを0に反転させるこ…

http://agc017.contest.atcoder.jp/tasks/agc017_c解説を見るとこんなうまいやり方があったのかぁ…となるんですが、それをどうやって思いつけるようになるかが重要だと思います。 僕はこう考えたらしっくりきました。まず魔法をかける前、ボールがどうなって…