山傘のプログラミング勉強日記

プログラミングに関する日記とどうでもよい雑記からなるブログです。

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();
    }
}

C - Modulo Summation

入出力例がなかったら解けなかったでしょうね。

正直、解説みればすぐにわかると思うので、まあ、書かなくていいか。

感想

ほぼ毎日勉強してるんですが、こんなものかとガックリ来ました。

C問題までは正解できたんですが、解けたのではなく当たったという感じで情けないです。まあ、調べて正解を見つけた問題も今までにいくつもあったので、平常運転ですかね。