読者です 読者をやめる 読者になる 読者になる

初投稿: Mujin Programming Challenge 2017 B.Row to Column

はじめに

初投稿です。主にアルゴリズムの紹介や解いてみたプログラミングコンテストの問題の紹介をしていきます! 言語はJavapythonが主です。将来的にははてなブログではなく、自作のwebに移行したいなとか思っています。自分の拙いコードをあげるのは恥ずかしいことですが、他の方に見てもらうことで指摘を頂き成長できると思いブログを始めました!宜しくお願いしますm(__)m

Mujin Programming Challenge

At Coderで行われたMujin Programming Challengeに挑戦した結果、惨敗でした。2時間もあって1つも解けませんでした。。。悔しいです。解けたと思ったんですけどね。。。2問目のB. Row to Columnに全2時間をかけて挑み、残り10分のところでコードを提出してみたのですが、WA(Wrong Answer)となりました。なぜだーーーとなって終了。。。幸いにも部分点は貰えたようなので方向性は間違っていないようです。以下で私の思考回路と、コードを紹介します。今度、見事acceptされた方のコードを分析してみたいと思います!

思考回路

  • まず真っ白だと100%無理。問題のサンプルにもあった。
  • 黒マスが1つだけの時、いけないんじゃね -> いけた。
  • 試行錯誤する 。
  • 横全てが黒になれば、全てが黒になっていない列数分操作をすれば終わりみたい。-> つまり最短で1行全て黒にする方法を探すのと同義
  • 1番たくさん黒マスがある行を探す。(maxBlackHorizontal)
    • この時すでに全てが黒の行があれば、サイズから1行全て黒マスの数(howManyVertical)を引いた操作数で終わる。
    • また、各行のうち最大の黒マス数が0のとき。つまり真っ白ということなので、-1を出力。
    • 他の場合、つまり、最大の黒マス数を所有する行に1つ以上サイズ未満の白マスがある。
      • その行数をRとした時に、Rの列に1つでも黒マスがあれば( hasBlackVertical)、1操作でR行の白マス1つずつ潰せるので、白マスの個数分の操作を行えば、R行が真っ黒になる!
      • R列に1つもない場合、1操作でその列に黒マスを持っていき、その後にR行の白マスの個数分の操作を行えば、R行が真っ黒になる!(つまり上記よりも+1操作数が増える)
      • 1行を真っ黒にしてしまえば、それまでにかかった操作数+サイズ-(1行全て黒マスの数)で真っ黒になる!

という思考回路でコードを書いてみました。解説を見てみるとロジックは間違っていないはず。ではなぜWAとなったんだろう。

Code

恥ずかしいですが、私が実際に書いたコードを載っけます。無駄なところ沢山あるでしょうが、何方かご指摘してくれると嬉しいです!

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Scanner;
 
public class Main {
    //各行を調べて、一番多く黒色のマスがある行数と、その黒色のマス数をリストにして出力
    public static ArrayList<Integer> maxBlackHorizontal(int[][] array){
        HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
        int size = array.length;
        int counter = 0;
        // 以下のfor loopで各行の黒マスの数をkeyに、行数をvalueにしてmapに格納
        for (int i = 0; i <size ; i++) {
            for (int j = 0; j < size; j++) {
                if (array[i][j]==1) {
                    counter++;
                }
            }
            map.put(counter, i);
            counter = 0;
        }
        //最大の黒マスの数を取得
        int max  = Collections.max(map.keySet());
        ArrayList<Integer> max_indices = new ArrayList<Integer>();
        max_indices.add(max);
        //黒マス数がmaxのやつをmax_indicesにいれていく。
        for(Integer i : map.keySet()) {
            if(i == max){
                max_indices.add(map.get(i));
            }
        }
        //max_indicesは1つめの値が1行がもつ最大の黒マス数で、2つ移行はその行数。
        return max_indices;
    }
    
    // いくつ黒マスで埋まっている列があるかを調べ、その数を出力。
    public static int howManyVertical(int[][] array){
        int size = array.length;
        int counter = 0;
        for (int i = 0; i <size ; i++) {
            for (int j = 0; j < size; j++) {
                if (array[j][i]!=1) {
                    break;
                }
                if(j == size-1){
                    counter ++;
                }
            }
        }
        return counter;
    }

    // 指定した列に黒マスが1つでもあるかどうかを調べ、booleanで出力。
    public static boolean hasBlackVertical(int[][] array, int index){
        int size = array.length;
            for (int j = 0; j < size; j++) {
                if (array[j][index]==1) {
                    return true;
                }
            }
        return false;
    }
    
    public static void main(String[] args) {
        // inputからマス目を作成。1が黒色で、0が白色。
        Scanner s = new Scanner(System.in);
        int size = s.nextInt();
        int[][] square = new int[size][size];
        for (int i = 0; i < size; i++) {
            String line = s.next();
            for (int j = 0; j < size; j++) {
                if (line.charAt(j) == '#') {
                    square[i][j] = 1;
                }
            }
        }

        ArrayList<Integer> max_indices = maxBlackHorizontal(square);
        int maxBlackHorizontal = max_indices.get(0);
        // すでに真っ黒な行があるとき
        if(maxBlackHorizontal == size){
            System.out.println(size - howManyVertical(square));
        }else if(maxBlackHorizontal ==0){
            // 真っ白の時
            System.out.println(-1); 
        }else{
            boolean flag = false; 
            for (int i = 1; i < max_indices.size(); i++) {
                if(hasBlackVertical(square, max_indices.get(i))){
                    System.out.println(size - maxBlackHorizontal+ size - howManyVertical(square));
                    flag = true;
                    break;
                }
            }
            if(!flag){
                System.out.println(size - maxBlackHorizontal+ 1 + size - howManyVertical(square));
            }
        }       
    }
 
}