tookunn’s diary

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

Educational Codeforces Round 45

Editorial A問題 問題 考察 ソースコード B問題 問題 考察 ソースコード C問題 問題 考察 ソースコード D問題 問題 考察 ソースコード E問題 問題 考察 ソースコード F問題 問題 考察 ソースコード G問題(未解決) 問題 考察 ソースコード Editorial codeforc…

Codeforces #486 Div3

Editorial A問題 問題 考察 ソースコード B問題 問題 考察 ソースコード C問題 問題 考察 ソースコード D問題 問題 考察 ソースコード E問題 問題 考察 ソースコード F問題 問題 考察 ソースコード Editorial codeforces.com A問題 問題 codeforces.com長さ…

yukicoder long contest 1 stick xor

問題 No.5002 stick xor - yukicoder 考察 愚直にやって終わった感じでした。 愚直にやる以外は全然思いつかなかった。1ターン毎に現在の盤面から最も多く漆黒→純白に反転できる操作を盤面に適用していく。 操作対象となるセル(x,y)のx,yはランダムに決定し…

Good Bye 2017 C New Year and Curling

問題 codeforces.com半径rの円の中心のx座標がN個与えられる。 i = 0,1,2,3...N-1の順に円はy=10^100からy = 0に向かって進む。 他の円に接した時、y = 0に円が接した時に円は止まる。 最終的なN個の円のy座標を求める。 考察 i番目の円aをy=0に向かって進め…

Educational Codeforces Round 35 (Rated for Div. 2) C Three Garlands

問題 codeforces.com整数k_i(1 x_i,x_i + k_i,x_i + 2*k_i,x_i + 3*k_i...の値を選択できる。 整数x_1,x_2,x_3の値を定めた時、max(x_1,x_2,x_3)以上の整数すべてを選択できるかを判定する。 考察 ・k_i = 1が1つ以上存在するのならYES 値の差が1なので整数…

AtCoder Beginner Contest 082/AtCoder Regular Contest 087 D - FT Robot

問題 D - FT Robot 解法 x座標、y座標に分けてDP 文字列Sを連続する'T','F'で分割して考えると、x座標だけ変化する、y座標だけ変化する区間が存在することが分かる。 よって、x座標、y座標の変化は独立して考えることが出来る。 あとはdp[i個目の連続する'F'…

AtCoder Regular Contest 086 C - Not so Diverse

問題 C - Not so Diverse 解法 整数がK種類以下になるまで、個数の少ない整数から書き換えていく(整数を消していくと考えても良い)。まず、各整数ごとに個数をまとめて、次に個数で整数の種類数をまとめていく。 あとはK種類以下の整数になるまで、整数を書…

COLOCON -Colopl programming contest 2018- C - すぬけそだて――ごはん――

問題 colopl2018-qual.contest.atcoder.jp 解法 A~Bまでの整数が書かれた各カードを購入するか購入しないで全探索する。制約等から時間計算量がO(2^35)と思ってしまうが 「...これまでに食べたどのカードに書かれた整数とも互いに素である整数の書かれたカ…

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つ目のスキャナーのス…