はじめに
どーも筆者です。私はプログラミング未経験でIT企業に就職し、エンジニアとしてキャリアをスタートさせた若造です。
研修でpaizaに出会い、問題を解くのにどはまりし、プライベートでも問題をちょいちょい解くようになりました。
今回はそんな私がAランク問題を解けるようになるまでと、Aランク問題の解説を行いたいと思います。言語はJavaです。
初心者でどうやったら難しい問題解けるようになるのだろうと困っている人の少しでもお役に立てればと思います。
私のpaizaとの向き合い方
初めてコードを見たとき、なんだこれ？英語いっぱいでわけわからん。呪文？状態でした。
なのでまず入門編の講座を見たり、並行して簡単な問題を解いたりしてゆっくりと理解を進めていきました。
ある程度理解が進むと問題を解くことを中心として、わかんないところが出たり、あれ？これなんだったっけ？ていうのが出るたびに調べてまた解くというスタイルに切り替えます。このやり方が一番理解が進みます。経験上です。数学と一緒です。
わからなすぎたら回答を見るというのも一つの手です。ただそれを見ただけでは何の身にもならないので、それを自分の手で書くことが大事です。
大事なことなのでもう一度言います。見ただけで理解した気になってはいけません。
ちゃんと自分の手で書くことがとても大事です。頭への定着率が全然違います。経験上です。
あと周りにエンジニア経験者がいれば質問しまくるのもとても有効です。人に聞いて学んだことは忘れにくいです。経験上です。自分で考えまくってから聞くとより有意義な時間になるし、頭に残ります。
そんなことを繰り返していくうちに、ある程度自力で解けるようになり、問題を解くのが好きになっていきました。
言いたいことは、上達率、定着率を上げたければひたすら解きまくり考えまくるということです。
解けなかったとしても考えまくった時間はあなたの力になります。絶対に。
これでどんどん解く問題のランクを上げていき、Aランクも解けるようになったって感じです。
ちなみに問題を解くときのコツですが、ノートに絵をかいたり、頭に浮かんでるロジックを書き起こすといいと思います。頭が整理されますし、後日見たときに記憶が呼び起こされるので。
さいごに
初めてのものを扱うときは頭がびっくりしちゃって、？？状態になります。ですがそこで諦めてはいけません。扱っていくうちにちょっとずつ慣れてきます。だいぶ慣れてくるとそこから波に乗っていけます！
ひたすらに問題を解いて、考えて悩んで、調べまくりましょう。
ただコードを見ただけじゃ全然頭に定着しないので、手を動かして考えまくりましょう。
だいぶパッションです笑
私もこれから精進してまいります！
おまけ～Aランク問題の解説～
ここからはめちゃめちゃ長いので興味のある方だけお付き合いいただければと思います。
私の努力の結晶を解説します。
私は数学が好きということもあり数学っぽい問題をチョイスしました。
「区間の積」という問題です。
私の回答では、配列と多重ループを使います。そこの理解がある前提で話を進めます。
問題のリンクです。
https://paiza.jp/works/mondai/a_rank_level_up_problems/a_rank_twopointers_boss
問題は以下の通りです。
数列 A についての情報と、整数 K が与えられます。
次の条件を満たす A の部分列の最短の長さを答えてください。
・ 数列に含まれる全ての要素の積が K 以上である。
なお、数列の部分列とは、数列の連続した 1 つ以上の要素を取り出して作ることができる数列のことです。
んー問題もシンプルでいいですねー笑
部分列の要素の積がK以上となるのは、最短で要素が何個の時？っていう問題ですね。
入力は、
（数列の要素の数）K
（数列）
で与えられ、
期待する出力は
（最短の要素の数）
です。
入力例と出力例を確認しよう
paizaの問題を理解するうえで大事なのは入力例と出力例を見て問題に照らし合わせることです。
例えば、
入力例1
5 1
1 1 1 1 1
出力例1
1
だと、要素1個でK(=1)以上となり、必要な要素は1個なので出力は1です。
入力例2
6 16
2 0 2 2 2 2
出力例2
4
だと、3番目～6番目の2×2×2×2=16でK(=16)以上となり、必要な要素は4個なので出力は4です。
どうでしょう。問題の理解が進んだのではないのでしょうか。ほかの問題でもやってみてくださいね。
ロジックを考えよう
さて、これをどう解くかという話ですがまずは入力に対してどういうロジックを踏めば期待する出力が出るかを考えます。
これについては、最短の要素数を出したいので要素数1から順番に調べていって、初めてK以上になったとき、その要素数を出力すればよさそうです。
コードを考えよう
ロジックが決まればあとはそれをコードを使ってどう描くかです。ここでこれまでの演習で学んできたコードの知識たち、言うなれば武器を使うときです。必要な要素数1から順番に調べるのでfor文を使うというのは確定でいいでしょう。
まずはいったん入力します。
要素の数はyousosuという変数でKはそのままKという変数にします。
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int yousosu = sc.nextInt();
long K = sc.nextLong();
ここではKの条件が10^10までなのでint型ではなくlong型を使ってます。
そして数列に番号を振りたいので数列を配列にします。
配列の名前はsuretu[]にします。
long []suretu = new long[yousosu];
for(int i = 0;i < yousosu;i++){
suretu[i] = sc.nextInt();
}
説明するときはsuretu[]だと長いのでa[]にします。yousosuも長いのでnとします。
さて、for文の中身を考えていきましょう。
小さい数字から考えてみよう
といってもいきなりnから考えるのは難しいので、はじめは具体的な小さい値で考えてみるとわかりやすいです。
これは数学の問題を解くときに、私がよくやっていた手法です。
いわゆる実験ってやつです。
ここでは具体的な値としてn=4(yousosu=4)の時を考えてみましょう。
n=4のとき
(1)必要な要素数が1の時
この時は単純でそれぞれの要素がK以上かを調べればよいです。
a[0]
a[1]
a[2]
a[3]
がそれぞれK以上かを見る。
(2)必要な要素数が2の時
a[0]a[1]
a[1]a[2]
a[2]a[3]
がそれぞれK以上かを見る。
(3)必要な要素数が3の時
a[0]a[1]a[2]
a[1]a[2]a[3]
がそれぞれK以上かを見る。
(4)必要な要素数が4の時
a[0]a[1]a[2]a[3]
がK以上かを見る。
ってな感じです。
nのときを考える
これを参考にnの時を考えていきましょう。大事なのは番号です。これがfor文の中身を考える上では必要です。
n=4の時と照らし合わせながら考えてみてください。4をnにすればいいです。
nのとき
(1)必要な要素数が1の時
a[0]
a[1]
︙
a[n-1] ←(n=4のときはa[3=4-1]でしたね)
がそれぞれK以上かを見る。
(2)必要な要素数が2の時
a[0]a[1]
a[1]a[2]
︙
a[n-2]a[n-1] ←(n=4のときはa[2=4-2]とa[3=4-1]でしたね)
がそれぞれK以上かを見る。
︙
︙
(n-1)必要な要素数がn-1の時
a[0]a[1]…a[n-2] ←(最後はn=4のとき、a[2=4-2]でしたね)
a[1]a[2]…a[n-1] ←(最後はn=4のとき、a[3=4-1]でしたね)
がそれぞれK以上かを見る。
(n)必要な要素数がnの時
a[0]a[1]…a[n-1] ←(最後はn=4のとき、a[3=4-1]でしたね)
がK以上かを見る。
はい、こんな感じです。ただ、これを一回一回計算させてたらとんでもない計算量になるので一個前でやった計算を使ったほうがよさそうです。
そこで全く同じ配列b[]を用意します。前の計算結果にa[]をかけていってb[]をどんどん更新していくというイメージです。ここでは自己代入の考え方を使用します。
それでは実際にやってみます。上と照らし合わせながらやると考えやすいでしょう。
(1)必要な要素数が1の時
これは今までと同じで大丈夫です。
a[0]
a[1]
︙
a[n-1]
がそれぞれK以上かを見る。
★
(2)必要な要素数が2の時
b[0]=b[0]a[1] ←これでb[0]a[1] (=a[0]a[1])が新たにb[0]になりました。以下も同様に、
b[1]=b[1]a[2]
︙
b[n-2]=b[n-2]a[n-1] ←b[n-2]の2は必要な要素数の2と一致してますね
がそれぞれK以上かを見る。
(3)必要な要素数が3の時
b[0]=b[0]a[2] ←これでb[0]a[2] (=a[0]a[1]a[2])が新たにb[0]になりました。以下も同様に、
b[1]=b[1]a[3]
︙
b[n-3]=b[n-3]a[n-1] ←b[n-3]の3は必要な要素数の3と一致してますね
がそれぞれK以上かを見る。
︙
︙
(n-1)必要な要素数がn-1の時
b[0]=b[0]a[n-2]
b[1]=b[1]a[n-1]
がそれぞれK以上かを見る。
(n)必要な要素数がnの時
b[0]=b[0]a[n-1]
がK以上かを見る。
★
はい、こんな感じです。
なんとなくわかっていただけたでしょうか。
それぞれb[?]まで計算しているかが大事なので(要素数)-(必要な要素数)番目まで計算されていることを覚えておいてください。
for文に落とし込む(必要な要素数が1のとき)
ではこれをfor文に落とし込んでいきます。
必要な要素数が1の時は計算方法が独立してるので、まずこの時を考えます。これは単にa[0]~a[n-1]がK以上かを調べればいいので、初期値1のcountという変数を用意して（以降も使います）、もしa[0]~a[n-1]がK以上だったらcount(=1)を出力し、これから書く必要な要素数2以降のコードには入ってほしくないのでSystem.exit(0)というのを使用します。これはそんなものないかなーって調べたら出てきました。こんな感じで武器を増やしてってます。
実際のコードはこんな感じです。
int count = 1;
for(int i = 0;i < yousosu;i++){
if(suretu[i] >= K){
System.out.println(count);
System.exit(0);
}
}
for文に落とし込む(必要な要素数が2以降のとき)
では必要な要素数が2以降の時を考えます。
b[]の名前はbubunretu[]にして、suretu[]と同じものを生成します。
long []bubunretu = new long[yousosu];
for(int i = 0;i < yousosu;i++){
bubunretu[i] = suretu[i];
}
それでは本題に入っていきましょう。
ここでは多重ループの考え方を使います。for文を二重に使用します。
外側のforで必要な要素数を増やしていって、内側のforでそれぞれの要素数の時の中身に入るっていうイメージです。
外側のfor
このforに入るたびに必要な要素数が増えるのでその回数を出力したいです。入るたびにcountを増やしていきましょう。
for(int i = 1;i < yousosu;i++){
count +=1;
こんな感じです。なんでi=1から？とか、いやそれ最後までcountされちゃうじゃんって思うと思うんですけどそれは次の内側のforで解決されるので次に行っちゃいましょー
内側のfor
ここが鬼門ですね。番号がややこしいので。これを考えるうえでさっき考えていたものが役に立ちます。
計算はbubunretu[j] *=suretu[?]ってな感じです。
bubunretu[0]からbubunretu[?]まで計算するかですが、これは(要素数)-(必要な要素数)と同じでしたね。てことは、
for(int j = 0;j < yousosu - i;j++){
でよさそうです。これはjがyousosu-(i+1)まで計算されているってことになるのでOKです。
suretu[?]ですが★で囲われているところをみるとa[i]からa[yousosu-1]まで計算されています。
0 <= j < yousosu-iにiを足すと、i <= j+i < yousosuになるので、suretu[?]はsuretu[j+i]でよさそうです。
ここがちょっと難しいですよね。ぼくもすごい考えました。
で、もしbubunretu[j]がK以上なら外側のfor文を抜け出してその時のcountを出力すればよいのですが、ただのbreakだと内側のfor文を抜け出すことになります。ここで調べますとどうやらラベル付きbreak文というのがあるみたいです。
Outer:
for(int i = 1;i < yousosu;i++){
count +=1;
Inner:
for(int j = 0;j < yousosu - i;j++){
bubunretu[j] *=suretu[j + i];
if(bubunretu[j] >= K){
break Outer;
}
}
}
System.out.println(count);
実際のコードはこんな感じです。
外側のfor文にOuterという名前をつけて、内側のfor文にInnerという名前をつけて、
break outerで外側のfor文を抜け出せるみたいです。へーですよね。
はい、これで問題を解くことができました。ここまで長々と読めた方は相当なもの好きですね笑
書いといてなんですが私はこんなに読めないです笑
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int yousosu = sc.nextInt();
long K = sc.nextLong();
long []suretu = new long[yousosu];
for(int i = 0;i < yousosu;i++){
suretu[i] = sc.nextInt();
}
int count = 1;
for(int i = 0;i < yousosu;i++){
if(suretu[i] >= K){
System.out.println(count);
System.exit(0);
}
}
long []bubunretu = new long[yousosu];
for(int i = 0;i < yousosu;i++){
bubunretu[i] = suretu[i];
}
Outer:
for(int i = 1;i < yousosu;i++){
count +=1;
Inner:
for(int j = 0;j < yousosu - i;j++){
bubunretu[j] *=suretu[j + i];
if(bubunretu[j] >= K){
break Outer;
}
}
}
System.out.println(count);
}
}
最終的なコードはこれです。お疲れ様でした！これからもプログラミングの勉強がんばっていきます！！
皆さんも一緒にがんばりましょ～ありがとうございました～