こんにちは。谷口です。
paizaでは多数のプログラミングスキルチェック問題を公開しています。
問題はS・A・B・C・Dと5つのランクにわかれているので、プログラミング初心者の方でもDランクから無理なく挑戦していただくことができます。
ただ、プログラミングの勉強を始めたばかりの方から「簡単な問題は解けるけど、なかなかランクをアップさせることができない」「少し難しい問題になると、途端に解き方がわからなくなってしまう…」とご相談を受けることもあります。
そこで、paizaラーニングでは「スキルチェック入門編」という動画講座を全編無料で公開しています。
プログラミング問題を題材に、単純な解き方だけでなく、コードの改善の仕方やアルゴリズムの考え方などもあわせて解説しています。「プログラミングスキルをアップさせたい」「プログラミング問題に挑戦してみたい」といった方の参考になると思いますので、今回はその講座内容をご紹介します。
※今回はPythonで解いていますが、解き方やアルゴリズムに関してはどの言語でも通じます。
問題「日別訪問者数の最大平均区間」(Bランク相当)
あなたはとあるWebサイトを管理していました。
ある連続したk日間、このウェブサイトでキャンペーンを行ったのですが、それが一体いつだったのか忘れてしまいました。幸い、Webサイトを運営していた全n日分のアクセスログが残っており、各日の訪問者数が分かっています。とりあえず、連続するk日の中で最も平均訪問者数が多い期間を、キャンペーンを行った期間の候補だと考えることにしました。
n日分の訪問者数のリストとキャンペーンの日数kが入力されるので、キャンペーンを行った期間の候補数と、候補の中で最も早い開始日を出力してください。
入力される値
入力は2行からなります。 1行目にはnとkが半角スペース区切りで入力されます。 2行目にはn個の整数a_1, a_2, …, a_nが半角スペース区切りで入力されます。a_iはi日目の訪問者数を表します。
条件
8個のテストケースにおいて、入力される値は以下の条件を満たします。
1≦n≦1,000
1≦k≦n
0≦a_i≦100全てのテストケースにおいて、入力される値は以下の条件を満たします。
1≦n≦300,000
1≦k≦n
0≦a_i≦100
期待する出力
キャンペーンを行った期間の候補数と、候補の中で最も早い開始日を、この順で半角スペース区切りで1行で出力してください。
入力例1
5 3 1 2 3 2 1
出力例1
1 2
入力例2
10 2 6 2 0 7 1 3 5 3 2 6
出力例2
5 1
実際に問題を解いてみる
入力値を取得する
まず、入力値を取得する処理を書きましょう。
入力値は、1行目に 2 つの変数 n と k が入力されます。 n は2行目にある訪問者数リストの日数、 k はキャンペーンの期間となっています。2行目は、 n 日分の訪問者数となっています。
# n と k を取得 input_str = input().split() # スペース区切りで取得 n = int(input_str[0]) k = int(input_str[1]) # a_1, a_2 ... a_n を取得 input_list = input().split() a_list = [] for a_i in input_list: a_list.append(int(a_i))
input関数で入力値を受け取るときに、split関数で入力値を分割して、input_listに代入しています。それから、リストの要素を全てint型に変換して、新しく作成したリストである a_list に代入しています。
受け取った入力値を処理する
次に、受け取った入力値を処理していきましょう。
# n と k を取得 input_str = input().split() # スペース区切りで取得 n = int(input_str[0]) k = int(input_str[1]) # a_1, a_2 ... a_n を取得 input_list = input().split() a_list = [] for a_i in input_list: a_list.append(int(a_i)) for i in range(n - k + 1): print(a_list[i])
はじめに、5日間のデータを、3日間ずつのまとまりでループを回すことを考えます。 一番左から3つのまとまりをとって、右に1つずつ期間をずらしていくイメージですね。また、右端の最後の要素を超えないように気をつける必要があります。
右端を超えないように、かつ5日間を3つのまとまりで処理していくなら、5 - 3 + 1 回、繰り返せばいいですね。 プラス1しているのは、リストは0番目から始まっているので、最後の要素も含むようにするためです。
ここまでできたら、あとは平均値の一番大きい区間を探して、その区間が何個あるのかと、最初に出てくる場所を探しましょう。
# n と k を取得 input_str = input().split() # スペース区切りで取得 n = int(input_str[0]) k = int(input_str[1]) # a_1, a_2 ... a_n を取得 input_list = input().split() a_list = [] for a_i in input_list: a_list.append(int(a_i)) # キャンペーンの各区間の平均値 average = [] for i in range(n - k + 1): i_average = 0 for j in range(k): # k日間分足して平均を求める i_average += a_list[i + j] average.append(i_average / k)
平均値を保存するリスト変数 average を作り、 ループの中にさらにループを作って、各開始日ごとに k 日間分を足し算したら k で割って、平均を average リストに追加しています。
出力値を求めて出力する
最後に、出力する値を求めます。
# n と k を取得 input_str = input().split() # スペース区切りで取得 n = int(input_str[0]) k = int(input_str[1]) # a_1, a_2 ... a_n を取得 input_list = input().split() a_list = [] for a_i in input_list: a_list.append(int(a_i)) # キャンペーンの各区間の平均値 average = [] for i in range(n - k + 1): i_average = 0 for j in range(k): # k日間分足して平均を求める i_average += a_list[i + j] average.append(i_average / k) ans_max = 0 for i in average: # 最大値をループで求める if ans_max < i: ans_max = i ans_first_max = 0 for i in average: # 最初に出てくる日を求める if i == ans_max: break ans_first_max += 1 ans_count = 0 for i in average: # 最大値と同じ値の個数を求める if ans_max == i: ans_count += 1 print(str(ans_count) + " " + str(ans_first_max + 1))
平均が一番大きい日を求めて、最初に出てくる日を求めて、次に何個の候補日があるかを求めて、最後に出力しています。
まとめ
とりあえずこれで答えは出ますので、ひとまず間違ってはいない解答コードができました。
ただ、少しコードの書き方が冗長な感じがするので、もっとシンプルなコードにできそうですね。アルゴリズムも見直せば、もっとスマートに答えが出せそうです。
paizaラーニングの「スキルチェック入門編2」では、もっと関数やメソッドを使って冗長なコードをシンプルにする方法や、アルゴリズムを見直して処理を高速にする方法などを解説しています。
「スキルチェック入門編1」では、さらに初心者向けにDランク問題の解き方から解説していますので、「全然わからなかった」という方は、まずそちらから始めてみたほうが無理なく学べます。
また、paizaラーニングの「アルゴリズム入門編」では、FizzBuzz、フィボナッチ数やハノイの塔といった、就職・転職の技術面接などでもよく出題されるプログラミング問題のアルゴリズムを解説しています。
「すぐに問題を解いてみたい」という方は、スキルチェック問題に挑戦してみてください。
詳しくはこちら
「paizaラーニング」では、未経験者でもブラウザさえあれば、今すぐプログラミングの基礎が動画で学べるレッスンを多数公開しております。
詳しくはこちら
そしてpaizaでは、Webサービス開発企業などで求められるコーディング力や、テストケースを想定する力などが問われるプログラミングスキルチェック問題も提供しています。
スキルチェックに挑戦した人は、その結果によってS・A・B・C・D・Eの6段階のランクを取得できます。必要なスキルランクを取得すれば、書類選考なしで企業の求人に応募することも可能です。「自分のプログラミングスキルを客観的に知りたい」「スキルを使って転職したい」という方は、ぜひチャレンジしてみてください。
詳しくはこちら