はまやんはまやんはまやん

hamayanhamayan's blog

2018-03-01から1ヶ月間の記事一覧

エレベータ [RUPC2018 Day1 G]

https://onlinejudge.u-aizu.ac.jp/beta/room.html#RitsCamp18Day1/problems/G

Censored String [RUPC2018 Day3 G]

前提知識 Aho-Corasick 解法 https://onlinejudge.u-aizu.ac.jp/beta/review.html#RitsCamp18Day3/2753249以下の解法は自信がないです。 ACできたので書いているだけです。 貪欲法で解く。 先頭から順番に文字を見ていって、この文字を消さないとPに含まれる…

Ebi-chan Lengthens Shortest Paths [RUPC2018 Day3 F]

前提知識 ワーシャルフロイド 最大流問題 解法 https://onlinejudge.u-aizu.ac.jp/beta/review.html#RitsCamp18Day3/2753218まず、長さを増やすかもしれない辺を考えてみると、これは最短路に含まれうる辺だけである。 それ以外の辺は最短距離に関係しない。…

Broccoli or Cauliflower [RUPC2018 Day3 E]

前提知識 オイラーツアー 遅延評価セグメントツリー(区間xor1区間総和) 解法 https://onlinejudge.u-aizu.ac.jp/beta/review.html#RitsCamp18Day3/2753110部分木にまつわるクエリなので、オイラーツアーとセグメントツリーを使ういつものやつかなと想像す…

The Diversity of Prime Factorization [RUPC2018 Day3 D]

解法 https://onlinejudge.u-aizu.ac.jp/beta/review.html#RitsCamp18Day3/2753033DPで解く。 前から順番にpとするかeとするかを決めていくのだが、それぞれ条件がある A[i]をpにするには (前回のp)<A[i] A[i]が素数 A[i]をeにするには 直前の要素がeでない…

AA Graph [RUPC2018 Day3 C]

前提知識 ワーシャルフロイド 解法 https://onlinejudge.u-aizu.ac.jp/beta/review.html#RitsCamp18Day3/2752946この問題は二段階で解いていく 「グラフから辺情報を抽出する」「ワーシャルフロイドで最短距離を求める」 後半はワーシャルフロイドを知ってい…

Hierarchical Calculator [RUPC2018 Day3 B]

解法 https://onlinejudge.u-aizu.ac.jp/beta/review.html#RitsCamp18Day3/2752876数が5種類しか無いのでそれぞれ考えてみる。 A[i]=0は0になってしまうので使わない A[i]=1は数が変わらないので使わない A[i]=2は数が大きくなるので絶対使う これらは分かり…

Many Kinds of Apples [RUPC2018 Day3 A]

解法 https://onlinejudge.u-aizu.ac.jp/beta/review.html#RitsCamp18Day3/2752843玉を入れる出すをシミュレートしよう。 特に注意するべき所も無いが、処理の途中で結果がわかったら終了するようなタイプのやつは、答える関数を別にしておくと、returnで答…

Ghost Legs [RUPC2018 Day2 F]

解法 https://onlinejudge.u-aizu.ac.jp/beta/review.html#RitsCamp18Day2/2751511あみだくじはよく「順列から順列への写像」と考えることができる。 今回は縦線が3本なので、3!=6通りの順列の中での写像関数としてイメージできる。 各あみだくじにおいて、…

Ball [RUPC2018 Day2 C]

解法 https://onlinejudge.u-aizu.ac.jp/beta/review.html#RitsCamp18Day2/2751424まず個数Mは無視して、価値を最大化するようにボールを取ってみよう。 すると、各色について価値の大きい順に取れるだけボールを取れば最適となる。 元の問題で使われるボー…

OOllOll [RUPC2018 Day2 B]

解法 https://onlinejudge.u-aizu.ac.jp/beta/review.html#RitsCamp18Day2/27513921が多いほど答えに近いと言える。 そのため、全て1の数の中からN以下の最大数が答えになる。 全て1の数は全てで30個くらいしか無いので、全探索して答え。 int N; //--------…

ai1333 [RUPC2018 Day2 A]

解法 https://onlinejudge.u-aizu.ac.jp/beta/review.html#RitsCamp18Day2/2751381Xを100で割ると追加すべき3の個数が分かるので、それを末尾に加えて答える。 int X; //---------------------------------------------------------------------------------…

Grid Components [AtCoder Regular Contest 093 D]

https://beta.atcoder.jp/contests/arc093/tasks/arc093_b

Traveling Plan [AtCoder Regular Contest 093 C]

https://beta.atcoder.jp/contests/arc093/tasks/arc093_a

Sad powers [Codeforces Round #471 (Div. 2) C]

http://codeforces.com/contest/955/problem/CQ個のクエリに答えよ。 「x=[L,R]の範囲で整数a,pでx=a^pかつa>0,p>1と表現できる数の個数を答えよ」

Not simply beatiful strings [Codeforces Round #471 (Div. 2) B]

http://codeforces.com/contest/955/problem/B文字列Sがある。 これを2つのadorableな文字列に分割できるか判定せよ(連続する文字列で分割しなくてもよい)。 adorableな文字列とは「2種類の文字で構成される文字列」のこと。

log は定数 [yukicoder No.670]

https://yukicoder.me/problems/no/670

対決!!! 飲み比べ [yukicoder No.669]

https://yukicoder.me/problems/no/669

6.0*10^23 [yukicoder No.668]

https://yukicoder.me/problems/no/668

Mice's Luck(ネズミ達の運) [yukicoder No.667]

https://yukicoder.me/problems/no/667

1000000007で割るだけ [yukicoder No.666]

https://yukicoder.me/problems/no/666

Two Sequences [AtCoder Regular Contest 092 D]

https://beta.atcoder.jp/contests/arc092/tasks/arc092_b

2D Plane 2N Points [AtCoder Regular Contest 092 C]

https://beta.atcoder.jp/contests/arc092/tasks/arc092_a

Two Colors Card Game [AtCoder Beginner Contest 091 B]

https://beta.atcoder.jp/contests/abc091/tasks/abc091_b

Two Coins [AtCoder Beginner Contest 091 A]

https://beta.atcoder.jp/contests/abc091/tasks/abc091_a

TreesAndBrackets [SRM731 Div1 Easy]

https://community.topcoder.com/stat?c=problem_statement&pm=14836括弧列で表現された2つの木t1とt2がある。 t1から葉を削除する操作を0回以上行って木t2に出来るか判定せよ。 木の子供の順序は変えられない。

Russian Dolls Ways [CSAcademy #73 D]

https://csacademy.com/contest/round-73/task/russian-dolls-ways/N個のマトリョーシカ人形がある。 i番目の人形のサイズはA[i]である。 サイズがA[i]<A[j]であればj番目の中にi番目の人形を入れられる。 複数入れ子もOK 適切に入れて最終的な人形を少なく…

Binary Isomorphism [CSAcademy #73 C]

https://csacademy.com/contest/round-73/task/binary-isomorphism/(問題の意味が完全に理解できなかったけど、多分) 2つの根付き木が与えられるので同型判定せよ。

Ricocheting Balls [CSAcademy #73 B]

https://csacademy.com/contest/round-73/task/ricocheting-balls/N個のボールがある。 i番目のボールの高さはH[i]mである。 このボールは下に1m/秒で落ちるが、地面に到着したら上に1m/秒の速さで上がっていく。 ある秒数でボールを止めたときの、高さの総…

Three Equal [CSAcademy #73 A]

https://csacademy.com/contest/round-73/task/three-equal/N要素の0~2の配列Aがある。 これに「A[i] = ((A[i] + 1) % 3)」という操作を行い、全ての要素を等しくしたい。 最低何回必要か。