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

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

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

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

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…

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

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つにまとめて、再分配することを考える。 自分を入…

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関数で絶対値…

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; //---------------------…

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をする。…

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なら普通に辺を伸ばせば大丈…

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

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

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

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…

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-…

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

https://beta.atcoder.jp/contests/abc111/tasks/abc111_b 解法 https://beta.atcoder.jp/contests/abc111/submissions/3304064xを全探索して、すべての桁の数が同じ最小の数を出力すればいい。 すべての桁の数が同じ数の条件は111の倍数であることである。 …

https://beta.atcoder.jp/contests/abc111/tasks/abc111_a 解法 https://beta.atcoder.jp/contests/abc111/submissions/33040201を9に、9を1に変換するが、これは文字列的な操作である。 なので、Nを取得するときはstringで取って、処理するのがオススメ。 s…

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0302?year=2014 考察過程 1. 何を全探索すれば効率良く計算ができるかを考える 2. bの範囲の下限を全探索すると、明るさが[b,b+d]である頂点のx座標の最大最小、y座標の最大最小が高速に求…

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0301?year=2014 前提知識 双方向リスト 考察過程 1. 制約として、aが小さいのが気になる 2. Maを考えると10^5*10^2=10^7なので簡単な計算なら間に合いそう 3. 隣に渡していって、1つ削除が…

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0300?year=2014 考察過程 1. 操作がやばいので、操作の実装以外はそんなに難しくないのでは？ 2. よく見ると最大8回で揃うようなので、操作は7回まで見ればいい（7回操作してできなかったら…

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0299?year=2014 考察過程 0. （似たような問題を今まで見たことありすぎて考察過程になってるか分からん） 1. 最適戦略を考えよう 2. 引き返す回数は最大1回でいいし、店に行く途中で引き返…

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0298?year=2014 考察過程 1. 時間と分のセットで扱うのは面倒なので、全て分に直そう（典型の考え方） 2. あとは、1つにまとめてソートして出力すればいい 3. 重複している部分はuniqueを使…

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0297?year=2014 考察過程 1. 効率よく計算できそうな見た目もしている 2. が、制約を見るとシミュレーションしても大丈夫 3. しよう 解法 https://onlinejudge.u-aizu.ac.jp/status/users/h…

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0296?year=2014 考察過程 1. 合計丁度1000円が作れるかを判定すればいい 2. 簡単な判定方法を探す 3. 大きい硬貨をなるべく使って1000円に近い金額を作ろうとすればいいのでは？ 解法 https…

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0295 解法 https://onlinejudge.u-aizu.ac.jp/status/users/hamayanhamayan/submissions/1/0295/judge/3156095/C++14実装問題。 D×Cが答えなので、これを答えよう。 int D, C; //----------…

https://onlinejudge.u-aizu.ac.jp/beta/room.html#ACPC2018Day2/problems/F 考察過程 1. まず面倒なt+ceil(b/(t+a))について考えてみると、tについて下に凸の関数になっている 2. ダイクストラかな？ 3. 三分探索すれば、いつまで待てばいいかわかりそう 4.…

http://codeforces.com/contest/1053/problem/BN要素の数列Aがある。 この数列の連続部分列のうち、以下の条件を満たすものが何通りあるか。 条件 各要素で、1が立っているビットを自由に動かして数を作ったとき、 その数すべてのXORを取って0にすることがで…

http://codeforces.com/contest/1053/problem/Ax座標が[0,N]の間、y座標が[0,M]の間にある異なる格子点を3つとって、面積をNM/Kにせよ。 存在しないならNO 考察過程 1. K=2の時に最大で、(0,0), (0,M), (N,0)の三角形 2. 例えばK=3を作りたいときは、この面…