AGC029-A解説

A - Irreversible operation

問題

A - Irreversible operation

解説

BWをWBにする操作は、Wを左に持っていく、Wを左のBと交換すると考えればよい。

あるWがあるとして、その左側にBとWからなる文字列があるとする。 すると、左側の文字列をいくら並び替えたところで、あるWから見て左であることには変わりない。 よって、あるWに対して、左側にあるBの数だけWを左のBと交換する操作が行える。これを全てのWに対して計算して和を取ればよい。

毎回あるWについて、左に何個Bがあるかを数えるのは非効率なので、最初にそれらを計算しておく。これは累積和を使って実装する。

累積和のイメージ

これで累積和配列[i]の値は最初からからi番目までのBの数になる。

これで解くことができました。一応サンプルコード。

import java.util.Scanner;

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

        String s = sc.next();
        int[] B_Count = new int[s.length() + 1];
        //累積和配列に値をセット
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == 'B') B_Count[i]++;
        }
        //累積和をとる
        for (int i = 0; i < s.length(); i++)
            B_Count[i + 1] += B_Count[i];

        long ans = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == 'W') ans += (long) B_Count[i];
        }

        System.out.println(ans);
    }
}

Java入門5

今日の目標

変数について学ぶ

変数宣言ができるようになる

準備

Code, Compile & Run | CodeChefにアクセスして、JAVAを選びます。

今までの振り返り

今までは"Hello, World"や10など、プログラム中に埋め込んだ値を出力することをしてきました。 しかし、実際には決まった動きしかしないプログラムなどほとんどありません。大抵のプログラムは計算をしたり、使用者から何か入力を受け付け、それにあった処理をしたりします。 そういった埋め込んだ値以外を扱う方法について学んでいきましょう。

変数

変数とは、プログラムの中で使うデータに名前を付けたものです。

まずはコードを書いてみよう

まずは変数を使ったコードを書いて見ましょう。 これは長方形の面積を求めるプログラムです。heightは高さ、widthは幅、areaは面積を表しています。

このコードの内容は後で解説するので、動かしてみるだけで大丈夫です。

class Codechef
{
    public static void main (String[] args) throws java.lang.Exception
    {
        int height = 10;
        int width = 15;
        int area = height * width;
        System.out.println(area);
    }
}

これを実行すると150と出力されたと思います。 ここで、heightやwidthの値を変えてもう一度実行してみましょう。 結果が変わったと思います。

では文法について見ていきましょう。

変数の宣言

変数を使うには、使う前に

「このデータの種類でこういう名前の変数を定義します」

と宣言する必要があります。これを変数宣言といいます。

変数宣言は型名 変数名;です。

型名

型とはなんでしょうか？型とは、データの種類を表すものです。

型は基本型と呼ばれる特別な型が最初から用意されています。例えば数字や文字など、どのプログラムでも必ず使うような汎用的なデータ達です。

基本型以外の型は参照型と呼ばれ、自分で定義したりすることもできます。

変数名

変数名とは、変数の名前です。これは開発者が自由に決めることができます。

変数に値を代入する

変数を宣言したことで、その変数を使うことができるようになります。変数に中身を入れるには、代入をします。

代入の文法は変数名 = 値;です。

イコール記号を使っていますが、数学のイコールと違って、右側の値を左側に入れますよ、という意味です。

一回まとめる

変数宣言　型名 変数名;

変数に値を代入する　変数名 = 値;

そしてこれらは型名 変数名 = 値と省略して書くことができます。こちらの書き方が一般的です。

ではさっき書いたコードを振り返ってみましょう。

int height = 10;
int width = 15;
int area = height * width;

この場合、上から

int型の変数heightに10を代入。int型の変数widthに15を代入。int型の変数areaにheight*widthを代入。 と読むことができます。

余談

プログラム上で使用されるなんらかのデータは、メモリ上に配置されます。プログラムの実行時にメモリを使用して、データを一時的に記憶します。

メモリはアドレス(番地番号)を使ってアクセスします。よってメモリ番地1242142番にデータを入れます！と指定してもいいのですが、それだと人間はとても把握できないですよね。なのでメモリ上の位置の代わりに変数名を使うことでデータが置いてあるメモリの番地について考える必要がないようになっています。

また、変数の型(データの種類)を変数宣言のときに決める必要があるのは、メモリ上に置かれたデータが何かわからないからです。0と1で表されたものが文字なのか数字なのかわからないと困りますよね。 更に、データのサイズがわからないとどこがデータの終わりかわかりません。 なのでデータの種類を指定してあげるわけです。

次回やること

プログラムででてきたint型とはなんでしょうか。Javaの基本型について説明していきます。

ABC115解説

はじめに

この記事は初心者向けに書かれています。また、解法への思考経路を重視して書いています。

Dの解説はありません。

A - Christmas Eve Eve Eve

問題

A - Christmas Eve Eve Eve

解法

制約よりdは22~25の4パターンしかないので、場合分けをする。 場合分けといえばif文ですね。switch文は？と思う人もいるかもしれませんが、switch文はbreak;の書き忘れでバグりやすいのと、単純にコード長が長くなるので使うべきではありません。

解法コード：Submission #3738640 - AtCoder Beginner Contest 115

別解として、"Christmas"に" Eve"を25-d回後ろに足してもよい。

B - Christmas Eve Eve

問題

B - Christmas Eve Eve

解法

問題を要約するに、一番高い品物は半額、それ以外の品物は定価、ということですね。 求めるものはその総額。

ここで、A,B,C,D,E円の品物があって、Cが一番高い品物とします。 答えをA+B+C/2+D+Eとしてもいいのですが、式変形を用いてA+B+C+D+E-C/2とすると解きやすくなります。

式を変形するのは競プロでよくあることです。 (今回はコードが書きやすくなるだけの恩恵ですが...)

また、2で割るときに奇数でないかを確認することも大事です。 この問題では全ての商品の値段は2の倍数となっているので問題ありませんね。

コード例

import java.util.Arrays;
import java.util.Scanner;

public class B {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        System.out.println(Arrays.stream(arr).sum() - Arrays.stream(arr).max().getAsInt() / 2);
    }
}

C - Christmas Eve

問題

C - Christmas Eve

解法

問題は最大値と最小値の差を最小化することなので、選ぶK個はどれも近い高さのほうができるだけ小さくできそうです。

また、選んだK個の木から最大値と最小値を高速に求めることができれば楽ですね。 何故なら問題で最小化しようとしているのはN個からK個選んだときの、最大値と最小値の差で、それ以外の木の高さは全く関係ありません。

よって木の列を始めにソートしてやります。 ちなみに、ソートといえば一般には昇順ソート(小さい方から大きい方へ並べる)を言います。

int n = sc.nextInt(), k = sc.nextInt();
long[] h = new long[n];
for (int i = 0; i < n; i++) h[i] = sc.nextLong();
Arrays.sort(h);

どれも近い高さのK個を選ぶとは、ソート済みの配列から連続してK個を見るということになります。 また、昇順ソートされているので最小値は見る区間の始めの数、最大値は見る区間の最後の数になります。

では、実装していきましょう。実装上の注意をあげます。

最小値の記録

最小値をどうやって記録するかというと、まず絶対にありえない大きさの数字で答えの変数(今回は変数名ansとする)を初期化します。

long ans = Long.MAX_VALUE;//2^63-1で初期化

次に、答えになりうる値とansを比べて、答えになりうる値のほうが小さいなら、ansを答えになり得る値で上書きします。

これはif文で書いてもいいのですが、こう書くこともできます。

ans = Math.min(ans, value);

if文と比べるとすっきりとする一方、上書きされたかがわかりません。 それがif文との使い分のポイントです。

最終的なコードはこちら

import java.util.Arrays;
import java.util.Scanner;

public class C {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), k = sc.nextInt();
        long[] h = new long[n];
        for (int i = 0; i < n; i++) h[i] = sc.nextLong();
        Arrays.sort(h);
        
        long ans = Long.MAX_VALUE;
        for (int i = 0; i < n - k + 1; i++) {
            ans = Math.min(ans, h[i + k - 1] - h[i]);
        }
        System.out.println(ans);
    }
}

ループ回数についてですが、N個のうち、K個を含む区間はN-K+1通りあります。最後の+1を忘れないようにしましょう。

h[i]が見ている区間の最小値、h[i+k-1]が見ている区間の最大値です。

Java入門4

今日の目標

プログラムの基本構造について知る。

人にとって読みやすいコードを書くことを知る。

準備

いつものように Code, Compile & Run | CodeChef にアクセスして、JAVAを選びましょう。

プログラムの構造

Java入門2でプログラムを書いている中で、気づいたことがあると思います。

以下のコードは毎回書く必要があること。そして、自分たちが命令を書いていくのは真ん中の部分だけだということです。

/* package codechef; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
    public static void main (String[] args) throws java.lang.Exception
    {
        // ここが命令を書くところ
    }
}

Javaのソースコードには波括弧{...}で囲われた部分が多く出てきます。 波括弧で囲われた部分をブロックといいます。

外側のブロックをクラスブロック、内側のブロックをメソッドブロックと呼びます。

class Codechef
{
    //この中がクラスブロック
}

public static void main (String[] args) throws java.lang.Exception
{
    //この中がメソッドブロック
}

Javaのソースコードは必ずこの二重構造を持っています。

私たちがコンピューターに対する命令を記述していくのはメソッドブロックの中となります。 その外側に関しては毎回書くお決まりのパターンですが、どんなプログラムでも全く同じでいいというわけではありません。 それについて説明します。

クラス名

public classの後に書かれる文字は、このプログラムの名前を指定するものでクラス名といいます。 クラス名は大文字のアルファベットで始まる名前を付けるのが一般的です。

クラス名は重要です。なぜならJavaには以下のようなルールがあるからです。

Javaのソースコードを記述したファイルを保存するとき、ファイル名は「クラス名.java」にしなければならない。

今皆さんはweb上でJavaを試しているため、これらのことを考える必要はありません。 いずれ自分のコンピューターでプログラムを書く際には、ファイル名とクラス名を一致させるというルールを忘れないようにしましょう。

正確に記述する

プログラミングにおいて大事なことの一つ目は「正確に記述する」ということです。

• 基本的に半角で記述する。大文字小文字の違いも意識する。
• オー(o,O)とゼロ(0)、エル(l)とイチ(1)、コロン(:)とセミコロン(;)、ピリオド(.)とカンマ(,)を間違えない。
• 括弧((), {}, [])や引用符(', ")の種類を間違えない。

これらは初心者がよく犯すミスなので気を付けましょう。プログラムは一文字違うだけで動かなかったり大きく動作が変わってしまいます。

public static void main(String[] args) {...}をスラスラ書けるようになりましょう。読み方はパブリック・スターティック・ボイド・メイン・ストリング[] argsです。

外から内へ

次に大事なのは、プログラムは上から下へではなく、外から内へ書く、という意識です。

はじめにこう書くと、中身を一生懸命書いている内に、}を閉じ忘れることが多々あります。

class Codechef
{
    public static void main (String[] args) throws java.lang.Exception
    {
        //ここを一生懸命書くと、}で閉じるのを忘れる。いくつ閉じればいいのかわからなくなる。

このミスを減らすため、括弧を開くとまず閉じる。それから中身を書く。という順でプログラムを書きましょう。

インデント

Javaでは文法上、キーワード間にどれだけ空白や改行を入れてもいいことになっています。 よって、こういったコードも書くことができます。

class Codechef{public static void main (String[] args) throws java.lang.Exception{System.out.println("Hello, World!");}}

しかし、これではプログラムの構造を把握することは難しいです。適切な場所で空白や改行を入れるようにしましょう。特にブロックの始まりから終わりで字下げをしてください。 この字下げの事をインデントといいます。

class Codechef
{
■■■public static void main (String[] args) throws java.lang.Exception
■■■{
■■■■■■//インデントでは、タブ文字を使います。TABキーで入力できます。
■■■■■■//一階層ごとにTAB一文字を使いましょう。
■■■■■■//この例では、黒四角3つ分をTAB文字1つとして読んでください。
■■■■■■//他の言語では、空白4つを使うこともありますが、JavaではTABが一般的です。
■■■}
}

コメント

今までも沢山ソースコード上にでてきましたが、説明しておきます。 ソースコードをより読みやすくするために、ソースコードの中に解説、注釈文を書き入れることができます。これをコメントといいます。 コメントはコンパイル、実行時両方で無視されます。人が読むためだけのものです。

Javaではコメントの書き方が2種類あります。

単一行コメント

//から行末まではコメントになります。

複数行コメント

/*
この間は全てコメントになる。
何行コメントを書いてもOK。
*/

終わりに

今回の記事は長くて疲れたかと思います。次回からはどんどんコーディングしていきます。今はイメージできなかったりわからないところは次回以降をするうちに自然にわかるようになるとおもいます。

Java入門3

今日の目標

プログラミングにおいて汎用的に使う用語について知る。

今回学ぶ用語はどれも非常に重要です。

開発の流れ

Javaでの開発の流れを示します。

1. ソースコードの作成
2. コンパイル
3. 実行

では、詳しく解説していきます。

ソースコードの作成

Javaの文法に従ってプログラムを書いていきます。 人が読める状態のプログラムをソースコードといいます。

コンパイル

私たちが書いたソースコードは、そのままではコンピュータの心臓であるCPUは理解できません。 そのため、CPUがわかる形式に変換してやる必要があります。この作業をコンパイルといいます。

CPUはマシン語と呼ばれる言葉で書かれたプログラムしか理解できないのです。

そこでいきなりソースコードからマシン語に変換しても良いのですが、Javaではまず、バイトコードと呼ばれる形式に変換を行います。 この変換をするソフトフェアのことをコンパイラといいます。

また、コンパイルする際にソースコードの文法チェックが行われます。

実行

無事にコンパイルに成功すれば、次はインタプリタと呼ばれるソフトフェアに実行を指示します。

インタプリタは内部にJVM(Java Virtual Machine)という仕組みをもっており、バイトコードを少しずつ読みながらマシン語へと翻訳してCPUに送ります。

まとめ

私たちが書いたソースコードはコンパイラによってバイトコードにコンパイルされる。 バイトコードはインタプリタの内部のJVMによって少しずつ読みながらマシン語に変換されて実行される。

ソースコードが2回の変換を通している。 ソースコードはバイトコードに一気に変換されるが、バイトコードはマシン語に変換されながら実行されるという違いがある。

余談

Java入門2にてCode, Compile & Run | CodeChefを使ったときはこれらのことを考えず、ソースコードを書いてRUNを押せば実行できました。 しかし、このサイトの裏では私たちの書いたソースコードがコンパイルされ、JVMによって実行されています。

Java入門2

今日の目標

まず簡単なコードを書いて動かしてみて、プログラミングの雰囲気を掴みます。 コードの内容を理解する必要はありません。

準備

Code, Compile & Run | CodeChefにアクセスして、JAVAを選びます。 最初は画像のような画面が出ていると思います。

私たちは主に、//your code goes hereと書かれた部分の下に自分のコードを書いていく形になります。 ちなみに、//以降は消してしまって大丈夫です。

さっそくプログラミング

まずはSystem.out.println("Hello, World!");と入力してみます。しかし、これをそのまま全て打つのは頭が悪いです。

始めに、printlnと入力してみましょう。きっと下の画像のように候補を出してくれていると思います。

自分の入力したい候補がでてきたら、キーボードのTABキーを押しましょう。すると候補の一番上を選択したことになり、自動で入力されることでしょう。 もし入力したい候補が一番上にない場合は矢印キーで候補を上下に動かしてからTABキーを押しましょう。 これらの一連の動作はプログラミングでよく使うので使いこなしましょう。

この時点でコードはこのようになっているはずです。

System.out.println();

次に、()の間に"を入力してください。これはShift+2で入力できます。

すると、もう一つの「"」も自動で入力されたかと思います。これが補完機能です。

最後に、""の間にHello, World!と入力すれば完成です。

こうなっていればOKです。System.out.println("Hello, World!");

動かす

サイト右下のRUNボタンを押してしばらく待ちましょう。 少し経つと下にHello, World!と表示できれば成功です。

動かないときは

プログラムには文法が存在します。間違ったコードを書いた場合、エラーメッセージがでます。 何行目のどこがダメなのか、勿論英語ですが、そう難しくはないのでしっかり読みましょう。

間違った原因とエラーメッセージを関連付けて覚えましょう。次に同じ間違えをしたときに一瞬で解決できるようになります。 これがプログラミング上達に一番大事なところと言えるでしょう。

ここから、初心者が間違えやすいポイントを挙げていきます。

• プログラムの行の最後に;(セミコロンと読みます)が抜けている。
• 括弧の対応が取れていない。(や{と)や}は必ずセットで存在しています。

改造

System.out.println("Hello, World!");と書いて「Hello, World!」と表示されたということは...わかりますね？ 次は自分の好きな言葉を出力してみてください！

どんどんいくぞ

/* package codechef; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
    public static void main (String[] args) throws java.lang.Exception
    {
        System.out.println("Hello, World!");
        
        System.out.println("28 + 50");
        System.out.println(28 + 50);
        
        System.out.println(5 * 10);
        
        int x;
        x = 8;
        System.out.println(x * x * 3.14);
    }
}

このプログラムを写して実行してみましょう。コピペは使わずにやってみてください。

Java入門1

ようこそ

これからプログラミング初心者を対象に、Javaでのプログラミング入門をする記事です。

Javaの環境構築

プログラミングをするには、プログラミングに必要な実行環境と開発環境をパソコンに入れて、設定をする必要があります。

ただ、これは初心者には難しく、また、権限がないパソコン(学校のパソコンなど)に設定することはできません。自分のパソコンを持っていない人のために、オンラインでプログラミングをして、書いたプログラムを実行するサイトがあるので、しばらくはそれを使います。

Code, Compile & Run | CodeChefにアクセスして、ポップアップにJAVAと入力して、選択してください。

このサイトは入力の補完機能があるため、長いコードを一々全て打つ必要がなく、とてもプログラミングがしやすいのでオススメです。 最初に入力されているコードは気にしなくて大丈夫です。