【解説】プログラミングでかわいい彼女をつくって水着を着てもらう方法

今回は、2015年12月8日より開催しておりました、paizaオンラインハッカソンvol.7「プログラミングで彼女をつくる」の解法とSwiftオープンの上位コードについてお届けします。

■POH7 水着ゲットチャレンジの解説

今回一番難易度が高かった水着問題です。

「これだけ解けない！」「彼女に水着が着せられない！」という声を多くいただきましたが、この解説と模範解答コードがあれば誰でも彼女に水着を着てもらうことができますよ！！やったー！！

水着ゲットチャレンジ問題は、階乗の問題です。階乗とは、簡単に言うと4の階乗であれば4×3×2×1、6の階乗であれば6×5×4×3×2×1というふうに、整数を階段状に掛けた計算結果のことです。

それでは実際の問題文を見てみましょう。

◆問題文

階乗とは数学の演算の一つで、N の階乗をN! と書きます。N が自然数であるとき、階乗は次のように計算できます。

N! = N * (N - 1) * ... * 2 * 1

入力される値

入力は標準入力にて以下のフォーマットで与えられます。

N

条件

すべてのテストケースにおいて、以下の条件をみたします。

1 ≦ N ≦ 1000000

期待する出力

N! の最下位桁から続く0 をすべて除いた値の下位9桁を出力して下さい。

入力例１

入力

15

出力

307674368

入力例２

入力

10

出力

36288

◆解説

それでは、解き方を解説していきます。（コードはPythonになります）

問題の本質部分は以下の行です。

N が与えられたとき、N! のすべての桁の代わりに、N! の最下位桁から続く0 をすべて除いた値の下位9桁を求めるプログラムを作成してください。

――――――――――――――――

N!(Nの階乗)は、Nの数字が大きくなると爆発的に大きくなっていきます。

例えばN = 100　とすると

93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

となり、158桁となり普通の変数では桁あふれしてしまいます。また多倍長の変数などでも1000000の階乗ともなると処理に時間がかかりすぎてタイムアウトしてしまいます。

＜具体的なpythonのコード＞

n = input()
ans = 1
for i in range(1, n+1):
   ans = ans * i

while ans % 10 == 0:
   ans = ans / 10

print ans % 1000000000

このような素直にNの階乗を求めた後に0を除いて、下位9桁を出力という事を行う事ができません。

では、0が増えていくのと、上の桁が増えていくものを随時消していく方針で考えていきましょう。

まずは0が増えていく方を考えていきます。

5の階乗を考えます。

5,4,3,2,1
5! = 120

この時は0が1つ付きます。この0は5かける2で10が現れるからです。

同様に、15の階乗を考えます。

15,14,13,12,11,10,9,8,7,6,5,4,3,2,1
15! = 1307674368000

この時は0が3つ付きます。1つは5!で出現したものが現れています。

残りは10と、15に2の倍数の数字がかけられた時に現れます。

15に2の倍数の数字がかけられた時とは
15,14に注目すると

15=5*3
14=7*2

15*14 = (5 * 3) * (7 * 2)

整理すると 10 * 7 * 3 となり 350 になります。10がかけられるので0が増えています。

10に関してもこのように考えると 2 かける 5 で 10となり 0が1つ増えるとも言えます。

まとめると、各数字の素因数に現れる 5 と 2 がかけられた時に 0 が増えることになります。

上の桁に関しては繰り上がって10桁目より上の桁へ行った数字は9桁以下での計算には関係ありませんので、毎回1000000000の余りを取っていくだけで問題ありません。

具体的に、処理を考えていきます。

・1〜Nのうち、全てにおいて5で割れる場合、割り切れなくなるまで割り算をしてその個数を数えておく

という事前処理をし、答えの変数を ans とすると

ans = 1としておき

・1〜Nを順に

　・5の倍数
　　ならば、割り切れなくなるまで割る
　・2の倍数かつ事前に数えた5の数が1個以上
　　ならば、2で割り切れなくなるまで割り算をし数えた5の数を引いていく
　（この処理をすることで 2 * 5が出現するたびにその計算をスキップすることになります

　・ans = ans * 処理をした数字 と計算し ans を更新する
　・ans = ans % 1000000000 とし9桁に収まるように余りを取る

という処理をすることで桁を溢れさせる事無く計算を進めていく事が出来ます。

以下ソースコードです。

#coding:utf-8
N = input()
ans = 1

#5の倍数になる数を探し5で割れる回数を数える
five = 0
for i in range(1, N+1):
   n = i
   while n % 5 == 0:
       n = n / 5
       five += 1

ans = 1
for i in range(1, N+1):
   n = i

   #5の倍数ならばiを5で割り切れなくなるまで割る
   while n % 5 == 0:
       n = n / 5

   #割り切れなくなった数が2の倍数で、5の倍数が残ってれば2で割り
   #最初で数えた5で割れる回数から1引く
   while n % 2 == 0 and five > 0:
       n = n / 2
       five -= 1

   #9桁になるように余りを取る
   ans = ans * n
   ans = ans % 1000000000

print ans

■めがねゲットチャレンジ　Swiftオープン

今回はPOH7開催直前にSwiftがオープンソース化されたということで、めがねゲットチャレンジ問題をSwiftで解いた方の中から、平均実行時間と提出コードバイト数が少ない順にランキングをそっと（？）公開しておりました。

たくさんのご参加ありがとうございました！！

■問題文

あなたはクライアントから画像分析の仕事を受けました。

N × N ピクセルの白黒画像と M × M ピクセルの白黒画像が与えられます。 白黒画像の各画素は 0 または 1 のいずれかです。 N × N ピクセルの画像を入力、M × M ピクセルの画像をパターンと呼ぶことにします。

あなたの仕事は、入力からパターンとの完全一致を探すことです。

入力とパターンがピクセルの位置 (y, x) で完全一致するとは、 全ての i, j (i = 0, 1, ... M - 1, j = 0, 1, ... M - 1) について、 (入力の位置 (y + j, x + i) におけるピクセル) = (パターンの位置 (j, i) におけるピクセル) が成立することをいいます。

また、依頼主からは、入力にはパターンと完全一致する箇所は必ず 1 つだけ存在するということを 伝えられています。

ここで、N = 4 の入力の例を見てみましょう。

図中の赤い線で囲まれている部分とパターンが完全一致していることがわかります。 完全一致のピクセルの位置、すなわち、(1, 0) を出力してください。

入力される値

入力は標準入力にて以下のフォーマットで与えられます。

N
q_{0, 0} q_{0, 1} q_{0, 2} ... q_{0, N-1}
q_{1, 0} q_{1, 1} q_{1, 2} ... q_{1, N-1}
...
q_{N-1, 0} q_{N-1, 1} q_{N-1, 2} ... q_{N-1, N-1}
M
p_{0, 0} p_{0, 1} p_{0, 2} ... p_{0, M-1}
p_{1, 0} p_{1, 1} p_{1, 2} ... p_{1, M-1}
...
p_{M-1, 0} p_{M-1, 1} p_{M-1, 2} ... p_{M-1, M-1}

条件

すべてのテストケースにおいて、以下の条件をみたします。

10 ≦ N ≦ 100, 2 ≦ M ≦ 10
q_{i, j}, p_{i, j} は 0 または 1
パターンと完全一致する箇所は必ず1つだけ存在します

期待する出力

パターンと完全一致する左上のピクセルの座標を半角スペース区切りで出力してください。

入力例１

入力

4
0 0 1 0
0 1 1 0
0 1 0 1
1 1 1 0
3
0 1 1
0 1 0
1 1 1

出力

1 0

入力例２

入力

4
0 0 0 0
0 0 1 1
0 0 1 1
0 0 0 0
2
1 1
1 1

出力

1 2

■Swiftオープン上位コードのご紹介

1位 ishiokaさん　平均実行時間：0.01 秒 提出コードバイト数：54 byte

let a=Int(readLine()!)!-5;print(78476795%a,78001036%a)

アッ――!!!!

これは完全にテストコードを読まれて出力されていますね！！！！

このような解き方（？）をされた方も非常に多かったのですが、せっかくなので問題に沿った解き方で挑戦してくださった方のコードで解説したいと思います。

8位 formulaさん　平均実行時間：0.01 秒 提出コードバイト数：182 byte

var i=0,j=0,n=0,m=0,p=[UInt8](),r={readLine()!},R={m=Int(r())!;for k in 0..<m{p+=r().utf8+[0]}};R();n=m;R();for;j<m*m;{if p[2*(i+j/m*n+j%m)]^p[2*(n*n+j++)]>0{i++;j=0}};print(i/n,i%n)

formulaさんのコードを見やすくするため、問題担当者がインデントと解説コメントを追記させていただいたものがこちらです。

var i=0,
    j=0,
    n=0,
    m=0,
    p=[UInt8](),
    r={readLine()!},
    R={
            m=Int(r())!;
            for k in 0..<m{
              p+=r().utf8+[0]
            }
    };
//ここまでが各種初期化処理
//i,j,n,m,p[]までは普通の初期化処理

//r, Rは関数を変数に入れて何度も呼び出す際に文字数を消費しないような工夫です。

//rは 1行読み込む関数 readLine()! をrに代入しておき何度か呼ぶので短く呼べるようにしている。

//Rは 1行目を読み込み変数 m に代入し0からm行を取得して変数に代入していく処理、区切り文字に[0]を使っている
//また文字列はそのままutf8で代入しているので0と1と半角スペースがそれぞれ配列的には48(文字0), 49(文字1), 32(半角スペース)のように入力を得ている。
//0 1 0 1のような1行ならば
//[48, 32, 49, 32, 48, 32, 49, 0]
//みたいな感じで1行を得て1次元配列に0区切りで取得しています。
//データは0区切りで画像とパターンまとめて変数pに入力しています。

R();//先に説明したRを実行してpに一致する点を探す0,1の画像を入力
n=m;//Rを実行すると同時にmに行数が得られるのでnに代入しておいている
R();//画像から探すパターンをpに追加入力
//この時点でmはパターンのサイズ

for;j<m*m;//0からm*mまでループ、即ちパターンのサイズ分ループ
{
  if p[2*(i+j/m*n+j%m)]^p[2*(n*n+j++)]>0 { //条件文
    //p[2*(i+j/m*n+j%m)] と p[2*(n*n+j++)] の排他的論理和「^」をとっている。
    //排他的論理和を取るとここで比較されうる数字48,49では一致すれば0,一致しなければ1なので一致しなければ条件を満たします。
    i++;
    j=0
  }
};

//ループを抜ける条件は末尾までパターンと一致しきった時です。
//iは一致した点なのでi/nで縦軸、1%nで横軸のそれぞれの位置が分かります。
print(i/n,i%n)

この問題は、2次元配列に持った0,1の画像の様なデータを一致する部分を探すために2次元配列から入力を得たり、一致する部分を探すために比較的ループが多くなったり……でコードも冗長になりがちな問題でした。formulaさん、ありがとうございました！！

■まとめ

paizaオンラインハッカソンvol.7「プログラミングで彼女をつくる」の解法、いかがでしたでしょうか？

「レア問題は難しくて全然解けなかった＞＜」という方もいらっしゃったかと思いますが、よかったら解説や回答コードを参考にまたチャレンジしてみてくださいね！

paiza.jp

■壁紙プレゼントについて

paizaに会員登録すると、下記の壁紙３種類がダウンロードできます！是非お気軽にご登録下さい！

---

paizaは、技術を追い続けることが仕事につながり、スキルのある人がきちんと評価される場を作ることで、日本のITエンジニアの地位向上を目指したいと考えています。

自分のスキルを磨いていきたいと考えている方におすすめなのが「paizaラーニング」。オンラインでプログラミングしながらスキルアップできる入門学習コンテンツです。初心者でも楽しくプログラミングの基本を学ぶことができます。

そして、paizaでは、Webサービス開発企業などで求められるコーディング力や、テストケースを想定する力などが問われるプログラミングスキルチェック問題も提供しています。

スキルチェックに挑戦した人は、その結果によってS・A・B・C・D・Eの6段階のランクを取得できます。必要なスキルランクを取得すれば、書類選考なしで企業の求人に応募することも可能です。「自分のプログラミングスキルを客観的に知りたい」「スキルを使って転職したい」という方は、ぜひチャレンジしてみてください。