tookunn’s diary

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

SRM719 Div2 Hard

SRM

問題 TopCoder Statistics - Problem Statement 考察 根ノードから任意のノードまでのパスのXORの計算を行う。xor[V] = 根ノードから任意のノードVまでのXORそうすると任意のノードVから他の任意のノードUまでのパスのXORの計算結果は xor[V] ^ xor[U]になる…

AtCoder Regular Contest 079 D Decrease (Contestant ver.)

ARC

問題 arc079.contest.atcoder.jp 考察 ・公式解説 Editorial - AtCoder Regular Contest 079 | AtCoder公式解説見ながらソースコード中に考えたこと書きました。実験して解法につながる性質とか規則性見つけるの難しい。 こういう問題に出くわしたらどうする…

yukicoder No514 宝探し3

問題 http://yukicoder.me/problems/no/514 考察 座標と座標のマンハッタン距離はである。(とする) そこで、座標と座標のマンハッタン距離を考える。(y座標を求めるためにx座標を0に固定する) すると、となり、と出来る。これでは求まった。 あとはとな…

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どちらかに一意に…

SRM 708 Div2 Hard

SRM

問題 https://community.topcoder.com/stat?c=problem_statement&pm=14536 考察 うーん。これ思いつく発想ってどうやるんだろ。「X[i]を決めた時のiより左、右に分けた時の左側、右側それぞれの文字列が左右対称であることを思いつく」 ことかなぁ@tookunn_1…

AtCoderBeginnerContest 054 D

ABC

問題 abc054.contest.atcoder.jp 考察 薬品を買うか買わないかの2通り,その選択をN回行う 通り 通りの買い方の中から,比がになる薬品の買い方を見ていく。そして、その買い方の中で最小の予算を求める 番目の薬品までを見た時,タイプの総量が,タイプの総量が…

最大流 蟻本読んだメモ

参考にした資料: 蟻本第2版 P188~P191 ネットワークフロー入門 http://hos.ac/slides/20150319_flow.pdf 最大流問題 始点Sから終点Tまで各辺の容量を超えることなく流すことが出来る最大の流量を求める。 定義 有向グラフ,頂点の集合,辺の集合 始点,終点 …

RUCP2016 Day3 D Complex Oracle - Complex Oracle -

問題 http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=RitsCamp16Day3&pid=D考察にめちゃくちゃ時間を奪われたので,もっと考察する時間を短縮させたい。 考察 は, 全体で番目の値より大きい値の数が分かれば,番目の値がこの数列の中で何番目に…

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…

RUCP2016 Day3 C 成長する点 - Growing Point -

問題 http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=RitsCamp16Day3&pid=C割と問題文通りにやるだけなのだけど、幾何っぽいというのもあって方針は合ってるが実装のバグが取れないのが辛かった 考察 一番最初に拠点0と最も近い餌との間に直線…

RUCP2016 Day3 B 周期数列 - Periodic Sequence -

問題 http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=RitsCamp16Day3&pid=B 考察 考えられる周期tをそれぞれ試していくだけN = ktから,tはNを割り切る数なのでそこまで多くない ソースコード import java.io.IOException; import java.io.Inpu…

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…

RUPC2016 Day3 A マイナンバー - My Number -

問題 http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=RitsCamp16Day3&pid=Aこれは当時本番で解いたのでそこまで苦労しないで解けた感(実装は時間掛かった) 考察 ?のところに0~9までの数字を当てはめて実際にそのマイナンバーでチェックディジ…

RUPC2016 Day2 G Max Pig Noodle

問題 http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=RitsCamp16Day2&pid=G誤読というか,交換人と交換しなくていいパターンあるの読み取れなくて苦戦したが,自力で解けたので良かった。 考察 当初,N人の交換人との交換をどの順番に行っていく…

RUPC2016 Day2 D Courage Test

問題 http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=RitsCamp16Day2&pid=D 考察 まず,頂点uと頂点vから同じ回数しか移動できないので,Nが奇数の場合はNoになる。次は,頂点uと頂点vそれぞれから各頂点の最短距離を記憶しておく。ダイクストラ…

RUPC2016 Day2 C ABNN is 17 years old forever

問題 http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=RitsCamp16Day2&pid=C当時は結構苦戦してたけど,今やるとUnionFindの練習ぐらいに感じる... 考察 村の合併をUnionFindで表現して,合併するごとにrankを増加させていき,最終的にrankが1の時…

RUPC2016 Day2 B SEARIGHT LIVE FES

問題 http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=RitsCamp16Day2&pid=B 考察 外側の角の部分から上,横,下に分けて考える。外側の人がa番目に存在する 内側の人がb番目に存在する以上を前提とすると 外側の人が上(W-1番目まで)に存在する場…

RUPC2016 Day2 A Gossip

問題 http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=RitsCamp16Day2&pid=A 考察 が答え。 つまり最初に情報を持っているアイドルの間隔を2で割った値の最大値が解だが,アイドル1とアイドルNがそれぞれ情報持っているアイドルの中で一番間隔が…

RUPC2016 Day1 F リレー / Relay

問題 http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=RitsCamp16Day1&pid=F解説見て通しました。 考察 基本的には公式解説にある通りの考え方で何となく理解しましたが,オイラーツアーを行う実装がイメージできなかったので,mayokoさんの解説…

RUPC2016 Day1 E 28

問題 http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=RitsCamp16Day1&pid=E 考察 良い整数は各桁に,2または8しか現れないのでまでの正整数はそこまで多くない。 なので、考えられる良い整数はすべて生成しておき、を割り切ることが出来る良い…

RUPC2016 Day1 D スキャナー / Scanner

問題 http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=RitsCamp16Day1&pid=D解説記事見てしまった。 考察 当初、貪欲に時間のかかる紙から選んで、早くスキャンが終わっているスキャナーに振り分けた。が、通らなかった。3つ目のスキャナーのス…

RUPC2016 Day1 C 足し算掛け算 / AddMul

問題 http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=RitsCamp16Day1&pid=C 考察 出現するアルファベットの数を、1~9までの出来るだけ大きい数を括弧でくくれるようにカウントする。を文字列Sの中に回出現するアルファベットの数とする。 も…

RUPC2016 Day1 B ハミング距離 / Hamming Distance

問題 http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=RitsCamp16Day1&pid=B 考察 ハミング距離がである値の中で最大のものを求めなければならないので、を左から見ていき,'0'である文字を個'1'に変える。 もし、'0'である文字が個に満たない場…

RUPC2016 Day1 A 秤 / Steelyard

問題 http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=RitsCamp16Day1&pid=A 考察 吊らされたおもりと対称的におもりを吊っていく。 具体的にはに同じ重さのおもりを吊っていく。 ソースコード import java.io.IOException; import java.io.Inp…

AtCoderBeginnerContest 010 D 浮気予防

問題 abc010.contest.atcoder.jp解説見て蟻本写経して通しました。 考察 当初、複数のを含む連結成分を探して,橋を見つけてそれを消していけば良いのかなぐらいに考えてたけど、そこから何も分からなかったので解説を見て最大フローを求める問題と分かった。…

AtCoderBeginnerContest 021 D 多重ループ

ABC

問題 abc021.contest.atcoder.jp過去問埋めで久々のABC D問題の自力AC 考察 という性質から,内の複数のの間で重複した値が許されるということが分かる。これは結局,までの範囲の数値から個の数値を重複を許し,取り出すことと同じ。例えば,までの範囲の数値か…

第3回 ドワンゴからの挑戦状 予選 B ニコニコレベル

問題 dwacon2017-prelims.contest.atcoder.jp 考察 文字列を左から順に見ていき,'2','5','?'の時で場合分けして状態を遷移する。 2の場合 i番目の文字が2である状態からi+1番目の文字が5である状態に遷移する 5の場合 i番目の文字が5である状態からi+1番目の…

AtCoderRegularContest 065 F シャッフル / Shuffling

問題 arc065.contest.atcoder.jpさすがF問題ということで解説見て,解説放送見て,他の方の提出コードを見て,時間をかけてやっと理解(完全ではない)出来ました。復習必須に感じたのでメモとして記事にします。 考察 まず、まとめられるはまとめていく。 まとめ…

AtCoderGrandContest 005 B

AGC

問題文 agc005.contest.atcoder.jp解説見ました。 考察 愚直に個の区間ごとに最小値を計算しても計算量がになるのでTLEになる。ここで最小値になる値に注目して区間を考える。具体的な例として問題文の入力例2で考える。 i0123 a1324 の値を見ると最小値がに…

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を消費していく。・そして、す…