駆け出しハッカー部の仲間たち { ３と５の倍数編 }

プログラミングの能力をあげたい奴らがそこにいた。彼らは今日はどんな敵と戦うのだろうか。みていこう。

先生

なんかここ高校の部活ぽいわよ

はるか

先生ここ部活ですよ。駆け出しハッカー部って名前です。僕も部員です。

先生

今日は解説としてお仕事もらったからにはちゃんとやってあげるわ。しょうがないわね。

ちゃらららー

ひらい

今日受験したコーディングのテストには読解力が必要とされたんすよね。あとは配列をsliceしたときに2つ以下の数字の組み合わせが一番多く含まれているときの要素数を返す関数をつくりなさい。みたいなものもありました

億ラビット

アルゴリズムを突き止めていくと、条件分岐とかループがなくなるので、そもそもimmutableでtypescriptとかと組み合わせるとコードをテストする必要が薄れて生産性も上がるということですよね。プログラマーの生産性を決める一つの基礎力だと思ってます。脳内パラダイムシフトですね。この領域に意識的に入っていかないと１０年、１５年やっててもペーペーで終わるみたいな。以上、体育会系プログラマーの戯れ言でしたw

ひらい

おもしろいですね。アルゴリズムの研究をする会をひらきましょうか？

億ラビット

いいですねー。動くものを作れるだけじゃなくて、プログラマーとしての基礎力の研究するチャンネル作りたいですね。地道な基礎練習は体育会の基本ですねw。

ひらい

じゃあ Hackerrank使って遊びましょう。

先生

読者のみなさん、 hackerrank はプログラマーのスキルを正当に評価することを目的としてサービスを開発しているのよ。プログラマーはHackerrankに参画することによって、能力を証明できるというわけね。そのサービスとしてプログラミングの問題が出されているわ。ディスカッションのパートでは有益な情報交換もあり好感がもてるわね

今日のお題　３と５の倍数

早速彼らは第１問に取り掛かった。３と５の倍数が云々とのこと。早速問題をみてみよう。

Project Euler #1: Multiples of 3 and 5

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 6 and 9. The sum of these multiples is 23.Find the sum of all the multiples of 3 or 5 below N.

source: https://www.hackerrank.com/contests/projecteuler/challenges/euler001

英語で書いてある通りだね。与えられたNよりもしたの自然数のうち３もしくは５の倍数の合計を算出するコードをかく問題。

あっ早速億ラビット君からコメントが。

早っ。

億ラビット

僕適当に挑んだ結果今日の問題ミスりました。やり直して来ますw

はるか

えっ。天才プログラマーがミスってる。

ひらい

サクッとやったらタイムアウトー

かけだしハッカー部のエース二人がサクッとやってみたら不合格。なかなかHackerrankは甘くないようですね。

億ラビット

僕解けました！

ひらい

解けましたwこれ1問目からちゃんと考えないと解けないやつきてますね(ぎりぎりかもw)

学士

Runtime Errorだと？何がおかしいのかわからんっす。

ひらい

問題文を素直にプログラムに落とし込むと処理する量が多すぎてランタイムエラーになります(こんなデータ量処理できないよ)

学士

おー。なめてた。。。リスト内包表記は重いという事？

t = int(input().strip())
for a0 in range(t):
    n = int(input().strip())
    result = sum([i if i%3==0 or i%5==0 else 0 for i in range(n)])
    print(result)

t = int(input().strip())

for a0 in range(t):

n = int(input().strip())

result = sum([i if i%3==0 or i%5==0 else 0 for i in range(n)])

print(result)

億ラビット

これ紙に書いたりして法則を見つけないとですね。パターンを見つける感じですかね

はるか

おー。なるほどなんだか大変そうだ。今はできないのであとで来ますー。

学士

くうううー

数時間後

学士

しゃあああああできたあああああ！！！！！！！！！

はるか

くううーーーービリで完成した

先生

全員終わったようね。さて、コードでもみていこうかしら。最初はそこの犬の凡庸なコードがらみさせてもらうわ

はるかの最初のコード

#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <stdbool.h>

int main(){
    int t;
    unsigned x3;
    unsigned x5;
    unsigned x15;
    
    scanf("%d",&t);   
    for(int a0 = 0; a0 < t; a0++){
        int n;
        scanf("%d",&n);
        n=n-1;
        x3=0;
        x5=0; 
        x15=0;
        
        x3 = 3 * (((n/3)*((n/3)+1))/2);
        x5 = 5 * (((n/5)*((n/5)+1))/2);
        x15= 15 * (((n/15)*((n/15)+1))/2);
        
        printf("%u\n",x3+x5-x15);
       
    }
    
    
    return 0;
}

#include <math.h>

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

#include <assert.h>

#include <limits.h>

#include <stdbool.h>

int main(){

int t;

unsigned x3;

unsigned x5;

unsigned x15;

scanf("%d",&t);

for(int a0 = 0; a0 < t; a0++){

int n;

scanf("%d",&n);

n=n-1;

x3=0;

x5=0;

x15=0;

x3 = 3 * (((n/3)*((n/3)+1))/2);

x5 = 5 * (((n/5)*((n/5)+1))/2);

x15= 15 * (((n/15)*((n/15)+1))/2);

printf("%u\n",x3+x5-x15);

}

return 0;

}

これは結局エラーがでて回答が出なかったようね。この問題はNに至るまでの 3, 6, 9 , 12…と 5,10, 15 ,20 という３の階乗と５の階乗を足していくことを理解しているわね。あとはちゃんと３と５の公倍数を取り除くところまでできていてOKね

ちゃんと学校で習った式使っているわね。ナイス。ループ使うと計算時間食ってしまうから公式は必要よ。でもダメだったのね。エラーが出たのね。

合格したコードは

#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <stdbool.h>

int main(){
    unsigned long long t;
    unsigned long long x3;
    unsigned long long x5;
    unsigned long long x15;
    
    scanf("%lld",&t);   
    for(unsigned long long  a0 = 0; a0 < t; a0++){
        unsigned long long  n;
        scanf("%lld",&n);
        n=n-1;
        x3=0;
        x5=0; 
        x15=0;
        
        x3 = 3 * (((n/3)*((n/3)+1))/2);
        x5 = 5 * (((n/5)*((n/5)+1))/2);
        x15= 15 *(((n/15)*((n/15)+1))/2);
        
        printf("%lld\n",x3+x5-x15);
       
    }
    
    
    return 0;
}

#include <math.h>

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

#include <assert.h>

#include <limits.h>

#include <stdbool.h>

int main(){

unsigned long long t;

unsigned long long x3;

unsigned long long x5;

unsigned long long x15;

scanf("%lld",&t);

for(unsigned long long a0 = 0; a0 < t; a0++){

unsigned long long n;

scanf("%lld",&n);

n=n-1;

x3=0;

x5=0;

x15=0;

x3 = 3 * (((n/3)*((n/3)+1))/2);

x5 = 5 * (((n/5)*((n/5)+1))/2);

x15= 15 *(((n/15)*((n/15)+1))/2);

printf("%lld\n",x3+x5-x15);

}

return 0;

}

ふむふむ。なるほど。桁数の問題だったのね。unsigned Long Long で64ビットワードまで使えるようにしてクリアしたのか。桁数必要だったのね。Unsigned Long Long なら 18446744073709551615　までつかえるもんね。なるほどね。犬よくやったわね。

はるか

いろいろはまりましたー。C言語でやってみましたがいろいろ型指定もあって少し面倒でした。C好きなんですけどちょっとPythonに明日からしてみようとおもいます。階乗の和は公式を使わないとさすがにタイムアウト食らいましたね。このあたりが大変でした

次は平井君のコードみてみましょう。おおっと。Scalaですね。これは先生も初めての言語です。みたところJava系なので読めないことはないですわね。

ひらい

Scalaはオブジェクト指向と関数型両方対応しているJVM上で構築されたAPIです。関数型の美学が爆発ですw　くわしくは僕の書いたこの記事読んでね　[Akka HTTP + Slick]誰でも手軽に作れるScala API

package com.jobinterview

object MultiplesOf3And5 {
  def solution(n: Long): Unit = {
    def sum(divide: Long): Long = {
      (1L to n / divide).sum * divide
    }

    println(sum(3) + sum(5) - sum(15))
  }

  def main(args: Array[String]) {
    val sc = new java.util.Scanner(System.in)
    val times = sc.nextInt()
    (0 until times).foreach(_ => println(solution(sc.nextLong() - 1)))
  }
}

package com.jobinterview

object MultiplesOf3And5 {

def solution(n: Long): Unit = {

def sum(divide: Long): Long = {

(1L to n / divide).sum * divide

}

println(sum(3) + sum(5) - sum(15))

}

def main(args: Array[String]) {

val sc = new java.util.Scanner(System.in)

val times = sc.nextInt()

(0 until times).foreach(_ => println(solution(sc.nextLong() - 1)))

}

(1L to n / divide).sum*devide

なに？この表記は？なんとこれで階乗の和が計算できるのね。すごいわ。あとは基本的に犬のコードと同じかしらねScalaだとシンプルにかけるのは興味深いわね。

最後に天才の億ラビットくんのコードみてみますね。億ラビットくんはPythonなのね。

#!/bin/python3
import sys

def solve(n):
    def s(m):
        q = (n - 1) // m
        return q * m * (1 + q) // 2
    return s(3) + s(5) - s(15)

t = int(input().strip())
for a0 in range(t):
    n = int(input().strip())
    print(solve(n))