ferinの競プロ帳

競プロについてのメモ

2017-12-30から1日間の記事一覧

ABC084 D - 2017-like Number

問題ページ D - 2017-like Number 考えたこと f(A) = (1からAのうち条件を満たす数) とすれば f(r) - f(l-1) として計算できるのでf(A)を前計算する 10^5までの素数をエラトステネスの篩で列挙して、条件を満たす数を1~10^5までで探せばよさそう 条件を満た…

ABC084 C - Special Trains

問題ページ C - Special Trains 考えたこと 乗れる電車のうち一番はやい電車に貪欲に乗っていけばよさそう t秒目に駅に来た時 s + k*f >= t を満たす最小のkの電車に乗ればいい 変形すると k >= (t-s)/f k = max(0, ceil*1と決定できるのであとは貪欲にえい …

AtCoder Regular Contest 007 C - 節約生活

問題ページ C: 節約生活 - AtCoder Regular Contest 007 | AtCoder 考えたこと 愚直に全探索するとO(N^N)になりそう 多少枝刈りできそうだし10^10なら通るのでは?と思って投げるとTLEじゃなくてWA 全てのテレビが付くまでは視聴できない時間が合ってもいい…

ARC005 C - 器物損壊!高橋君

問題ページ C - 器物損壊!高橋君 考えたこと N回見た拡張dijkstra d[y][x][何回壊したか] = (最短距離) でdijkstraをする #include <bits/stdc++.h> using namespace std; typedef long long ll; #define int ll typedef vector<int> VI; typedef vector<VI> VVI; #define FOR(i, a,</vi></int></bits/stdc++.h>…

ARC004 C - 平均値太郎の憂鬱 ( The melancholy of Taro Heikinchi )

問題ページ C - 平均値太郎の憂鬱 ( The melancholy of Taro Heikinchi ) 考えたこと 数式を書いてみると X/Y = (N(N+1)/2 - M) / N N = Y/2, M = (Y^2+2Y-4X)/8 N,Mが整数かつN < Mの条件を満たすような(X, Y)の組を探す N<Mの条件を満たす間(X, Y) (2X, 2Y) (3X, 3Y) … について探索していく これで出すとTLEしたのでMがマイナスになる部分を枝刈りする (kY)^2 + 2kY - 4kX > 0 を満たすように整数kを選ぶ k =</mの条件を満たす間(x,>…