概要
・グリーのエンジニアに応募してみたいが、応募前に自分の実力を試してみたい。
・地方に住んでいるので面接回数が少ない方がありがたい。
・面接は苦手だがプログラミングには自信がある。
GREE Programming Challengeは、このような方々のご要望にお応えするために作られた新しい採用プログラムです。
プログラミングスキルを評価する１次面接をパスできますので効率的な転職活動を行って頂けます。
もちろん学生の皆さんのチャレンジもお待ちしております。
チャレンジ方法
制限時間内に与えられた問題を解決するプログラムを書いてください。
一定の基準をクリアした方については、弊社人事担当から面接のご連絡をさせて頂きます。
※ただし、あなたの書いたコードが他人のコードに酷似していた場合、
あなただけでなく、酷似していた方についても失格とさせて頂きますので、問題の管理は厳重にお願いします。
もう採用は終了しているみたいなので記事書く。
カードのシャッフル（配点：30点）
N枚のカードをシャッフルするアルゴリズムを以下のように定義する。
1) カードをまずK個の山に均等に分ける。
2) 一つ目の山には、元のカードの最下部にあった「N/K枚」を順番を変えずにそのまま使う。
3) 二つ目の山には、元のカードの最下部から2番目にあたる「N/K枚」の塊を順番を変えずに使う。以下同様。
4) これでK個の山が出来たので、次にシャッフルに移る。
まず一つ目の山の一番上にあるカードを取って、シャッフル結果の山の1枚目のカードとなるようにする。
さらに二つ目の山の一番上にあるカードを取って、シャッフル結果の山の2枚目のカードとなるようにする。
全ての山の一番上のカードを使った後は一つ目の山に戻り、
一つ目の山で現在一番上になっているカードを取ってシャッフル結果の山の(K+1)枚目のカードとする。
次に、二つ目の山で現在1枚目になっているカードを取ってシャッフル結果の山の(K+2)枚目のカードする。以下同様。
例えば、N=6 で K=3 だった場合、元のカードの順番が上から下に「ABCDEF」となっていたとすると、
上記アルゴリズムを1回実行した結果は「ECAFDB」となる。
入力されたNとKの値を元にシャッフルを何度も繰り返した時に、
カードの順番が元のカードの順番と再び同じになるために必要な最低限のシャッフル回数を求め、
色々なNとKの値の組み合わせを連続してテストできるようにしたプログラムを書け。
入力値は以下のようにプログラムに入力されるものとする：
・1行目には、行われるテストの数Tが入力される。
・次に続くT行には、NとKの二つの整数が入力される。
出力結果
・T行の結果が出力される。各行には、各テストにおいて元の順番に戻るまでに必要な最小シャッフル回数が表示される。
もし元の順番に戻ることが決して無い場合は、-1が出力される。
条件
・Kは常にNの約数
・T <= 10000
・2 <= K <= N <= 10^9
出典
GREE Programming Challenge / カードのシャッフル | Interview Street Challenges
考え方
Case: n = 6, k = 3
index: 0 1 2 3 4 5
cards: A B/C D/E F
shuffle
result: E C A/F D B
index: 4 2 0/5 3 1
ここで、n / k == 2, n - n / k == 4 なので、
for(i = 0; i < n / k; i++)
for(j = n - n / k; j >= 0; j -= n / k)
でシャッフルできる。
解答
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
#include <stdio.h>
#define MAX 100000000
int cards[MAX], temp[MAX];
int count;
int check(int n){
int i;
for(i = 0; i < n; i++){
if(cards[i] != i){
return 1;
}
}
return 0;
}
void shuffle(int n, int k){
int i, j, l;
i = 0;
for(j = 0; j < n / k; j++){
for(l = n - n / k; l >= 0; l -= n / k){
temp[i++] = cards[j + l];
}
}
for(i = 0; i < n; i++){
cards[i] = temp[i];
}
if(check(n)){
count++;
shuffle(n, k);
}
}
int main(){
int num;
int n, k;
int i, j;
scanf("%d", &num);
for(i = 0; i < num; i++){
scanf("%d %d", &n, &k);
for(j = 0; j < n; j++){
cards[j] = j;
}
count = 1;
shuffle(n, k);
printf("%d\n", count);
}
return 0;
}
なんか面白そうなことやっているのでチャレンジしてみた。
文章が長くてパッと見なにやるのか把握するのに時間がかかったけど
簡単にいえば山を分割して後ろの山から順に先頭のカードを取るだけ。
シャッフルのアルゴリズムに少し悩んだけど(n, k) = (6, 3), (6, 2)を考えたら法則が見えた。
カードの中身が何であるかは問われていないので適当に数字入れてチェックもそれで。
あとはシャッフル関数を再帰呼び出ししてカウントすればOK。
しかしもう採用が終わったからなのかわからないけど投稿してもアウトプットに出力されない。
せっかくやったのになー。
早くまともにPHPで標準入出力できないと毎回C言語で書かなきゃならんので覚えよう…！
日経ソフトウエア 2012年 04月号 [雑誌]
![日経 ソフトウエア 2012年 04月号 [雑誌]](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_usaMNk04TmWqdAu5e3Jnr3DhDCnJYsG6xyneh-p7rHSZeYpWcclGC-8Z2ukZAhjf3Igdng1nMg9JMPkP60ookYMyKbvlXiCsfgXbfRQb_XUiwdE98Wh0ul8CiIC7syBi0PY2ipI3jflg=s0-d)
