プログラミングの能力をあげたい奴らがそこにいた。彼らは今日はどんな敵と戦うのだろうか。みていこう。
ちゃらららー
今日のお題 3と5の倍数
早速彼らは第1問に取り掛かった。3と5の倍数が云々とのこと。早速問題をみてみよう。
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よりもしたの自然数のうち3もしくは5の倍数の合計を算出するコードをかく問題。
あっ早速億ラビット君からコメントが。
早っ。

かけだしハッカー部のエース二人がサクッとやってみたら不合格。なかなかHackerrankは甘くないようですね。
1 2 3 4 5 | 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) |
数時間後
はるかの最初のコード
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 | #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 という3の階乗と5の階乗を足していくことを理解しているわね。あとはちゃんと3と5の公倍数を取り除くところまでできていてOKね
ちゃんと学校で習った式使っているわね。ナイス。ループ使うと計算時間食ってしまうから公式は必要よ。でもダメだったのね。エラーが出たのね。
合格したコードは
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 | #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 までつかえるもんね。なるほどね。犬よくやったわね。
次は平井君のコードみてみましょう。おおっと。Scalaですね。これは先生も初めての言語です。みたところJava系なので読めないことはないですわね。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | 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なのね。
1 2 3 4 5 6 7 8 9 10 11 12 13 | #!/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)) |
犬と違って、それぞれの階乗の和は一般関数にしてあるわね。しっかりしているわ。あっこれは。こんな演算子使ってる。
//
なるほど。勉強になりますね。
ということで、駆け出しハッカー部の1日が終わった。どうやらこれはフィクションではなく実話のようだ。覗きたいかたはこちらに行くと見えるらしいよ。プログラミングの腕あげるにはいい場所ではないかな?
では