昨日のCodeFestival内であったコンテンツの1つにチーム対抗早解きリレーというものがありました。
CodeFestival本選の順位毎にチーム分けし(10人ずつの20チーム)、相談して解く、というものでした。
「それだとチームの強い人数人が解くのを眺めてるだけになるのでは？」と思うかもしれませんが、問題が10問あり、1人が1問ずつ『実装する』というルールでした。
つまり、一番強い1人が10問全ての解法を考えたとしても、実装できるのは1人1問なので、他の9問は他の人に説明して、実装してもらうしかないというわけです。
また、相談ゾーンと実装ゾーンは離れていて、しかも実装ゾーンには1人しかいてはならない、と、結構徹底されていました。
ただし、実装ゾーンに行ったあとにやっぱり分からなくなったりしたら、相談ゾーンに戻ってもう一度話を聞く、とかはありでした。
なかなか文章だけで説明するのは難しいですが、解いた問題の解き方のメモがメインなので、この辺にしておきます。
さて、早解きリレーの問題はコチラから見られます。
一応、以下には問題の概略も書くようにします。
僕は本番ではA問題の解法を考えるのと、H問題を(強い人が紙に書いたコードを頑張って暗記して)実装する、しかやらなかったので、とりあえず勉強も兼ねてやってみました。解けない問題は後回しで、とりあえずパパっと解けた分だけ。
問題A。入力n(<=100)以下の素数かつ偶数の数字はいくつあるか？という問題。問題文をゆっくり読み、ゆっくり考えれば、簡単な問題です。素数かつ偶数なのは2しかないですもんね。
import java.util.*;
public class Main {
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int answer;
if(n <= 1){
answer = 0;
}else{
answer = 1;
}
System.out.println(answer);
}
}問題B。2つの数字の大小を比較するという問題。これも簡単です。Aより簡単？
import java.util.*;
public class Main {
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
if(n >= m){
System.out.println("Congratulations!");
}else{
System.out.println("Enjoy another semester...");
}
}
}問題C。ある音楽ゲームにおいて、『順番に出てくる音符の数がn、そして終わったときの最大コンボ数がmであったとき、ミス回数としてありうるもののうち最小のものはなにか』という問題。『m回成功1回ミス』とすると、どんなときでも最大コンボがmかつミスが最小ですね。よって次のようになります。schemeで解いた理由は特にありません。
(define n (read)) (define m (read)) (define answer (quotient n (+ m 1))) (display answer) (newline)
問題D。『n×nの盤上で行われるゲームがあり、初期配置として一番上の行の全マスにプレイヤーXの駒が、一番下の行の全マスにプレイヤーYの駒がある。Xの駒は真下に、Yの駒は真上にしか進めない。また、将棋のように相手のマスをとることができる。今の盤面の状況をみて、XとYのどちらが先行だったか判定せよ』という問題でした。初め読んだときは、こんなん解けるんか？と思ったのですが、『試合は始まったばかりでどちらも相手の駒を取っていないので、』というのを見落としてました。問題をゆっくり読むのは大切です。
import java.util.*;
public class Main {
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
String[] banmen = new String[n];
for(int i = 0; i < n; i++){
banmen[i] = sc.next();
}
int turnx = 0;
int turny = 0;
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(banmen[j].charAt(i) == 'X'){
turnx += j;
}
}
for(int j = n-1; j >= 0; j--){
if(banmen[j].charAt(i) == 'Y'){
turny += (n - 1) - j;
}
}
}
if(turnx == turny){
System.out.println("Impossible");
}else if(turnx > turny){
System.out.println('X');
}else{
System.out.println('Y');
}
}
}
問題E。
『w×Hの盤面の各マスに、空白か、数字が書かれている。各数字のペアを考え、マンハッタン距離が最大であるペアのうち、好きなものを選び、そのペアのうち大きい方の数のところに2数の和を、小さい方の数のマスは空白にかえる、という操作を行う。それを繰り返すと最後は数が1つだけ残ることになる。最後の数が最大になるようにした場合、その最大の数はいくらか。』という問題。
難しそうに書いてありますが、実はどのようにやっても、最後に残る数字は、スタート時に盤上にある数字の和になりますね。ひっかけ？です。本選の問題Dもそういうのでしたね。こういうのは面白いので好きです(解けなかったときは相当腹が立つと思います)。
import java.util.*;
public class Main {
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int h = sc.nextInt();
int w = sc.nextInt();
String[] banmen = new String[h];
for(int i = 0; i < h; i++){
banmen[i] = sc.next();
}
int answer = 0;
for(int i = 0; i < h; i++){
for(int j = 0; j < w; j++){
char elem = banmen[i].charAt(j);
if(elem == '.'){
continue;
}else{
answer += (int)elem - 48;
}
}
}
System.out.println(answer);
}
}
説明の都合上、問題Hから。
『ある区間長nとアクセス数mとm回それぞれのアクセスされた時間が与えられる。連続したn秒のうち、最も多くのアクセスが含まれる区間内のアクセス数はいくらか。』という問題。
いわゆる、『しゃく取り法』というやつですね。知っていてよかった。これは、問題中で現れるnの大きさに依存せず、mにのみ依存するように設計されているアルゴリズムです(間違ってたら教えて下さい)。
import java.util.*;
public class Main {
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int[] access = new int[m];
for(int i = 0; i < m; i++){
access[i] = sc.nextInt();
}
int left = 0;
int right = 0;
int nowmax = 0;
while(right < m){
if(access[right] - access[left] <= n){
if(right - left + 1 > nowmax){
nowmax = right - left + 1;
}
right++;
}else{
left++;
}
}
System.out.println(nowmax);
}
}
そして最後に問題G。
『整数mと、n個の数字が与えられる。n個の数字のいくつかを重複なく足したもののうち、m以上となっている最小のものはいくらか。また、m以上となる組み合わせがない場合は-1を出力せよ』という問題でした。
これは強い人に解き方を教えてもらい(というかコードを紙に書いてもらい)、暗記してそれをそのままPCに打ち込んで解いた問題です。
つまり本番では、解いたわけではありません。ただ、頑張って暗記したおかげで(笑)、コードの内容は完全に覚えたので、色々考えていたら理解できました。やはり、本で読むより他の人に教えてもらう方が理解が早いですね(教えてもらったかというとあやしいかもですが)。
これは『ナップザック問題』という有名な問題の類題だそうです。名前は聞いたことあるけど(蟻本をペラペラめくったときに見た)、ちゃんとやったことはありませんでした。ちょうど良い機会なので、ここに僕なりの説明を書いて、理解を確認したいと思います。
まずはコードから(つまり、僕が暗記したコードです)。
import java.util.*;
public class Main {
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int[] a = new int[n];
for(int i = 0; i < n; i++){
a[i] = sc.nextInt();
}
int[] dp = new int[20050];
dp[0] = 1;
for(int i = 1; i < 20050; i++){
dp[i] = 0;
}
for(int i = 0; i < n; i++){
for(int j = m; j >= 0; j--){
dp[j+a[i]] |= dp[j];
}
}
int answer = -1;
for(int i = m; i < 20050; i++){
if(dp[i] == 1){
answer = i;
break;
}
}
System.out.println(answer);
}
}これのdp[]という配列は最終的に、
ぴったり音量iに出来る組み合わせがある -> dp[i] = 1 ぴったり音量iに出来る組み合わせがない -> dp[i] = 0
となります。
また、どの目覚まし時計も使わない場合、音量0が達成できるので、初めの時点で
dp[0] = 1
とするのを忘れないようにします(「ここは絶対に忘れないで下さいね」と本番でも強く言われました)。
そして、dp[]という配列を更新していく2重ループの部分は、こんな感じになります。
for(int i = 0; i < n; i++){
for(int j = m; j >= 0; j--){
dp[j+a[i]] |= dp[j];
}
}ここで出ている
|=
というのは、『+=』とかと同じ使い方ですね。ここではdpはint型なのでこういう使い方が出来るか疑問に思うかもしれませんが、ビット演算として考えると(そしてdpが1か0しか入っていないことも加えると)、
dp[j+a[i]] |= dp[j];
は
if(dp[j] == 1){
dp[j+a[i]] = 1;
}と同じ意味になります。しかし、|=を使った方が確かにスマートですね。強い人のコードは美しい。
さてさて、アルゴリズム部分の話に移ります。このdpを処理する2重ループ内の挙動について、i=0とi=1の時の実行のみをまとめてみました。
汚いですが画像を載せます。
分かるでしょうか・・・？分かりにくくてすみません。
この2重ループが終わると、dp[]の内、目覚まし時計の一部(0個や全部も含む)を1回ずつ使ったときの合計音量のところだけ1になっています。なるほど、確かにこれだと解けますね。
しかし、1つ疑問が残りました。それは、
この2重ループで計算量が小さくなるのは分かるけど、それだったら別に内側のforはfor(int j = 0; j <= m; j++)にしてもいいんじゃないの？
というものです。
でも、本番では『このループは絶対mからはじめて減らしていくように書いて下さいね！』と強い人に強く言われたので、多分このような変更をしてはダメな理由があるハズだ、と考え、色々試してみたら、やっとこさ分かりました。自分なりに図を2つ書いてみました。同じ内容の図です。
グジャグジャ書いてますが、つまり内側のforを"j=0;j<=m;j++"に変更してしまうと、『同じ目覚まし時計を複数個使った場合も考えてしまうからダメ』ということです。
自分はこれでちゃんと納得して理解できました。よしよし。
また、重複使ってよいという問題では、ループを下側からやっていくように書けばOKということですね(多分)。すごい、楽しいぞプログラミング。
というわけで、解けた問題の説明は以上です。
問題F(連結グラフ内に1個だけ含まれるループの長さを求める問題)は解き方を説明してもらって理解したのですが、Javaで隣接リストを作るやり方がまだ分かっていません。調べたらすぐ分かる(と期待している)ので、そのうち調べようと思っています。C++ではpush back?というのを使うそうです。
すぐにやるの、面倒ですよね。こういう風に、向上に対する焦りがないから弱いんでしょうけど。
CodeFestivalのチーム早解きリレーでは、上に書いたように2問にしか関われなかったのですが、強い人がどのように問題を解いているかが間近で見られたのがよかったです。
また、僕に暗記するコードを説明するときも、よく間違うポイントをちゃんと説明するあたり、天才的な人が上位で戦っているというのではなく、ちゃんと勉強した人達が真剣にやって戦っている(もちろん頭も良いでしょうけど)のだと実感できたのがよかったです。
これによって、また少しやる気が出ました。
というわけでチーム対抗早解きリレーの復習(一部)は終わりです。
次の記事は何になるか分かりません。ただ、あまり間が空かないようにしたいと思います。以上です。
