AtCoder Beginner Contest (ABC) 106 を解いてみた
AtCoder Beginner Contest (ABC) 106 の解法ログです。
問題文はAtCoder公式からどうぞ。
注:ソースコードの変数と解法中の文字は無関係です
A - Garden
解法
算数の問題にこういうのありましたね。道の重なりに注意。
ソースコード
int main(void) { int a, b; cin >> a >> b; cout << a * b - a - b + 1 << endl; return 0; }
B - 105
解法
Nが小さいので、N以下の数で割ったあまりを全て見ていけばOK。
余り0になる場合が8つあるなら、その数は約数を8個持つ。
ソースコード
int main(void) { int n; cin >> n; int result = 0; for (int i = 1; i <= n; i += 2) { int count = 0; for (int j = 1; j <= i; j++) { if (i % j == 0) count++; } if (count == 8) result++; } cout << result << endl; return 0; }
C - To Infinity
解法
1<=n<=K
文字目に1以外の文字が存在する場合、5000兆日経つと、たとえK=10^18
でも1以外の文字がKの場所に到達する(指数関数は一瞬で膨れ上がるので)。
そうでない場合は5000兆日経ってもK文字目は1のまま。
K文字目まで1が続くのなら1を、そうでないなら最初に出現した1以外の文字を出力する。
ソースコード
int main(void) { std::string s; int64_t k; cin >> s; cin >> k; for (int i = 0; i < k; i++) { if (s[i] != '1') { cout << s[i] << endl; return 0; } } cout << '1' << endl; return 0; }
D - AtCoder Express 2
解法
愚直に解く場合、『クエリ(p,q)
に対して、「全列車に対しp<=L,R<=q
であるかを調べる」』という解法を思いつける。計算量はO(Q*M)
なので間に合わない。
都市の数が少ないことに着目すると、train[L][R]=LからRに向かう電車の数
という配列を作ることができそう。この配列を利用して「p<=L,R<=q
を満たす場所を足していく」という解法を思いつける。計算量はO(QN^2)
。……計算量増えてるじゃーん!!
しかし、「p<=L,R<=q
を満たす場所を足していく」処理は累積和を利用することでO(N)
に落とせる。ということで、先程の配列から累積和を作ってクエリに答えればAC。
ソースコード
(printf/scanfで書いてます)
int main(void) { int n, m, q; cin >> n >> m >> q; int train[501][501] = {}; int cum[501][501] = {}; int m1, m2; for (int i = 0; i < m; i++) { scanf("%d%d", &m1, &m2); train[m1][m2]++; } for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { cum[i][j] = cum[i][j - 1] + train[i][j]; } } int a, b; int answer; for (int i = 0; i < q; i++) { answer = 0; scanf("%d%d", &a, &b); for (int j = a; j <= b; j++) { answer += cum[j][b]; } printf("%d\n", answer); } return 0; }
その他
37分全完やったぜ。