読者です 読者をやめる 読者になる 読者になる

tookunn’s diary

主に競技プログラミング関係

Codeforces

Codeforces #397 Div1+Div2 D Artsem and Saunders

問題 codeforces.com 考察 多分これは,与えられた2つの式 から、式を変形して考察を進めれば良いのかな?@tookunn_1213 この単射ではないっていうのはh(a) = h(b)の場合,h(a) = h(b) = Aとして、g(h(a)) = a,g(h(b)) = bで,g(A) = a,bはaかbどちらかに一意に…

Codeforces #395 Div2 A~C

A問題 問題 codeforces.com 考察 周期Nと周期Mが重なる数をカウントするEditorialを見ると,Z / lcm(N,M)が解になるらしい。 ソースコード import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.NoSuchEle…

Codeforces #389 Div2 A~C

@tookunn_1213 pic.twitter.com/SHGWcrMwJV— tookunn (@tookunn_1213) 2017年1月6日 問題 codeforces.com 考察 rとdを導出する式を見つけ出すのに結構時間掛かってしまった RかLかは偶奇を見ればよい ソースコード import java.io.IOException; import java.…

Codeforces #388 Div2 A~C

Codeforces Round #388 (Div. 2)B問題,二次元座標上に平行四辺形を作る問題で,三点が与えられて残りの一つの点の候補を上げていく問題だったけど全然分からなかった。C問題,submitデバッグしたら通った感じ#tookunnVirtual pic.twitter.com/669qgq7q9M— took…

Codeforce #384 Div2 A~C

問題 codeforces.com ・Hackされた 考察 ・0か1しかない。 ・なので、AとBが同じcompanyを示すなら0,そうでない場合は0と1は必ず隣接するため1になる ソースコード import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; im…

Codeforces AIM Tech Round Div2 C

問題 codeforces.com 考察 入力としてどの頂点がどの頂点つながっているかを与えられる。頂点xと頂点yがつながっているということは頂点xと頂点yに対応する文字が隣接しているということ。逆に頂点xと頂点yがつながっていないということは必ずその2つの頂点…

Codeforces #348 Div2 C

問題 codeforces.com 考察 問題を誤読していて,サンプルが合わなくて辛かった。僕が行った解法としては愚直に与えらたクエリを実行して,指定された行,列の中の要素をシフトし,与えられた値を格納していく。そして、すべてのクエリを実行し終わったら,逆から…

Codeforces #371 Div2 A~C

A 問題 codeforces.com 考察 ・区間[l1,r1],区間[l2,r2]を数直線上で考えて、[l1,r1]と[l2,r2]の位置関係でそれぞれ場合分けして, [l1,r1]と[l2,r2]間でかさなっている区間の長さ + 1が解になる。 ・kが重なっている区間内に存在する場合は長さから-1した値…

Codeforces #372 Div2 A~C

A 問題 codeforces.com 考察 を順に見ていき,カウントしていく。 との差がより大きければカウントをリセットする。 ソースコード import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.NoSuchElementExce…

Codeforces AIM Tech Round3 Div2 D

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

Codeforces #369 Div2 A~C

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…

Codeforces 370 Div2 A~C

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

Codeforce #350 Div2 D1,D2

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

Codeforces #343 Div2 C

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

Codeforces #336 Div2 C

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

Codeforces #352 Div2 C

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

Codeforces #355 Div2 C

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

Codeforces #358 Div2 C

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

Codeforces #349 Div2 A~C

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

Codeforces #366 Div2 A~C

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

Codeforces #341 Div2 C

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

Codeforces Educational Round 10 C

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

Codeforces #360 Div2 C

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

Codeforces #356 Div2 C

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

Codeforces #341 Div2 B

問題 codeforces.com 1000×1000のマスにN個のビショップが置かれている。 2つのビショップ同士が互いに斜め方向に位置する場合、お互いを攻撃し合う。 この互いに攻撃し合う組み合わせを数える。 ここで、マスの列は左から右へ、行は上から下に、1から1000ま…

Codeforces Educational Round2 B

問題 codeforces.com 配列aと配列bの長さnとmが与えられ、整数型の配列aとbが与えられる。 0 解法 配列aをソートして、各b[i]ごとに配列aに対して二分探索を行って、b[i]と同じ値がある場合は b[i]と同じ値の中で一番要素番号が大きいもの + 1、無い場合はb[…

Codeforces Educational Round2 A

問題 codeforces.com aからzまでの文字(大文字も含む)と1から9までの数字と「,」(カンマ)「.」(コロン)「;」(セミコロン)を含む文字列が与えられる。 与えられた文字列をカンマまたはセミコロンで区切り、数字として表されるものと それ以外のものに分けてカ…

Codeforces #333 Div2 A

問題 codeforces.combx進数で表された値Xとby進数で表された値Yが与えられるので、 値としてXとYは等しいか等しくないかを求める。等しくない場合はXとYがどちらが大きいか小さいかを求める。 XとYが等しい場合は "=" Xの方が大きい場合は ">" Yの方が大きい…

Codeforces #320 Div2 D

問題 http://codeforces.com/contest/579/problem/D 整数N,K,XそしてN個の整数Aが与えられる。 N個の整数Aのうち、一つの整数A[i](1 そして残りのN-1個の整数とA[i]をOR演算した場合の最大値を求める。 解法 全探索だと間に合わなかったので、A[0]からA[N - …