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

hamayanhamayan's blog

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

直線状の点 [パソコン甲子園2018 予選 I]

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0388 考察過程 1. 制約を見るとN^2はいけるので、2点を結ぶ全ての直線は列挙できる 2. ここからK個以上の同じ点が同じ直線上に存在することを判定できないか考える 3. 同じ直線状にあるなら…

タクシー [パソコン甲子園2018 予選 H]

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0387 考察過程 1. タクシーはタクシー乗り場を後ろにしか移動できないので、後ろのタクシーから客を確定させていく 2. どの客を乗せればいいかだけを決めれば、どのタクシーがどの客を乗せ…

ワープ装置 [パソコン甲子園2018 予選 G]

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0386 考察過程 1. mod10^9+7なのでDP数え上げ感がある 2. dpをまず考えるが、制約を見ると「dp[i] := 星iにたどり着く組み合わせ数」っぽい 3. 更新はそれより前の星の今いる出口と同じ文字…

ボゾソート [パソコン甲子園2018 予選 F]

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0385 考察過程 1. 愚直にシミュレートして行けば良さそう 2. そのためには昇順になったかを高速に判定する必要がある 3. Aを昇順にしたものと同じ場所になった個数を数えればいい? 4. 同じ…

デュードニー数 [パソコン甲子園2018 予選 E]

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0384 考察過程 1. 点数に比べて問題設定が難しい 2. とりあえず全探索対象を探そう 3. y+aを全探索すれば、10^4が最大なので、全探索できるっぽい 解法 https://onlinejudge.u-aizu.ac.jp/s…

熱中症対策 [パソコン甲子園2018 予選 D]

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0383 考察過程 1. まだ難しくなる段階じゃない 2. 何か全探索する対象を探す 3. 1リットルを買う個数を全探索し、足りない分を500ミリリットル買うことにする 解法 https://onlinejudge.u-a…

ケーキパーティー [パソコン甲子園2018 予選 C]

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0382 解法 https://onlinejudge.u-aizu.ac.jp/status/users/hamayanhamayan/submissions/1/0382/judge/3162071/C++14持ってきたケーキを1つにまとめて、再分配することを考える。 自分を入…

赤とんぼ [パソコン甲子園2018 予選 B]

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0381 解法 https://onlinejudge.u-aizu.ac.jp/status/users/hamayanhamayan/submissions/1/0381/judge/3162047/C++142つの数の差を取ればいい。 条件分岐を使っても良いし、abs関数で絶対値…

摂氏華氏 [パソコン甲子園2018 予選 A]

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0380 解法 https://onlinejudge.u-aizu.ac.jp/status/users/hamayanhamayan/submissions/1/0380/judge/3162045/C++14計算式通りにCを計算する。 実装問題。 int F; //---------------------…

力持ち [パソコン甲子園2014 予選 I]

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0303?year=2014 前提知識 区間DP 解法 https://onlinejudge.u-aizu.ac.jp/status/users/hamayanhamayan/submissions/1/0303/judge/3162012/C++14二段階でDPして解く。 まず、区間DPをする。…

Tr/ee [AtCoder Regular Contest 103 E]

https://beta.atcoder.jp/contests/arc103/tasks/arc103_c 考察過程 1. 実験してみると、作れる最低条件が3つ見つかる 2. 「S[0]は1」「S[N-1]は0」「Sの[0,N-2]は回分になっている」 3. これ以外なら作れると仮定して考える 4. 1なら普通に辺を伸ばせば大丈…

平らな農地 [yukicoder No.738]

https://yukicoder.me/problems/no/738 考察過程 1. かかるコストはマンハッタン距離になっている 2. 定石「マンハッタン距離の総和を最小化したいときは中央値を使う」 3. K個連続した要素を全探索して、すべて中央値にしたときのコストの最小値が答え 4. …

PopCount [yukicoder No.737]

https://yukicoder.me/problems/no/737 前提知識 https://www.hamayanhamayan.com/entry/2017/04/23/212728title=桁DP 考察過程 1. まず目につくのがpopcountの組み合わせ数の少なさである 2. 60通りくらいしかないので、問題を言い換えることができそう 3. …

約比 [yukicoder No.736]

https://yukicoder.me/problems/no/736 前提知識 最大公約数 解法 https://yukicoder.me/submissions/288497既約分数にする場合を考えると、分母分子の最大公約数で割ると、既約分数にできる。 同様にそれ以上約日できないものにするために、全ての要素の最…

接線 [yukicoder No.735]

https://yukicoder.me/problems/no/735 解法 https://yukicoder.me/submissions/288494三平方の定理をする。 ∠OLA=90°になりため、求めたい長さをxとするとx^2=d^2-r^2となる。 よって、x=sqrt(d^2-r^2)が答え。 平方根を取るには、C++ではsqrtを使う。 doub…

Careful Engineer [yukicoder No.734]

https://yukicoder.me/problems/no/734 解法 https://yukicoder.me/submissions/288493プログラムを書くべきXが満たす条件は以下の通りである。 (手作業でかかる時間)≧(プログラムでかかる時間) A*60*X ≧ B*X+C*60*60 (A*60-B)*X ≧ C*60*60 ここで(A*60-…

/\/\/\/ [AtCoder Beginner Contest 111 / AtCoder Regular Contest 103 C]

https://beta.atcoder.jp/contests/arc103/tasks/arc103_a 考察過程 1. 条件を言い換えると、偶数番目と奇数番目をそれぞれ同じ数にしたい 2. ただし、数列に現れる数はちょうど2種類なので、全て同じ数というのはダメ(コーナーケースになりそう) 3. 偶数…