AtCoder振り返り(Beginner Contest 164)

AC

今回は3完でした。4問目が解けそうで解けず、、、
ただ3問は12分で解くことが出来たので地力は上がっている印象です。

成績

個別のコンテスト結果は以下の通りです。
パフォーマンスだけで見れば茶色上位相当ですね。緑パフォーマンスを出すには4問目以降も解けないとだめですね。

全体の成績は以下の通りです。
パフォーマンスがそこそこ高かったのでRatingも上がりました。後3回くらいチャレンジすれば茶色にはなれるでしょうか？

問題

問題1

atcoder.jp

引数Sと引数Wの比較処理を行う問題です。
if分岐が書ければ解けますね。

回答コード

import java.util.Scanner;
 
public class Main {
	public static void main(String[] args) {
		try (Scanner scn = new Scanner(System.in)) {
			int S = scn.nextInt();
			int W = scn.nextInt();
 
			if(S > W) {
				System.out.println("safe");
			} else {
				System.out.println("unsafe");
			}
		}
	}
}

問題2

atcoder.jp

引数 A, B, C, D が渡されます。
A, B：先行
C, D：後攻
なので、順番にC - BとA - Dを繰り返して先に0になったほうが勝ちです。という簡単なロジックです。
処理順番(C- Bが先) を間違えないことと、繰り返し処理が分かれば難しくはないです。
ただ私の回答は無駄が多く繰り返し処理は不要です。実際はもっと簡単に求めることができ除算を用いればO(1)で計算できます。

回答コード

import java.util.Scanner;
 
public class Main {
	public static void main(String[] args) {
		try (Scanner scn = new Scanner(System.in)) {
			int A = scn.nextInt();
			int B = scn.nextInt();
			int C = scn.nextInt();
			int D = scn.nextInt();
 
			int result = 0;
			while(true) {
				C = C - B;
				if(C < 1) {
					result = 0;
					break;
				}
				A = A - D;
				if(A < 1) {
					result = 1;
					break;
				}
			}
 
			if(result == 0) {
				System.out.println("Yes");
			} else {
				System.out.println("No");
			}
		}
	}
}

問題3

atcoder.jp

最大10^5の数だけ文字列が引数と渡され、重複を除き何種類あるか調べる機能
Map機能を使えば簡単に求められました。地味にMapの初期化方法忘れてました。

回答コード

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
 
public class Main {
	public static void main(String[] args) {
		try (Scanner scn = new Scanner(System.in)) {
			int N = scn.nextInt();
 
			String[] kuji = new String[N];
 
			Map<String, Integer> map = new HashMap();
			String key;
			int cnt;
			for(int i = 0; i < N; i++) {
				key = scn.next();
				map.put(key, 0);
			}
 
			System.out.println(map.size());
		}
	}
}

問題4

atcoder.jp
解けそうで解けなかった問題です。

最大20万桁の1から9になる文字列から2019の倍数をもとめるもんだいです。
20万×20万の2重ループは違うよなーとか
2019は素因数分解すると3 × 673になるけど何か意味あるのかな？とか色々考えていたのですが思いつきませんでした。

公式の解説ですが、最初と2020/4/27 18:00時点では内容が訂正されています。
「2019 は 2 でも 5 でも割り切れないので、mod2019 では 10 に逆元が存在します」という文言が消えてますね。

これ過去158のEとほぼ同じ問題らしいですね。自分にはまだ無理だ。。。
自分の中で理解できたこととしては、
「2019と10の最大公約数は1（互いに素である）ため、
10^x*n が2019で割り切れる場合 nも2019であるといえる。」という点ですね。

2019で各余りをmapでカウントしていって
最後に二項係数で求めるらしいのですがちょっとまだ難しいので勉強しておきます。。。

解答

import java.util.Scanner;

class Main{
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();

        Integer max_len = s.length();
        int[] n_mod = new int[max_len+1];
        int[] map2019 = new int[2019];
        int pow = 1;
        for(int i=max_len-1;i>=0;i--){
            Integer num = Integer.valueOf(s.substring(i, i+1));
            Integer tmp = (num*pow + n_mod[i+1])%2019;
            n_mod[i] = tmp;
            map2019[tmp]+=1;
            pow *= 10;
            pow %= 2019;
        }

        Long count = (long)map2019[0];
        for(int i=0;i<2019;i++){
            Integer num = map2019[i];
            if(num<2)continue;
            count += num*(num-1)/2;
        }
        System.out.println(count);
    }
}

解説
https://img.atcoder.jp/abc164/editorial.pdf