AtCoder Beginner Contest 103 の感想 - ヤマカサのプログラミング勉強日記

問題

Tasks - AtCoder Beginner Contest 103

C問題まで解くことができましたが、C問題は内容をよく理解せずに解答したので、本質的に解けたのはB問題だけでした。

A問題は全数探索してしまいました。(´・ω・`)

A - Task Scheduling Problem

最初、配列をソートして、最大値を一番最初に完了させて、後は昇順に完了させると思ったんですが、全く違いました。

多分、一般化すると、

$f(a) = |a_2 - a_1| + |a_3 - a_2 | + \cdots + |a_n - a_{n - 1} |$

を最小化する $a_i$ の選び方を考える問題だと思います。ん？なんか見たことあるような気がします。と思ったけど、あれは答えが中央値になるやつでしたな。

この問題が解けたらまた記事にしようと思いました。

www.yamakasa.net

B - String Rotation

文字列の回転ってなんなんすか？なんなんすか？と問題を理解するのに時間がかかりました。

最初解いたときは回転ってなんだよ？と思いあんまり考えずに、SとTを構成する文字が同じならば「Yes」と思ったんですがそうではないようです。なので、問題文をもう一度読み直し、「回転」の処理を実際に実装することで正解となりました。

回転する回数は最大でも文字列の長さであり、元の文字列に戻ったらそれ以降は調べる必要はありません。

コード

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Scanner;

public class ProblemB {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        String S = scan.next();
        String T = scan.next();
        scan.close();
        if(S.equals(T)) {
            System.out.println("Yes");
            System.exit(0);
        }

        String []t = new String[S.length()];
        Deque<String> q1 = new ArrayDeque<String>();

        for(int i = 0; i < S.length(); i++) {
            t[i] = T.substring(i, i + 1);
            q1.addLast(S.substring(i, i + 1));
        }

        int flag = 1;
        for(int i = 0; i < S.length(); i++) {
            flag = 1;
            String te = q1.pollLast();
            q1.addFirst(te);
            //disp(q1);
            int index = 0;
            for(String s1 : q1) {
                if(!s1.equals(t[index])) {
                    flag = 0;
                    break;
                }
                index ++;
            }
            if(flag == 1) {
                System.out.println("Yes");
                System.exit(0);
            }

        }

        System.out.println("No");
    }
    static void disp(Deque<String> q1) {
        for(String s : q1) {
            System.out.print(s);
        }
        System.out.println();
    }
}