ぱーぽーの競プロ記

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

その他コンテスト

CODE THANKS FESTIVAL 2014 A日程 G : 通勤電車と気分

概要電車には1~Kの番号が付けられたK個の座席が一列に並んでおり、N人がこれらの座席に座ることを考える。人は以下の2種類の座席の選び方のどちらかによって座る座席を選ぶ。 「とにかく座りたい気分」:空席の中で最も番号が小さいものを選ぶ。 「余裕があ…

CODE FESTIVAL 2014 予選B D 登山家

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

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

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

KUPC 2014 F テレパシー

概要 問題文はこちら http://kupc2014.contest.atcoder.jp/tasks/kupc2014_fキツネを強化するゲーム。解法 木DPで解くことができ、 dp[i][j] := i番目のキツネの力がj以上のときの最小コスト となる。(しめじ先生の記事や他の方の解答をチラ見して木DPがど…

KUPC 2014 D ハミング

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

KUPC 2014 J カード

概要 問題文はこちら http://kupc2014.contest.atcoder.jp/tasks/kupc2014_j解法 動的計画法で解くことができる。dp[日にち][カードの所持数]=持っているお金の最大値ソースコード #include <bits/stdc++.h> #define REP(i, x, n) for(int i = x; i < (int)(n); i++) #defi</bits/stdc++.h>…

KUPC 2014 C 占い

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

KUPC 2014 B 数当てゲーム

概要 問題文はこちら http://kupc2014.contest.atcoder.jp/tasks/kupc2014_b解法 KUPCではお馴染みな感じの問題。 (しかしこのような問題は初めて解いたのでやり方に若干戸惑った。)あらかじめ素数表を作っておく。1回目のループで求めたい値の約数を列挙し…

KUPC 2014 A マッサージチェア

概要 問題文はこちら http://kupc2014.contest.atcoder.jp/tasks/kupc2014_a解法 ソートして差分を足し合わせる。ソースコード #include <bits/stdc++.h> using namespace std; #define REP(i, x, n) for(int i = x; i < (int)(n); i++) #define rep(i, n) REP(i, 0, n) #de</bits/stdc++.h>…