A問題 SubstringとSubsequece 普通にやるとn^3くらい掛かりそうだけど適当に節約したらn^2に収まった。 書いた。submit。pretest AC。 B問題 レミングスの問題。 ソートして順番に取ってとかあれこれ考えたが分からんから、とりあえず飛ばした。 C問題 チョ…

A問題 ソートしてgreedyにやるだけじゃん。 書いた。submit。pretest WA。なんか言ってるし、とりあえず放置。 B問題 割引されるのは一番高くてもstoolの商品なんで、一個ずつ入れるのが良い？ これもソートしてgreedyにやるだけじゃん。 書いた。submit。pr…

http://codeforces.com/problemset/problem/145/E 問題 4,7で構成される長さnの列がある。m個のクエリが来るのでさばけ。クエリは次の2種類。 区間[l, r]の4と7を反転させるクエリ。 区間[1, n]の非単調減少列の長さを答えるクエリ。 1 1 解法 セグメントツ…

A問題 Lucky Number回ですか。 幅優先探索をしようと思ったら数値が10^5以下じゃなくて文字列の長さが10^5以下だった。 greedyにやるだけなんで書いた。submit。pretest AC。 C問題 DPっぽいけどO(nk)は死ぬなあ。 Lucky Number以外はまとめて良くて、Lucky …

100回記念で100位以内ならTシャツがもらえるらしいので参加。 A問題 いきなりむずいな。 円があーだこーだと考えるより多角形って考えたほうが楽な気が。 n=1,2に注意しつつ書いた。submit。pretest AC。 B問題 readforcesきた。 読めない…。簡単な問題とい…

codeforces見たら昼間からあったので参加してみた。 A問題 問題が読めない。 なんかおかしいと思ったらstatuesをstatusと読んでた。 やるだけ。submit。pretest WA。 移動しない場合を忘れた。submit。pretest AC。 C問題 こっちの方が簡単そうなんで手をつ…

http://codeforces.com/problemset/problem/121/E 問題 n個の数値の列に対して、区間にd足す操作と区間にlucky numberが何個あるか聞くクエリがm個あるので実装しろ。 1 数列の数値が10^4を超えることはない。 解法 配列の平方根分割。

http://codeforces.com/problemset/problem/121/C 問題 n桁のk-th permutationはlucky numberがlucky numberの位置に何個あるか答えよ。 1 解法 k

http://codeforces.com/problemset/problem/121/B 問題 n桁の数値dが与えられる。k回、1-originでdのx桁目が4でかつx+1桁目が7である最小のxの部分を探す。そのような箇所が見つかる度に、xが偶数の場合はx,x+1桁目を4に変え、奇数の場合は7に変える。最終的…

http://codeforces.com/problemset/problem/121/A 問題 xより大きい最小のlucky numberをnext(x)と書くことにする。求めよ。 l 解法 同じ数になる部分をまとめて処理する。

研究室でだらだらしながら解いた。 A問題 問題分が読みにくだけ。というか入力4通りしか無いんかよ。 書いた。submit。Idleness limit exceeded。 なんぞこれ。調べてみたらinput.txtから読み込まないとダメらしいので書きなおしてsubmit。AC。 B問題 やるだ…

http://codeforces.com/problemset/problem/117/C 問題 トーナメントグラフが与えられるので長さ3の閉路があるか判定せよ。ある場合はその閉路を一つ出力せよ。 頂点数 解法 強連結成分分解で閉路を見つける。後は閉路の部分の1頂点を取り出し、その閉路から…

http://codeforces.com/problemset/problem/117/D 問題 1からnまでの数列がある。この数列に対して奇数番目の数値を前半に、偶数番目の数値を後半に移動させる操作Fを再帰的に作用させる。この変換によってできた数列をbとする。各クエリに対して を求めよ。…

A問題 エレベータで上下に動く問題。 s=fに注意してやるだけ。 書いた。pretest AC。 B問題 (a*10^8+b)%modが0にならないようにする問題。 mod回ループ回すだけじゃん。 書いた。pretest WA。 aの上限を入れ忘れた。pretest WA。 よく見たらmod-(a*10^8+b)%m…

lukcy number回。いつもと比べて問題文が読みやすい。 ところで7はともかくなんで4もluckyなんだろうか。 A問題 これって答えめちゃくちゃでかくならない？ 4の数、7の数だけ考えればいいから別にいいのか。 ある一定の数を超えると常に作れそう。どう作る？…

http://www.codeforces.com/blog/entry/2446 なんぞこれ。ディスガイアはやったことが無いんだけど。 A問題 元ネタがあるせいで問題文が長くなってる…。 転生するらしい。 やるだけっぽい。ただしdoubleは怖いので100倍してintにした方が良さそうだ。 書いた…

A問題 やっぱり英語が読みにくい 答えは1,2,3のどれかで条件分岐をがんばる 書いた。サブミット。pretest WA。 よく考えたらb=nの時がうまくいってなかった。pretest AC。 B問題 良く分からん。 wとか意味ないよね。というかgreedyで行けるんじゃね？ double…

A ドミノを並べる いつかの合宿で似たような問題でなかったっけ？ 問題文み間違えてた。上2列と下2列で区切って互い違いにするだけじゃん 書いた。pretest AC。 B いつも通り問題文が読みにくい Bにしては難しい気が とりあえず解は2部探索できるな 解を固定…

久しぶりに参加した。 A 2*2のアミュレットを回転させる問題 setに突っ込んで最後に4で割るだけでは？ よく考えると回転して重なる場合があるから4で割るのはダメで、ちゃんと今までに出てきてないアミュレットかどうかを判定してやらないといけない 書いて…