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

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

AtCoder Beginner Contest 109 に出ました(全完!嬉しい)

久々にリアルタイムでAtCoder出ました!
ABC109です。

開始50分で4問全完できました!とても嬉しい。
ただ今回は、4問目の解き方が分かったあとに、実装ミスや細かい解答の表現の確認ミスがあり、結構無駄な時間を消費してしまいました・・・・
競プロは「解き方分かるか」+「実装力」であることを痛感しました。よい経験です。

今回もレーティングあがるかな、ドキドキ・・・


では、解答を書いていきます。過去問やるときとかは色んな言語で解いていますが、今回は本当に少しでも高い順位を狙おうと思い、一番スムーズに書けるJavaでコードを書きました。
※A⇒B⇒C⇒Dの順で解きました

A問題

A×Bが奇数なら、C=1とすれば A×B×C も奇数になりますね。
A×Bが奇数か確かめます。

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 n = sc.nextInt();
    int m = sc.nextInt();
    if((n*m)%2==1){
 	   System.out.println("Yes");
    }else{
	    System.out.println("No");
    }
  }
 
 //ここからテンプレ
  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問題

単純に全探索しました。
ただ、String同士の比較を == でやってしまって1回WAを出してしまいました。
equals()を使います。

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 n = sc.nextInt();
    String[] strs = new String[n];
    for(int i = 0; i < n; i++){
      strs[i] = sc.nextStr();
    }
 
    boolean check = true;
    for(int i = 1; i < n; i++){
      if(strs[i].charAt(0) != strs[i-1].charAt(strs[i-1].length()-1)){
        check = false;
      }
      for(int j = 0; j < i; j++){
        if(strs[j].equals(strs[i])){
          check = false;
        }
      }
    }
 
    if(check){
      System.out.println("Yes");
    }else{
      System.out.println("No");
    }
   
 
  }
 
 //ここからテンプレ
  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);
      }
  }
}

C問題

Dが1ならもちろん全都市にいけますね。
では、2ならどうでしょうか。
もとの位置と目標の都市との距離が2の倍数ならいけますね。
全都市に行けるかを考えると、
『Dがnのとき、各都市と元の位置の距離が全部nの倍数ならOK』
⇒『Dがnのとき、nが"各都市と元の位置の距離の差"の約数ならOK』
となります。
そしてこのDが最大になるのは
『"各都市と元の位置の差"たちの最大公約数』
です。
いつものテンプレに、下記のように最大公約数を求める関数を追加しました。

static int gcd (int a, int b) {return b>0?gcd(b,a%b):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 n = sc.nextInt();
    int x = sc.nextInt();
    int[] nums = new int[n];
    for(int i = 0; i < n; i++){
      nums[i] = Math.abs(sc.nextInt() - x);
    }
 
    int ans = nums[0];
 
    for(int i = 1; i < n; i++){
      ans = gcd(ans, nums[i]);
    }
 
    System.out.println(ans);
 
   
 
  }
  static int gcd (int a, int b) {return b>0?gcd(b,a%b):a;}
 
 //ここからテンプレ
  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);
      }
  }
}

D問題

C問題までで17分ほど、そこからD問題を解くのに30分以上かかりました。
やはり自分が全力を出してギリギリ解けるちょうどいいレベルがDなんだと思います。


全探索は間に合わないので、かってにこっちで手順を指定すればいいのでは?と思いました。
ということで、『左上から順の下記のような順番でチェック』していき、
f:id:frfrfrfr:20180908222837j:plain
そこが奇数枚になっていれば、『右か下に移すのみ』に制限することにしました。
そして、『移す先は"できれば"奇数(=奇数がなくても移すは移す)』としました。
調べる順番も操作も制限したわけです。

ただ、これは恐らく最大化としては問題ないハズ・・・。
・最大化するやり方の、操作の順を変えても結果は変わらないこと
・『左か上に1枚移す』のを『右か下に -1枚移す』と読み替えられること
・偶奇しか気にしていないこと
から、厳格な証明もできるのでは・・・?
厳格な証明はもちろんしていませんが、感覚的に間違いなさそうだという確信があったため、この解き方で実装開始。

行と列での凡ミスや、出力ミス(座標が0からじゃなく1からだった)もありましたが、開始後50分で無事解けました!

『左上から順に読む』の実装をラクしすぎて、計算量が増えて、実行時間が1931 msと制限ギリギリになってしまいました・・・(笑)
コードはこんな感じです。

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(); //h
    int w = sc.nextInt(); //w
 
    int[][] table = new int[h][w];
    for(int i = 0; i < h; i++){
        for(int j = 0; j < w; j++){
            table[i][j] = sc.nextInt();
        }
    }
 
    int count = 0;
    String[] anss = new String[h*w];
 
    for(int sum = 0; sum < h + w - 1; sum++){
        for(int i = 0; i < h; i++){
            for(int j = 0; j < w; j++){
                if(i + j != sum){continue;}
 
                if(table[i][j] % 2 == 1){
                    count++;
                    if(i < h - 1 && table[i+1][j] % 2 == 1){
                        table[i+1][j]++;
                        anss[count-1] = String.valueOf(i+1)+" "+String.valueOf(j+1)+" "+String.valueOf(i+2)+" "+String.valueOf(j+1);
                    }else if(j < w - 1 && table[i][j+1] % 2 == 1){
                        table[i][j+1]++;
                        anss[count-1] = String.valueOf(i+1)+" "+String.valueOf(j+1)+" "+String.valueOf(i+1)+" "+String.valueOf(j+2);                        
                    }else if(i < h - 1){
                        table[i+1][j]++;
                        anss[count-1] = String.valueOf(i+1)+" "+String.valueOf(j+1)+" "+String.valueOf(i+2)+" "+String.valueOf(j+1);
                    }else if(j < w - 1){
                        table[i][j+1]++;
                        anss[count-1] = String.valueOf(i+1)+" "+String.valueOf(j+1)+" "+String.valueOf(i+1)+" "+String.valueOf(j+2);                        
                    }else{
                        count--;
                    }
                }
            }
        }
    }
/*
    int count = 0;
    String[] anss = new String[n*m];
 
    anss[count-1] = String.valueOf(j)+" "+String.valueOf(i-j)+" "+String.valueOf(j+1)+" "+String.valueOf(i-j);                           
    */
    System.out.println(count);
    for(int i = 0; i < count; i++){
        System.out.println(anss[i]);
    }
    
   
 
  }
 
 //ここからテンプレ
  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);
      }
  }
}


というわけで、今回もなんとか全完できました。
レーティングどうなるかなー、早く1200に到達したい!水色!
現在1063の緑色です。
引き続き頑張ります!


P.S.(同日0:00追記)
レーティング、1063⇒1116になってました。
グッと上げるにはARCの参加も必要なのかもしれませんね。
そしてパフォーマンスが前回は1600(ABCの上限)だったのが、今回は1415でした。落ちてる・・・
最近勉強してないので、少しやろうかな。やるべきだ。
以上。


P.S.2
解説記事でD問題見たんですが、
・最終的に、全部偶数or1個奇数で他全部偶数
まで持って行けるんですね・・・!
ちなみに解説記事の方では、僕のやり方とは違うやり方でした。
ただ、「勝手に見ていく手順を決める」点では同じでした。
奥深い問題ですね。