Topcoderの環境をUbuntuで作ったので試してみました。昔のSRMだとあまり考察がなくて解きやすく、実装力をつけるのにもってこいですね。Easy 一周するとwidth-2, height-2の場合に帰着できて、あとはwidth==2or1の場合分けをやる。 struct SpiralRoute { int…

http://arc070.contest.atcoder.jp/tasks/arc070_c関数dpとかいうやつ。僕のいうところの「愚直に値を持つ」dpと同じです。 愚直にx座標すべて持ってみることを考えて、実は本当に持つ必要があるものは少なくて、更新も簡単にできる、みたいな感じです。 |x-…

https://www.ioi-jp.org/camp/2012/2012-sp-tasks/setを使う問題といえばコレ。直方体の体積を断面図を考えて求めていく問題です。こういう問題でsetを使う際、 (1)番兵を使うと便利。 (2)lb,ubを覚えてまとめてerase(lb,ub)する。 (3)ある要素を見つけてそ…

http://codeforces.com/contest/875/problem/Eならし計算決めるアレです。 とりあえず距離kのとき行けるかどうかを判定する。 setでi番目まで処理し終わったとき、もう一人がどこにいるかを管理する。 i+1番目を考えて、もう一人の候補の座標としてありうる…

http://tenka1-2017.contest.atcoder.jp/tasks/tenka1_2017_fhttp://omochan.hatenablog.com/entry/2017/10/20/004232の続きです。普通に蟻本通りにやればいいだけでした…。 x≡k(modm) x≡k'(modm')を満たすxは x=mt+kとして mt≡k'-k(modm')をtについて解けば…

http://codeforces.com/contest/875/problem/Fprinceを点、princessの二人のprinceの候補を辺とみます。それからkruskalっぽいことをします。具体的には 1.違う連結成分どおしで、二つともlockedじゃなければ繋ぐ。 2.同じ連結成分どおしで、lockedじゃなけ…

http://tenka1-2017.contest.atcoder.jp/tasks/tenka1_2017_fある十分大きいx(A A^A^A^A...を考えるとKのmodφ(M)とmodMの値が求められるので、あとはユークリッドの互除法をして解を構成すればよい…なんですが、値がでかくなりすぎてWA…どうやって小さくする…

https://szkopul.edu.pl/problemset/problem/6YiP6JA5U15hY94pLwuHoYPg/site/?key=statement実践的アルゴリズム貪欲編です。少し観察すると(列をstripする回数==M)または(行をstripする回数==N)が成立することがわかります。 対称なので(列をstripする回数==…

http://poj.org/problem?id=1284答えはφ(p-1)個になります。証明しましょう。準備.n(|p-1)についてx^n≡1(modp)はちょうどn個の解を持つ。証明.p-1=nkとしたとき、 x^(p-1)-1=(x^n-1)(x^(n(k-1))+x^(n(k-1)-1)+...+1)であり、 x^(p-1)-1≡0(modp)の解はp-1=nk…

POJ 2115: http://poj.org/problem?id=2115A+Cx=B+(2^K)yの解(x,y)のうちxが非負で最小のものを求めればよい。これはユークリッドの互除法やるだけで求められるが、少し遠回りに書いたらREを起こしてえぇ…ってなりました。たぶんオーバーフロー起こしてまし…

http://poj.org/submit?problem_id=1150初中国剰余定理かもしれない。 (X/10^k)mod10を求めればいいです。ここでkはXが10で割り切れる回数です。 中国剰余定理より (X/10^k)mod10 (X/10^k)mod2, (X/10^k)mod5となります。 対称性よりmod5についてのみ注目し…

http://code-festival-2017-qualb.contest.atcoder.jp/tasks/code_festival_2017_qualb_e赤のボールがA,青のボールがB個の状態から選ぶ方法の数を再帰的に求めます。これを(A, B)と定義しておきましょう。 赤を選ぶ場合単に(A-1,B)とすればいいです。青を選…

http://code-festival-2017-qualb.contest.atcoder.jp/tasks/code_festival_2017_qualb_d結局10111111...または111111...101となる文字列を見つける問題になるんですが、言い換えが甘くて場合分けをミスり、WAを量産しました。証明しながら解くことの重要性…

http://code-festival-2017-quala.contest.atcoder.jp/tasks/code_festival_2017_quala_eまず最初に縦の向きに人を動かすとします。すると領域は二つに分断されます。そのうち一つについて横に進む人がX人、上から下に進む人がY人、下から上に進む人がZ人だ…

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

http://tenka1-2013-final.contest.atcoder.jp/tasks/tenka1_2013_final_d包除原理の良問です。目標を達成しないスケジュールを考えます。それはどれかの筋肉が目標を達成しなければいいです。 なのでS:=目標を達成しない筋肉の集合、f(S):=Sについて何通り…

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

http://codeforces.com/contest/855/problem/F平方分割強い(確信)平方分割してブロックでまとめて解く。 もしブロック内に0が存在したら普通に更新。 0がなかったら反対側を見て、0ではない値をとるようだったら配列に値を入れてsortする。 ブロックの更新が…