ぱーぽーの競プロ記

競技プログラミングに関することを書きます。

CODE FESTIVAL 2014 予選B D 登山家

概要ある山脈にN個の山小屋が東西に一直線に並んでいる。それぞれの山小屋は標高H[i]に建てられている。それぞれの山小屋から東西を見渡したときに、何個の山小屋が見えるか求めたい。山小屋が見える条件は以下の通り。 現在の山小屋をi、見たい山小屋をjと…

Donutsプロコンチャレンジ2015 C 行列のできるドーナツ屋

概要N人が一列に並んでいて、それぞれの身長H[i]である。自分より前に何人見えるのかを知りたい。”見える”とは、以下の条件を満たす場合のことをいう。 自分がi番目に並んでいてj番目の人が見えるとき、j&lti 自分とj番目の人(身長H[j])の間にj番目の人より…

TopCoder SRM 633 Div2 Easy : Target

概要 ##### # # # # # # # ##### ######### # # # ##### # # # # # # # # # # # # # # # ##### # # # #########↑みたいな感じのを出力せよ。というSRMではあんまり見ない感じの問題。解法 やるだけ問題。しかしどう実装するか悩んだ挙句、クソコードを書いて…

TopCoder SRM 627 Div2 Hard : BubbleSortWithReversals

概要 数列Aが与えられる。 同じ要素が被らないように連続する要素をK回まで反転することができる。例えば、 A = {3, 2, 1, 5, 4}, K = 2のとき、 {3, 2, 1}と{5, 4}を選んで反転させると{1, 2, 3}と{4, 5}となり、数列Aは、A = {1, 2, 3, 4, 5}となる。この…

TopCoder SRM 626 Div1 Easy : FixedDiceGameDiv1

問題概要 1~bの値が書いてあるb面サイコロをa個持っているAさんと、1~dの値が書いてあるd面サイコロをc個持っているBさんがいる。二人がそれぞれ持っているサイコロを全て振って出た目の合計を比べるとき、AさんがBさんより大きい値になる期待値を求める問題…

KUPC 2014 D ハミング

概要 問題文はこちら http://kupc2014.contest.atcoder.jp/tasks/kupc2014_d解法 数学できないマンだったので、しめじたんの記事を参考にさせていただきました。(分かりやすい、神) http://d.hatena.ne.jp/simezi_tan/20140710/1404932438文字列s1とs2が与え…

KUPC 2014 C 占い

概要 問題文はこちら http://kupc2014.contest.atcoder.jp/tasks/kupc2014_c解法 「同じ数字である」という関係を「同じ根を持つ集合」と捉える。その集合を扱うのにUnionFindTreeを用いる。違う集合に属している場合はそれらをマージする。最後にマージした…

TopCoder Open 2014 Round 2B easy : SwitchingGame

解法・感想など 本番で解けなかったやつ。自分の中では分かったつもりですが、うまく文章にできてないのでご了承下さい。ライトのオンオフがどちらでもよい"?"の処理が重要である。Twitterでのアドバイスや他の人のコードを参考にしながら、状態数が2つ(ラ…

ARC #023 C タコヤ木

概要 問題文はこちら http://arc023.contest.atcoder.jp/tasks/arc023_3解法 (他の記事を参考にしながら解いた。説明に間違いがあるかもしれない)例えば入力で 1 -1 -1 3 が与えられた場合、単調増加な数列になるのは ・1 1 1 3 ・1 1 2 3 ・1 1 3 3 ・1 2…

ARC #022 C ロミオとジュリエット

概要 問題文はこちら http://arc022.contest.atcoder.jp/tasks/arc022_3コンテスト中に満点解法で解くことが出来なかった。解法 木の直径を求めることでこの問題を解くことができます。やり方はとても簡単でDFSを2回やればよいです。具体的なやり方は以下の…

StrongPrimePower (SRM400 div1 easy)

解法・感想など nが入力で与えられたとき、n=p^qを満たすp、qを求める問題です。 nは10^18以下の自然数、pは素数です。n (p=2,q=60のとき、2^60 > 10^18 となる) n=p^qを変形し、p=n^(1/q)とします。 qの範囲はすでに分かっているので、先ほど変形した式に代…

AOJ 1325 Ginkgo Numbers

概要 問題文はこちら http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1325 解法 この問題ではガウス整数を扱っていることが分かります。 http://ja.wikipedia.org/wiki/%E3%82%AC%E3%82%A6%E3%82%B9%E6%95%B4%E6%95%B0#.E3.82.AC.E3.82.A6.E3.82…

FiveHundredEleven (SRM511 div2 hard)

解法・感想など Editorial見ました。こういうゲーム理論の問題は自力ではまだ解けないですね、勉強しないと。 (ズラズラと書いていくので、日本語おかしいところがあるかもしれません。)このゲームでの勝敗条件は以下の通りです。 ・自分の番で引くカードが…

FauxPalindromes (SRM564 div2 easy)

解法・感想など 与えられた文字列に対してまず普通の回文かどうか調べます。 もし回文ではなければ、重複する文字を削除した文字列を生成し、また回文かどうか調べればよいです。他の記事を拝見したところ、下のソースコードよりはるかに簡単に実装していた…

AOJ 2182 Eleven Lover

概要 問題文はこちら http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=218280000桁以下の数字(文字列)が与えられます。 その中で11の倍数である部分文字列の個数を求める問題です。 解法 動的計画法(DP)で求めることができます。int dp[(左から見…

AOJ 1503 Number

概要 問題文はこちら http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1503 解法 この問題は全く解法が思いつかなかったので、nanikakaさんやその他の記事を参考にしました。感謝です。どうやら記事によると、 「(n + 1)! + 2, (n + 1)! + 3, (n …

ARC #010 C 積み上げパズル

概要 問題文はこちら http://arc010.contest.atcoder.jp/tasks/arc010_31次元のパズル的なやつがあって高得点狙いましょう!みたいな問題です。 (問題文が読みやすいのでそちらを参考にしてください) 解法 動的計画法(DP)で解くことができます。まずこの…

AOJ 0574 Nails

概要 問題文はこちら http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0574釘にいくつかの輪ゴムをひっかけて三角形を作ります。 1本以上の輪ゴムに囲まれた釘の本数を求める問題です。2 3 1 5 解法 想定解はおそらく動的計画法(DP)でしょうが、…

RedAndGreen (SRM521 div2 easy)

解法・感想など 1WA食らってしまったので反省。区間を定めて全探索です、その左側をRに右側をGにします。 間違っても一つ一つシミュレーションしてはいけない。 ソースコード class RedAndGreen { public: int minPaints(string row) { int ans = INF; int…

Codeforces 236B Easy Number Challenge

概要 問題文はこちら http://codeforces.com/problemset/problem/236/B 解法 素数判定・約数の個数判定がきちんとできていれば解ける問題です。・素数判定について 私はエラトステネスの篩を用いて求めました。蟻本にも載っているので参考にしてみてはいかが…

AOJ 1092 Make KND So Fat

概要 問題文はこちら http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1092 解法 動的計画法(DP)で解くことができます。この問題では2回動的計画法をします。(1回の動的計画法だけでも解を求めることはできるかもしれませんが、私は2回に分け…

EllysXors (SRM543 div2 medium)

解法・感想など 自力では解けなかったので他の方々の記事を参考にしました、感謝。この問題はLからRまでのxorを解くという問題ですが、やることは「1からNまでのxorを求めることができるか」ということになります。なぜそういえるのか? → 打ち消しあう…

AOJ 2026 Divisor is the Conqueror

概要 問題文はこちら http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2026N枚のカードを持っています。 そのカードをある条件に従って一枚ずつ場に出し、N枚全てのカードを場に出すことができるかを判定する問題です。ある条件についてですが…

StrIIRec (SRM545 div2 medium)

解法・感想など この問題は全然解法が分からなかったので、いろいろな方の記事を参考にして解きました。【問題概要】 文字列(abcdef...)(n文字ある)を並び替えてある条件に合うような文字列を求める問題。 ある条件は以下の通り。 ・minStrよりも辞書順で大…

AOJ 1268 Cubic Eight-Puzzle

概要 問題文はこちら http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1268図3(問題文を見てください)のようなサイコロが8つあり、それが図4のように並べられています。 サイコロを転がして入力で与えられるような目的の形にするまでの最短…

AOJ 2419 Acrophobia

概要 問題文はこちら http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2419フィールドに散らばっている巻物を全て集めてゴールに行くまでにかかる最短距離を求める問題です。 解法 幅優先探索(BFS)で解くことができます。この問題は探索する前ま…

AOJ 2049 Headstrong Student

概要 問題文はこちら http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2049循環小数に関する問題です。 x / y の割り算(x 解法 筆算で計算するのと同じようなことをループを回しながらやればよいです。 ここで重要となる考え方があり、それを「鳩…

AOJ 0225 Kobutanukitsuneko

問題文はこちら http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0225 ・概要 複数の文字列が与えられる。 それらをしりとりのような感じで全部繋げ、かつ最初の文字列の先頭と最後の文字列の後尾を繋げることができるか(オイラー閉路が存在する…

AOJ 2008 Dragon Fantasy

問題文はこちら↓ http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2008 ・概要 勇者が各地に散らばったクリスタルを全部集めて、そのクリスタルの力で魔王を倒します。クリスタルを全部集められるかどうかを調べる問題です。 問題文が日本語なの…

AOJ 1076 Time Manipulation

問題文はこちら↓ http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1076 ・概要 問題文が日本語なので省略。 ・解法 ・パターン① 包除原理を用います。この問題は蟻本や他の方々のコードを参考にしながら解きました。ベン図が奇数個重なってる時は…