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

hamayanhamayan's blog

2018-09-17から1日間の記事一覧

部活動調査 [パソコン甲子園2015 予選 G]

競技プログラミング

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0321?year=2015 前提知識 UnionFind 考察過程 1. 矛盾が発生するのは、ある生徒が2つ以上の部活動に属している可能性がある場合 2. a,bが同じ部活動に属しているということは、同じグループ…

品質管理 [パソコン甲子園2015 予選 F]

競技プログラミング

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0320?year=2015 考察仮定 1. 差分を考えていく問題であるが、差分だけを再計算することで判定できないか考える 2. 現在の状態を打ち消して、更新して、現在の状態を考えなおすという典型テ…

プログラミングコンテスト [パソコン甲子園2015 予選 E]

競技プログラミング

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0319?year=2015 考察仮定 1. 答えのAを全探索できるのでは？ 2. できる 解法 https://onlinejudge.u-aizu.ac.jp/status/users/hamayanhamayan/submissions/1/0319/judge/3140675/C++14答え…

極秘調査 [パソコン甲子園2015 予選 D]

競技プログラミング

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0318?year=2015 考察仮定 1. 問題のベン図を見ながら高校数学のように数えやすい物をつかって表現する 2. すると答えはn(C) - n(A∧C) + n(A∧B∧C)となる 3. これを各々数えて、計算すると答…

カエルはまっすぐ帰る [パソコン甲子園2015 予選 C]

競技プログラミング

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0317?year=2015 考察仮定 1. 貪欲に行けそうか考えると、流石にいけそう 2. 最適戦略を考えるとなるべく大ジャンプを使うほうがよくて、使えなくなったら小ジャンプ 3. DPでも解ける制約に…

魚釣り競争 [パソコン甲子園2015 予選 B]

競技プログラミング

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0316?year=2015 解法 https://onlinejudge.u-aizu.ac.jp/status/users/hamayanhamayan/submissions/1/0316/judge/3140614/C++14実装をする。 イワナをh1匹、ヤマメをh2匹釣った場合の合計点…

参加者数 [パソコン甲子園2015 予選 A]

競技プログラミング

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0315 解法 https://onlinejudge.u-aizu.ac.jp/status/users/hamayanhamayan/submissions/1/0315/judge/3140590/C++14実装問題。 総和を答える。 int P, M, C; //--------------------------…

プログラミングコンテスト II [パソコン甲子園2016 予選 I]

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0343?year=2016 前提知識 二分探索 BIT 座標圧縮 考察過程 1. （平衝二分木でset作れば一発っぽいが…） 2. （パソコン甲子園で平衝二分木実装して通したらかっこいい） 3. クエリ先読みして…

競技プログラミングにおける最小全域木問題まとめ [MST, プリム, クラスカル, ブルーフカ]

未整理記事 最小全域木 辺に重みが付いている無向グラフが与えられて、ここからいくつかの辺を選んで木を作るとき、重みの総和の最小値は？という問い アルゴリズムは3種類ある 解説 プリム法 O(V^2) or O(ElogV) ある頂点を始点として、頂点を1つずつ増やし…

村の道路計画 [パソコン甲子園2016 予選 H]

競技プログラミング

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0342?year=2016 前提知識 凸包 最小全域木（実際には少し違うけど）のクラスカル法 UnionFind（最小全域木の構築で使用） 考察過程 1. 「幾何っぽさ」「村を構成するどの2つの集落を結んだ…

繰り返す呪文 [パソコン甲子園2016 予選 G]

競技プログラミング

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0341?year=2016 前提知識 動的計画法 考察過程 1. 典型問題として覚えてしまっているので、考察過程がなかった 2. 文字列の添字を持つDPを作る 3. 10^9+7での数え上げ、制約もどちらのindex…

パンケーキ [パソコン甲子園2016 予選 F]

競技プログラミング

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0340?year=2016 前提知識 動的計画法 （想定解では貪欲で解けるので、必要不可欠ではない） 考察過程 1. pの上限が小さいのが気になる 2. 裏返しの操作は順番が逆になっても結果が変わらな…

形状データ処理 [パソコン甲子園2016 予選 E]

競技プログラミング

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0339?year=2016 考察過程 1. 集合として見た時に同様のものがあれば消すことができる 2. 集合として等しい判定をするにはいろいろな方法があるので、好きな方法を使おう 解法 https://onlin…

ニュータウン [パソコン甲子園2016 予選 D]

競技プログラミング

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0338?year=2016 考察過程 1. 一見厄介そうな問題に見える 2. 問題を簡単にしているのが「全て同じ大きさの正方形」で埋めるという部分 3. とりあえず何かを全探索する方針で考えるが、正方…

日本の暦 [パソコン甲子園2016 予選 C]

競技プログラミング

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0337?year=2016 解法 https://onlinejudge.u-aizu.ac.jp/solutions/problem/0337/review/3140004/hamayanhamayan/C++14実装問題。 なるべく簡単に実装できるように実装方針をまず考えよう。…

日の出と日の入り [パソコン甲子園2016 予選 B]

競技プログラミング

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0336?year=2016 解法 https://onlinejudge.u-aizu.ac.jp/solutions/problem/0336/review/3139998/hamayanhamayan/C++14境界となる「日の出または日の入り」を考えてみる。 すると、H=-Rのと…

ワード [パソコン甲子園2016 予選 A]

競技プログラミング

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0335?year=2016 解法 https://onlinejudge.u-aizu.ac.jp/solutions/problem/0335/review/3137179/hamayanhamayan/C++14実装問題。 int W; //---------------------------------------------…