プログラミングを上達させたい

プログラミングの勉強を始めた、情報学専攻の大学院生です。モチベーション維持のため、ブログに勉強したことを書いていきます。→就職。IT全然関係ない仕事をしています

AtCoder Typical Contest #001の2問目まで

久しぶりにやっておこう、そして書いておこうと思って。

4月から社会人になったものの、IT企業でもないし、そういう部署でもないから、
全くプログラミングをしていません。
たまにはやろうということで、1ヶ月前くらいにあったAtCoder Typical Contestの初回を途中まで解きました。
3問目は、数学的な内容っぽいなぁと思い、やってないです。典型なんですね。
今回はスルーです。スルーはよくないことだと思います。僕は。


というわけで、A問題
これは、書いたことあるので、なんとか自力で解けました。

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.TreeSet;
 
 
 
public class Main {
  public static void main(String[] args) {
    InputReader sc = new InputReader(System.in);
 
    int h = sc.nextInt();
    int w = sc.nextInt();
 
    String[] sstr = new String[h];
    for(int i = 0; i < h; i++){
      sstr[i] = sc.nextStr();
    }
 
    int[][] stage = new int[h][w];
    int xgoal = -1;
    int ygoal = -1; 
    LinkedList<Integer> xqueue = new LinkedList<Integer>();
    LinkedList<Integer> yqueue = new LinkedList<Integer>();
    for(int i = 0; i < h; i++){
      for(int j = 0; j < w; j++){
        char ccc = sstr[i].charAt(j);
        if(ccc == '#'){//壁
          stage[i][j] = 0;
        }else if(ccc == '.'){//通れる
          stage[i][j] = 1;
        }else if(ccc == 's'){//スタート
          stage[i][j] = 0;
          xqueue.add(i);
          yqueue.add(j);
        }else{
          stage[i][j] = 1;
          xgoal = i;
          ygoal = j;
        }
      }
    }
 
    boolean clear = false;
    while(!xqueue.isEmpty()){
      int nowh = xqueue.poll();
      int noww = yqueue.poll();
      if(stage[nowh][noww] == 2){
        clear = true;
        break;
      }
      if(nowh >= 1 && stage[nowh-1][noww] >= 1){
        xqueue.push(nowh-1);
        yqueue.push(noww);
        if(xgoal == nowh-1 && ygoal == noww){
          clear = true;
          break;
        }
      }
      if(noww >= 1 && stage[nowh][noww-1] >= 1){
        xqueue.push(nowh);
        yqueue.push(noww-1);
        if(xgoal == nowh && ygoal == noww-1){
          clear = true;
          break;
        }
      }
      if(nowh < h-1 && stage[nowh+1][noww] >= 1){
        xqueue.push(nowh+1);
        yqueue.push(noww);
        if(xgoal == nowh+1 && ygoal == noww){
          clear = true;
          break;
        }
      }
      if(noww < w-1 && stage[nowh][noww+1] >= 1){
        xqueue.push(nowh);
        yqueue.push(noww+1);
        if(xgoal == nowh && ygoal == noww+1){
          clear = true;
          break;
        }
      }
      stage[nowh][noww] = 0;
    }
 
    if(clear){
      System.out.println("Yes");
    }else{
      System.out.println("No");
    }
 
 
 
  }
 
//nextChar を追加したよ!
 
//System.out.printf("? %d %d\n", i, j);
 
  
// LinkedList<Integer>[] setsu = new LinkedList[n];
// for(int i = 0; i < n; i++){
//   setsu[i] = new LinkedList<Integer>();
// } 
 
 //ここからテンプレ
  static class InputReader {
      private InputStream stream;
      private byte[] buf = new byte[1024];
      private int curChar;
      private int numChars;
      private SpaceCharFilter filter;
 
      public InputReader(InputStream stream) {
          this.stream = stream;
      }
 
      public int next() {
          if (numChars == -1)
              throw new InputMismatchException();
          if (curChar >= numChars) {
              curChar = 0;
              try {
                  numChars = stream.read(buf);
              } catch (IOException e) {
                  throw new InputMismatchException();
              }
              if (numChars <= 0)
                  return -1;
          }
          return buf[curChar++];
      }
 
      public String nextStr() {
        int c = next();
        while(isSpaceChar(c)){c = next();}
        StringBuffer str = new StringBuffer();
        do{
          str.append((char)c);
          c = next();
        }while(!isSpaceChar(c));
        return str.toString();
      }
 
      public char nextChar() {
        int c = next();
        while(isSpaceChar(c)){c = next();}
        char ret;
        do{
          ret = (char)c;
          c = next();
        }while(!isSpaceChar(c));
        return ret;
      }
 
      public int nextInt() {
          int c = next();
          while (isSpaceChar(c))
              c = next();
          int sgn = 1;
          if (c == '-') {
              sgn = -1;
              c = next();
          }
          int res = 0;
          do {
              if (c < '0' || c > '9')
                  throw new InputMismatchException();
              res *= 10;
              res += c - '0';
              c = next();
          } while (!isSpaceChar(c));
          return res * sgn;
      }
 
      public boolean isSpaceChar(int c) {
          if (filter != null)
              return filter.isSpaceChar(c);
          return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
      }
 
      public interface SpaceCharFilter {
          public boolean isSpaceChar(int ch);
      }
  }
}

よしよし。ただ、なんか一発でなかったりと、コツコツやることの大切さを痛感しました。

そしてB問題
こちらは、JavaでUnion Findを解いたことがなかったので、良い練習になったと思います。
解説を参考にしました。
頑張ってクラスを作りました。privateがどうとかはやってないです。何故かと言うと、よく分かんないからです。
こんな感じのコードになりました。ちなみに、繋ぎ直しはやりましたが、ランクがどうとかはやってないです(解説を参照)。

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.TreeSet;
 
class UnionFindTree{
 
//各ノードの親を保管するリスト。親がもうない場合は-1。
  private int[] ufTree;
 
  public UnionFindTree(int num){
    ufTree = new int[num];
    for(int i = 0; i < num; i++){
      ufTree[i] = -1;
    }
  }
 
  public void doUnion(int a, int b){
    if(a == b){return;}
    int aend = a;
    int bend = b;
    LinkedList<Integer> pasta = new LinkedList<Integer>();
    LinkedList<Integer> pastb = new LinkedList<Integer>();
    pasta.push(aend); pastb.push(bend);    
    while(ufTree[aend] >= 0){
      aend = ufTree[aend];
      pasta.push(aend);
    }
    while(ufTree[bend] >= 0){
      bend = ufTree[bend];
      pastb.push(bend);
    }
    if(aend == bend){
      return;
    }else if(aend > bend){
      while(!pasta.isEmpty()){
        int anode = pasta.pop();
        ufTree[anode] = bend;
      }
    }else{
      while(!pastb.isEmpty()){
        int bnode = pastb.pop();
        ufTree[bnode] = aend;
      }
    }
    //あるノードの親は、自分より小さい番号になる
  }
 
  public boolean ask(int a, int b){
    if(a == b){return true;}
 
    int aend = a;
    while(ufTree[aend] >= 0){
      aend = ufTree[aend];
    }
 
    int bend = b;
    while(ufTree[bend] >= 0){
      bend = ufTree[bend];
    }
 
    return aend == bend;
  }
}
 
 
 
public class Main {
  public static void main(String[] args) {
    InputReader sc = new InputReader(System.in);
  
    int n = sc.nextInt();
    int qnum = sc.nextInt();
    UnionFindTree u = new UnionFindTree(n);
    for(int qcount = 0; qcount < qnum; qcount++){
      int qnumber = sc.nextInt();
      int a = sc.nextInt();
      int b = sc.nextInt();
      if(qnumber == 0){
        u.doUnion(a, b);  
      }else{
        System.out.println(u.ask(a, b) ? "Yes" : "No");
      }
    }
  }
 
//nextChar を追加したよ!
 
//System.out.printf("? %d %d\n", i, j);
 
  
// LinkedList<Integer>[] setsu = new LinkedList[n];
// for(int i = 0; i < n; i++){
//   setsu[i] = new LinkedList<Integer>();
// } 
 
 //ここからテンプレ
  static class InputReader {
      private InputStream stream;
      private byte[] buf = new byte[1024];
      private int curChar;
      private int numChars;
      private SpaceCharFilter filter;
 
      public InputReader(InputStream stream) {
          this.stream = stream;
      }
 
      public int next() {
          if (numChars == -1)
              throw new InputMismatchException();
          if (curChar >= numChars) {
              curChar = 0;
              try {
                  numChars = stream.read(buf);
              } catch (IOException e) {
                  throw new InputMismatchException();
              }
              if (numChars <= 0)
                  return -1;
          }
          return buf[curChar++];
      }
 
      public String nextStr() {
        int c = next();
        while(isSpaceChar(c)){c = next();}
        StringBuffer str = new StringBuffer();
        do{
          str.append((char)c);
          c = next();
        }while(!isSpaceChar(c));
        return str.toString();
      }
 
      public char nextChar() {
        int c = next();
        while(isSpaceChar(c)){c = next();}
        char ret;
        do{
          ret = (char)c;
          c = next();
        }while(!isSpaceChar(c));
        return ret;
      }
 
      public int nextInt() {
          int c = next();
          while (isSpaceChar(c))
              c = next();
          int sgn = 1;
          if (c == '-') {
              sgn = -1;
              c = next();
          }
          int res = 0;
          do {
              if (c < '0' || c > '9')
                  throw new InputMismatchException();
              res *= 10;
              res += c - '0';
              c = next();
          } while (!isSpaceChar(c));
          return res * sgn;
      }
 
      public boolean isSpaceChar(int c) {
          if (filter != null)
              return filter.isSpaceChar(c);
          return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
      }
 
      public interface SpaceCharFilter {
          public boolean isSpaceChar(int ch);
      }
  }
}

こういうのって蓄積していくべきなんでしょうか。
でも、ちゃんとコメントいっぱい書くなりノートみたいなの作るとかしないと、後で使った時によく分かんなくなりそうですよね・・・
日々いっぱい問題解いて、統一感のあるコードを書いてたら大丈夫なんでしょうが。
迷うところです。

これから、どうしましょうか。プログラミングは続けたいんですが。
アプリ開発とかWeb開発とかみたいな方向に行くか、競技やるか、データ分析のやつやるか・・・
なんとか、なんかしようと思います。なんとかしてなんかするぞ〜!
おわり

広告を非表示にする