なんか競技プログラミングでやりたいことを明確に文字に起こした方がモチベが上がるかもという試みです。 TODOが達成出来たり,他のやるべきことが出来たらまた書くかもしれないので、＃1ということで。 Codeforces とりあえず20回分ぐらいのA～C(出来たらDま…

はじめに 3月にあったRUPC2016で中々良い思いをさせてもらったので、調子に乗って大学生ではないですがACPC2016に参加させていただきました。 tookunn.hatenablog.com この記事を見た合宿参加者はぜひ参加記を書いて楽しかった思い出を共有しよう！！ 1日目 …

問題 codeforces.com 考察 ・文字列に含まれる00,11の数はそれぞれ(0or1の数) * (0or1の数 - 1) / 2になる。(最初は0or1の数C2の組み合わせの数かと思ったけどよく考えると長さは一定して2なのでさっきの式になる)・00001111から00010111にすると,00の数と11…

A 問題 codeforces.com 考察 ・"OO"があれば"++"に変えるだけ。 ソースコード import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.NoSuchElementException; import java.util.*; public class Main { i…

A 問題 codeforces.com 考察 ・とが同じことに気付く。・が分かっているので,をからの順で問題文の式通りに求めていく。 ソースコード import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.NoSuchElemen…

問題 No.420 mod2漸化式 - yukicoder 考察 ・まずは素直にを書き連ねてみる。 ・が奇数の時にになっていることに着目する。・つまり,を2進数で表現した時1が立っているビットの数がになる。・はまでなので、はまでしかないことが分かる。・を普通にからまで…

問題文 codeforces.com 考察 ・が作ることが出来るクッキーの数・作ることが出来るクッキーの数を二分探索で求める。・個のクッキーを作る場合はそれぞれ材料が * M]必要になり、 * M - b[i]]が1以上の場合に魔法の粉を使ってKを消費していく。・そして、す…

問題文 codeforces.com 考察 ・の文字列内の開き括弧と閉じ括弧の個数が同じでなければならない・に使われている開き括弧と閉じ括弧の数が分かればに使われる開き括弧と閉じ括弧の数が分かる・長さの文字列で開き括弧が閉じ括弧より個多いときの組み合わせ・…

問題文 codeforces.com 考察 解説見て解きました。まさか破壊される個数じゃなくて破壊されない個数の最大値を求めるDPとは。・数直線上のi位置のbeaconを起動させて左にの位置までのbeaconを破壊した時のからの位置までの残っている破壊されないbeaconの最…

問題文 codeforces.com 考察 ・,tx,ty)]を番目のbottleからまでの距離とする。 ・・よく考えるととそれぞれ最初に拾うbottleと最後に拾うbottle以外はとを往復するのでとなる。・あとはから最初に到達する最短のbottleを選んで,から最初に到達する残りbottle…

問題 codeforces.com 考察 今回は解説見ないで出来た。・試しに自分での数列を考えて、考察したら思いついた。(というか本当によくよく考えたらそう)・実は数列の部分列のように1ずつ増加している最大長の部分列(ここでは最大長の)について問題文にある操作(…

問題文 codeforces.com 考察 ・頂点をrootとして,頂点は頂点に,頂点は頂点に,..., 頂点は頂点につながっているとする。・以上から を頂点から頂点までの間のedgeのcostの合計の最大値として, が成り立つ。・あとはrootから辺を辿ってそれぞれの葉まで探索し…

codeforces.com 全体的に問題文の量が比較的多くて辛かった...。誤読も多かったし。 A 問題 codeforces.com 考察 ・まず、半径をr,円周率(3.14...)をpiとすると1秒間に増加する量はr * r * pi * eとなり、v(1秒間に減少する量)より多ければ、容器の中の水は…

codeforces.com A 問題 codeforces.com 考察 ・回ループを回して、ループ回数の偶数、奇数の場合分けをすれば良い。 ・最終的に出力される文字列をうまいことループで表現できないかを考える。 ソースコード import java.io.IOException; import java.io.Inp…

問題 codeforces.com 考察 ・が素数Pで割り切れる場合はとで1000ドルずつ、合わせて2000ドル発生する。・が素数Pで割り切れるときは、または最低でも一方がPで割り切れなければならない。・つまり、とがどちらもPで割り切れないのならば、2000ドルは発生しな…

問題 codeforces.com 考察 ・区間にFoePairsが含まれている場合、区間にはForPairsが含まれているので、カウントしない。・つまり,区間の始点からFoePairsが含まれているような最小の終点を分かれば良さそう。・尺取り法を使うっぽい。・問題ページのサンプ…

問題 agc001.contest.atcoder.jp 考察 ・直径がとなる木を考えた時の、中心となる木の頂点を中心点と呼ぶ。・中心点から距離が以下となる頂点の数を最大になるような中心点を選べば、削除する点が少なくて済む。・が奇数の時は、中心点の隣接する頂点一つを…

codeforces.com この問題の想定解法がSparse Tableを使ったもので、ちゃんと理解したいなと思ったので忘備録的な感じで書きます。 色々調べながら書いているので、間違っているところがあったら指摘して頂けるとありがたいです。 Sparse Tableとは まず、Spa…

問題 No.390 最長の数列 - yukicoder やったこと まず最初に考えたのは「よい数列」というのはa[i] 再帰をしましたが、 計算量はO(N^2)であるので、TLEでした。 N = int(input()) x = sorted([int(i) for i in input().split()]) dp = [[-1 for j in range(N…

問題 codeforces.comいろいろ誤読や勘違いが多くてAC出来なかった 解法 この問題で出てくる頂点被覆は問題文に書いてある通りで、「あるグラフのすべての各辺について、その辺につながっている2つの頂点どちらかまたは両方の頂点を選択した頂点の集合」がグ…

問題 abc014.contest.atcoder.jp 考察 追加辺を(a,b)間につなげた場合に出来る閉路の長さ(辺の長さ)を求めるということなので、aのノードとbのノードから追加辺以外の辺を辿って最も早く合流できるノードcが分かれば、 cとaの間の長さ + cとbの間の長さ = (a…

問題 abc017.contest.atcoder.jp 考察 部分点まで自力で行けたけど、満点解法は解説を見ながら、AC。解法としてはしゃくとり法をしつつ、DPをしていく。dp[i] = i番目のサプリメントまでを見た時の摂取方法の組み合わせdp[i] := dp[i - 1] + dp[i - 2] + ...…

問題文 codeforces.comリアクティブ方式。 考察 最初は素数を使って割り切れるかどうか試していこうと思いましたが、[2,100]での素数の数が25個なので、97,89などの素数がhidden numberだと20クエリ以内に収まらない。よく考えると,エストラネスのふるい等を…

問題 abc023.contest.atcoder.jp 考察 まず解法として最初に思い浮かんだのは、その時点の高さが最大の風船を割っていく貪欲だが、 風船iと風船jがあり、H[i] S[j]であると、ある時点では風船jの方が割られる風船だが、 最終的な高さは風船iの方が高くなる可…

問題 arc055.contest.atcoder.jp 考え 本番中は全く分からなくて、解説放送をみてもあんまり理解できなかったので、 下記の解説を参考させていただきました。とてもわかりやすいです。ソースコード中に考えをまとめながらコーディングしたのでそちらを参照し…

問題 No.375 立方体のN等分 (1) - yukicoder 考え 同じ方向からN - 1枚の平面で切断するのが最大なので、TMaxはN - 1下図のA方向からの平面の切断数をa、B方向はb、C方向はｃ、とすると TMinはa + b + cの最小の値となる。 なので、aの値を全探索をして、残…

問題 abc038.contest.atcoder.jp 考え 部分点までは自力で行けたけど、満点解法は分からずで、解説などを見て通しました。主に2通りの解き方があるらしい。1つ目は公式解説であるようなセグメントツリーというデータ構造を使う方法。セグメントツリーは蟻本…

本戦で部分点取ってから何も手を付けてなかったので、解説見ながらやってみた。 問題 discovery2016-final.contest.atcoder.jp 考え 求める最小の時刻を二分探索を使って、貪欲に求めていく。 ある時刻xに選択することができる最大の美味しさを持つ料理を取…

問題文 abc005.contest.atcoder.jp 考え 一度に焼ける個数Pが、ある区画内( 最左上(y , x)で最右下(y + H,x + W)である範囲 )の焼ける場所の個数(H * W個)以上であれば、その区画内の場所をすべて使ってたこ焼きを焼くことが出来る。 まず、たこ焼きの美味し…

問題 abc003.contest.atcoder.jp 考え 部分点解法はX * Y = D + Lなので、X * Yの範囲内でD個のデスクを置く組み合わせ(X * Y)C(D)と残ったX * Y - Dの範囲内でL個のラックを置く組み合わせ (X * Y - D)C(L)を掛け、それを(R - X + 1) * (C - Y + 1)回掛けつ…