tookunn’s diary

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

AtCoderBeginnerContest 050 D

問題 abc050.contest.atcoder.jp解説見て通しました。 考察 これ以下の記述は自分が公式解説放送見ながら書いたメモみたいなものです。・(は問題文での) ・(は問題文での) 以上の式がある。 (aのiビット目)と(bのiビット目)に注目して考えると、とを入れ替え…

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…

Codingame Fantastic Bitsに参加

Codingameというサイトで行われた「Fantastic Bits」というコンテストに参加しました。今回、事実上初めて長期間コンテストに出た && これから長期間コンテストに出始めようかなと思った ので参加した内容を記録した方が良いと思い、軽く記事にします。ちな…

yukicoder No443 GCD of Permutation

問題 No.443 GCD of Permutation - yukicoder 考察 まず愚直に整数の各桁を並べ替えて出来る整数の集合を列挙することは制約から無理ということが分かる。ここから公式解説の解法について考える(自分に向けての補足)yukicoder Sに含まれる整数"xxxxab"と"xxx…

POJ 1328 Radar Installation

POJ

問題 1328 -- Radar Installation蟻本の練習問題埋めの一環として取り組んだ。 制約書いてないのがあったりして混乱したので解説記事をみて通した。 幾何的要素が若干あったので、色々理解するのに時間がかかった。 考察 レーダーの適用範囲を円とし、その円…

CODE FESTIVAL 2016 qual B D

問題 code-festival-2016-qualb.contest.atcoder.jp 考察 本番中は貪欲っぽいな思って、色々考察して試して時間切れを迎えた。どういう発想で解法に近づくのかを記録しておく。・問題概要から数列Aのある要素はその要素の前の要素によって操作が変わる?だか…

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した値…

SRM 699 Div2 Hard

SRM

問題文 TopCoder Statistics - Problem Statement 考察 ・であり、の時,]から]に辿ることが出来るということは]と]の最小公倍数になる整数の頂点を通るということ。 ・最小公倍数は以下である。 ソースコード import java.util.*; public class FromToDivisi…

CODE FESTIVAL 2016 予選A D

問題 code-festival-2016-quala.contest.atcoder.jp 考察 まず問題文にある式がどういうものかを考えてみる。 (左上の整数) + (右下の整数) = (右上の整数) + (左下の整数)を と考える。 そしてこの式を変形すると, または となる。 この変形した式が表すの…

Codeforces #372 Div2 A~C

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

AtCoderBeginnerContest 044 D

ABC

問題 abc044.contest.atcoder.jp 考察 解説見てAC。・bを探索したいが,全探索をしてしまうと最大になってとなり、間に合わない。・ここでの場合にnをb進数で表現すると2桁以下になることに気付くととの範囲に分けてbを探索できることに気付ける。・nをb進数…

競技プログラミングTODO#1

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

会津大学競技プログラミング合宿2016参加記

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

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…

yukicoder No420 mod2漸化式

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

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が含まれているような最小の終点を分かれば良さそう。・尺取り法を使うっぽい。・問題ページのサンプ…

AtCoder Grand Contest 001 C Shorten Diameter

AGC

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