AtCoderで茶色になったから書いた記事

はじめに

入茶記事を書いている人を見かけて自分も書いた方が良いかなと思って書きました。
茶色になったのは一ヶ月半程前なので、曖昧なところもありますが、それなりに思い出しながら書きます。誰かが「あぁ、こんなやつでも茶色になれるんだな」と思って競プロを始めるきっかけになったらいいなぁと思ってます。

入茶したとき

入茶したのはABC245 (2022/3/26)のときでした(401というギリギリのレートでした)。

それまでコンテストには計6回参加していたので、まぁ自分の実力を考えれば良い方なんじゃないかなと感じています。自惚れかもしれませんが。
ちなみに、画像からもわかる通り、次のコンテストで灰色に戻りました。
(10回目のコンテストでまた茶色に戻ったからヨシ！)

一応の自己紹介

その辺にいる大学生です。
情報系の大学とかではないので(化学を主に学んでます)、ほとんど趣味でプログラミングに触れています。今はJavaをメインにやっていますが、大学一年生のときはずっとPowerShellで遊んでました。BigIntとかデカい数字で遊ぶの楽しいもんね。しょうがない。ちなみにC++、Pythonは読めなくはないですが書けません。

Javaに触れたのは確か1月末あたりだったと記憶しています。入門書みたいなのを買って「こんな書き方すんのか」くらいな感じで勉強していたら2月の終わりくらいに友人から競技プログラミングを誘われました。それがAtCoderとの出会いです。懐かしいですね。まだ三ヶ月も経ってないですが･･･。
AtCoderのプロフィールはこちら

参加環境

使用言語：Java
コードはメモ帳で書いてPowerShellかコマンドプロンプト(気分で変わる)を用いてコンパイル、テストをして大丈夫そうなら提出。
何かソフトを導入して～みたいなことはしていません。
テンプレートみたいなものは事前に作ってコピペしてます。
↓こんな感じ(テンプレなので可読性ガン無視状態)

基本的にこれを使ってますが、案外自作メソッド使わないで終わるんですよね。もうちょっと良いテンプレ作る必要があるのかな･･･。

追記

今は以下の記事にまとめたテンプレを使ってます。まだ使ったことないのもあるので間違いがあるかもしれませんが…。

入茶のためにしたこと

可能な限りABC、ARC、AHCなどに参加してたら茶色になりました。おそらく問題慣れしたのかなぁ。
過去問は一切解いていないのか、と言われれば解いた問題もありますが、かなり少ないです。

今でもこんなザマです。もっとやる気出すべきですよねぇ(他人事)。
解いてる人は解いてますし、やる意味がないのかと言われたらめちゃくちゃ役に立つと思います。傾向がつかめますし、アルゴリズムの勉強になりますし。私が単純に怠け者なだけです。
AtCoder以外の競技プログラミングには参加していません。英語のものは読めないし、他のものも手を付けてしまうとAtCoderがおろそかになっちゃうかなぁと思っているので。

おそらく、私が茶色になれた理由は友人がアルゴリズムに詳しかったことと数学が元々好きだったからかなぁと思います。
個人的な意見ですが、競技プログラミングはほぼほぼ数学です。計算量を減らせるか、すなわちどこからどこまでが必要の無い計算かどうかは人間側が計算・判断する必要があって、それって結局数学で証明できたりするんですよね。まぁ茶色程度の私の数学力ではABCだと運が良ければ4完ってところなので(頻繁に実行時間超過をします)、それ以上を目指すなら大学数学の習得やアルゴリズムの暗記などが必要な気もしますが、私自身はこのレベルでも十分楽しめているのでゆっくり技術を習得できたらなぁくらいにしか思ってません。

実際に解くときの発想

実際にどんな感じで解いてるのかなみたいなのを伝えられたらなぁと思うのでABC247-Cを解いたときのコードと説明でもしようと思います。ガッツリネタバレみたいな感じなので嫌な人は次の見出しまで飛んでください。

こちらが問題文になります。

この問題を見たとき、私は最初for文でString型を連結していって目的のものを作れそうだな、と思いました。実装するならこんな感じ？

Sample1.java

import java.util.*;
class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        String answer = "1";
        for(int i=2;i<=N;i++){
            answer = answer+" "+String.valueOf(i) +" "+answer;
        }
        System.out.println(answer);
    }
}

提出してみるとACでした。これで十分ですね。

ただ私は、これで終わるのはなんとなくもったいない気がするんですよね。もっと他のやり方ないかなぁと思ってしまうんですよ(本当は制約あんまり見てなくてこのやり方だと普通すぎてTLE出ると思ってた)。
で、実際に私が提出したコードはこちらです(一部改良した点アリ)。

Sample2.java

import java.util.*;
class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        for(int i=1;i<(int)Math.pow(2,N);i++){
            if(i%32768==0)
                System.out.print(16+" ");
            else if(i%16384==0)
                System.out.print(15+" ");
            else if(i%8192==0)
                System.out.print(14+" ");
            else if(i%4096==0)
                System.out.print(13+" ");
            else if(i%2048==0)
                System.out.print(12+" ");
            else if(i%1024==0)
                System.out.print(11+" ");
            else if(i%512==0)
                System.out.print(10+" ");
            else if(i%256==0)
                System.out.print(9+" ");
            else if(i%128==0)
                System.out.print(8+" ");
            else if(i%64==0)
                System.out.print(7+" ");
            else if(i%32==0)
                System.out.print(6+" ");
            else if(i%16==0)
                System.out.print(5+" ");
            else if(i%8==0)
                System.out.print(4+" ");
            else if(i%4==0)
                System.out.print(3+" ");
            else if(i%2==0)
                System.out.print(2+" ");
            else
                System.out.print(1+" ");
        }
        System.out.println();
    }
}

このコードは何をやっているんだ？？？って思うかもしれないので説明すると、i番目の数字sはiを素因数分解したときの2の指数をkとするとs=k+1で表されるということに気付いて、2^15から順に割ってみて因数に持つか(つまりあまりが0か)を判定するように記述しています。
提出してみるとちゃんとACが取れます。

コード	実行時間
Sample1	189 ms
Sample2	344 ms

どう考えてもSample1の方がコードも実行時間も短いですし好まれるコードでしょう。しかし、私はどうしても楽しみながら解きたい人間なので(ただ問題文読み間違えただけなのも否めないですが･･･)こういうコードを書きたがるんですよね。
けど、結局ACなのだから間違いではないですよね？むしろさまざまな観点から解くことは良いことだと私は思っています。荒削りなコードでも全然良いと、特に競プロを始めたばっかりの人には思ってほしいなぁと感じます。

追記

今更ですが、Sample2のforの中は以下のように書き換えることでもっと短く書けるかと思います。

Sample2.java

//forの中身
int temp = i;
for(int j=1;;j++){
    if((temp%2)==1){
        System.out.print(j+" ");
        break;
    }
    temp /= 2;
}

絶対この方が良かった･･･。ちなみに実行時間は391msでした。ちょっと遅くなっちゃいましたね。

さらに追記

もし速度を気にするのであれば以下のように書き換えることで多少高速化できます。

Sample2.java

import java.io.*;
class Main{
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static PrintWriter pw = new PrintWriter(System.out);
    public static void main(String[] args)throws IOException{
        int N = Integer.parseInt(br.readLine());
        pw.print(1);
        for(int i=2;i<(1<<N);i++){
            int temp = i;
            pw.print(" ");
            for(int j=1;;j++){
                if((temp%2)==1){
                    pw.print(j);
                    break;
                }
                temp>>=1;
            }
        }
        pw.println();
		pw.close();
    }
}

133msだったのでまぁまぁ良いんじゃないでしょうか。
ちなみにビット演算はKing314さんから指摘されて知りました。知識(というか精進)が足りないですね･･･。

今から始める人へ

"競技"プログラミングと言われると地道に精進しながら難解な問題を解かなくちゃいけないと思うかもしれませんが案外ひらめき的な部分がある気がします。実際、難しい問題を解くときは使えるアルゴリズムをひらめくことができるかどうかがキーになりますし。
あと私個人の意見ですが、競技プログラミングは趣味の範疇で良いと思います。ギスギスした感じで解くよりは楽しみながら解いた方が絶対良いですからね。
楽しんでいる内に少しずつ解けるようになるから楽しみながら取り組もう！

おまけ

メモ帳でやるときは文字コードが初期でUTF-8になっているので、もしメモ帳でコーディングするときは事前にANSIで保存しておくかPowerShell(コマンドプロンプトでも可)に以下のように書いてコンパイルするとデバッグで日本語使うときに楽です。

javac -encoding UTF-8 ファイル名.java

また、テストケースはコマンドラインに直接書き込んだ方が速いですが、何回も同じテストケースをやるときはtest.txtを作って同じディレクトリ内に保存して以下のように実行するといちいちコピペしないでスマートにテストできます(このやり方はコマンドプロンプトのみ可。PowerShellでのやり方はこれの下のコードを参照)。

java Main < test.txt

他にも、PowerShellでコンパイルと実行を同時に行なうこともできます(PowerShellの実行ファイルは許可範囲を指定する必要があります。詳しいことは他の人の記事を見てください)。

Test.ps1

javac -encoding UTF-8 Main.java
if(Test-Path "${PSScriptRoot}Main.class"){
    java Main #ファイルの中身を入力として読み込ませたいなら「cat test.txt | java Main」と記述
}
pause
exit

これでMain.javaのコンパイルと実行を同時に行えます。「java Main」と書いた場合はコンテストサイトからコピーして貼り付ければ結果がでて、Enterを押すとウィンドウが閉じます。
あと、一応書いておきますが、メモ帳環境は少数派です。JavaならEclipseなどを使った方が良いですよ。