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

情報学専攻の大学院→放送局でCMの営業など@大阪→舞台俳優&IT営業@東京

AtCoderBeginnerContest#017

久々の更新です。
今日はABCがあり、こういう機会には書かねばもう書かなくなっちゃいそうだな、ということで更新。
別に大した発見があったとかではないです。

あぁ、強いて言うなら、他の方のコードを参考にして、Javaの入出力を早くするようにしました。
それはテンプレ?みたいな感じでコードに入っています。
これについては、この記事の最後で書きます。


とりあえず、今日時間中に解けたA〜C問題までを、テンプレ部分は抜きで書きます。

AtCoderBeginnerContest#017

まずは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;
 
public class Main {
  public static void main(String[] args) {
    InputReader sc = new InputReader(System.in);
 
    int n = sc.nextInt();
    int a = sc.nextInt();
    int m = sc.nextInt();
    int b = sc.nextInt();
    int l = sc.nextInt();
    int c = sc.nextInt();
    System.out.println(n / 10 * a + m / 10 * b + l / 10 * c);
 
  }
 
 //これ以降にテンプレがあります(後述)

次に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;
 
public class Main {
  public static void main(String[] args) {
    InputReader sc = new InputReader(System.in);
 
    String str = sc.nextStr();
    boolean chokugo = true;
    int nowchumoku = str.length() - 1;
    while(nowchumoku >= 0){
      if(nowchumoku >= 1){
        if(str.charAt(nowchumoku) == 'o' || str.charAt(nowchumoku) == 'k' || str.charAt(nowchumoku) == 'u'){
          nowchumoku--;
          continue;
        }
        if(str.charAt(nowchumoku - 1) == 'c' && str.charAt(nowchumoku) == 'h'){
          nowchumoku -= 2;
          continue;
        }
      }else{
        if(str.charAt(nowchumoku) == 'o' || str.charAt(nowchumoku) == 'k' || str.charAt(nowchumoku) == 'u'){
          nowchumoku--;
          continue;        
      }
    }
    chokugo = false;
    break;
  }
  System.out.println(chokugo? "YES" : "NO");
}

最後の行にある、三項演算子(chokugo? "YES" : "NO")が使えるようになったのは最近の一番の上達です。

そしてなんとか満点がとれたC問題
満点が101点で、部分点として、30、100も設定されていました。
はじめは部分点狙いでいったので、30、100、101の全ての点の提出がありました。
せっかくなので、出した順に紹介します。

30点のやつ。単純に全組み合わせを試すだけです。

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.LinkedList;
 
public class Main {
  public static void main(String[] args) {
    InputReader sc = new InputReader(System.in);
 
    int n = sc.nextInt();
    int m = sc.nextInt();
 
    int[] lownum = new int[n];
    int[] highnum = new int[n];
    int[] point = new int[n];
    for(int i = 0; i < n; i++){
      lownum[i] = sc.nextInt();
      highnum[i] = sc.nextInt();
      point[i] = sc.nextInt();
    }
 
    int pattern = 1;
    for(int i = 0; i < n; i++){
      pattern *= 2;
    }
 
    int maxscore = 0;
    while(pattern >= 0){
      int nowscore = 0;
      int nowbit = pattern;
      boolean[] houseki = new boolean[m];
      for(int i = 0; i < m; i++){
        houseki[i] = false;
      }
      for(int i = 0; i < n; i++){
        if(nowbit % 2 == 1){
          nowscore += point[i];
          for(int j = lownum[i] - 1; j < highnum[i]; j++){
            houseki[j] = true;
          }
        }
        nowbit /= 2;
      }
      pattern--;
      if(nowscore > maxscore){
        boolean allget = true;
        for(int i = 0; i < m; i++){
          if(!houseki[i]){
            allget = false;
            break;
          }
        }
        if(!allget){
          maxscore = nowscore;
        }
      }
    }
    System.out.println(maxscore);
  }

100点のやつ。やり方はあとで説明します。

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.LinkedList;
 
public class Main {
  public static void main(String[] args) {
    InputReader sc = new InputReader(System.in);
 
    int n = sc.nextInt();
    int m = sc.nextInt();
 
    int[] lownum = new int[n];
    int[] highnum = new int[n];
    int[] point = new int[n];
    for(int i = 0; i < n; i++){
      lownum[i] = sc.nextInt();
      highnum[i] = sc.nextInt();
      point[i] = sc.nextInt();
    }
 
    int pattern = 1;
    for(int i = 0; i < n; i++){
      pattern *= 2;
    }
 
    int maxscore = 0;
    for(int notget = 1; notget <= m; notget++){
      int nowscore = 0;
      for(int i = 0; i < n; i++){
        if(highnum[i] < notget || notget < lownum[i]){
          nowscore += point[i];
        }
      }
      if(nowscore > maxscore){
        maxscore = nowscore;
      }
    }
 
    System.out.println(maxscore);
  }

101点(=満点)のやつ。同じく、やり方はあとで説明します。

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.Comparator;
 
class Iseki{
  int lownum;
  int highnum;
  int point;
}
 
class lowComp implements Comparator{
  public int compare(Object o1, Object o2){
    Iseki i1 = new Iseki();
    Iseki i2 = new Iseki();
    i1 = (Iseki)o1;
    i2 = (Iseki)o2;
    return i2.lownum - i1.lownum;
  }
}
class highComp implements Comparator{
  public int compare(Object o1, Object o2){
    Iseki i1 = new Iseki();
    Iseki i2 = new Iseki();
    i1 = (Iseki)o1;
    i2 = (Iseki)o2;
    return i1.highnum - i2.highnum;
  }
}
 
public class Main {
  public static void main(String[] args) {
    InputReader sc = new InputReader(System.in);
 
    int n = sc.nextInt();
    int m = sc.nextInt();
    Iseki[] lowsort = new Iseki[n];
    Iseki[] highsort = new Iseki[n];
    for(int i = 0; i < n; i++){
      Iseki nowIseki = new Iseki();
      nowIseki.lownum = sc.nextInt();
      nowIseki.highnum = sc.nextInt();
      nowIseki.point = sc.nextInt();
      lowsort[i] = nowIseki;
      highsort[i] = nowIseki;
    }
 
    Arrays.sort(lowsort, new lowComp());
    Arrays.sort(highsort, new highComp());
 
    int[] underhere = new int[m + 1];//underhere[i] には、i番目以下の宝石を入手したときの合計が入る
    int[] overhere = new int[m + 1];//overhere[i] には、i + 1番目以上の宝石を入手したときの合計が入る
    underhere[0] = 0;
    overhere[m] = 0;
 
    int nowindex = 0;
    for(int i = 0; i < n; i++){
      int nexthigh = highsort[i].highnum;
      if(nowindex == nexthigh){
        underhere[nowindex] += highsort[i].point;
      }else{
        int keepnum = underhere[nowindex];
        for(int j = nowindex + 1; j < nexthigh; j++){
          underhere[j] = keepnum;
        }
        underhere[nexthigh] = keepnum + highsort[i].point;
        nowindex = nexthigh;
      }
    }
    if(nowindex < m){
      int keepnum = underhere[nowindex];
      for(int i = nowindex + 1; i <= m; i++){
        underhere[i] = keepnum;
      }
    }
 
    nowindex = m;
    for(int i = 0; i < n; i++){
      int nextlow = lowsort[i].lownum - 1;
      if(nowindex == nextlow){
        overhere[nowindex] += lowsort[i].point;
      }else{
        int keepnum = overhere[nowindex];
        for(int j = nowindex - 1; j > nextlow; j--){
          overhere[j] = keepnum;
        }
        overhere[nextlow] = keepnum + lowsort[i].point;
        nowindex = nextlow;
      }
    }
    if(nowindex > 0){
      int keepnum = overhere[nowindex];
      for(int i = nowindex - 1; i >= 0; i--){
        overhere[i] = keepnum;
      }
    }
 
    int maxscore = 0;
    for(int notget = 1; notget <= m; notget++){
      if(maxscore < underhere[notget - 1] + overhere[notget]){
        maxscore = underhere[notget - 1] + overhere[notget];
      }
    }
 
    // for(int i = 0; i <= m; i++){
    //   System.out.print(i);
    //   System.out.print(":");
    //   System.out.println(overhere[i]);
    // }
 
    System.out.println(maxscore);
  }

解けたのは結構嬉しかったです。

100点のやつは、notget番目の宝石を取らないようにした場合のスコアを計算し、どれが最大かを見つけるものです。
101点の方は、それを高速にやろうとしたものです。
具体的には (遺跡で見つかる宝石の一番小さい番号をlownum、一番大きい番号をhighnumとします。コードの中の表記もそうなっています)、
・遺跡をhighnumの小さい順に並べる。
・それを用いると、番号がi以下の宝石のみで最大何点取れるかを、一回通り見るだけでできる。
・同じように、番号がi以上の宝石のみで最大何点取れるかを、lownumの大きい順に並べた配列を用いて調べる。
・上のようにしたあとは、
notget番目を取らないときの最大点数=番号が(notget-1)以下の宝石での最大点数 + 番号が(notget+1)以上の宝石での最大点数
 で簡単に計算できる。
という感じです。これだと、遺跡の数がnとしたら、n*log(n)で解けてるんですかね。ソートのところに一番時間がかかってます。


ただ、公開された解説スライドを見ると別のやり方(多分考え方は同じ)でした。
どっちのがいいんでしょうね。いもす法で解けば簡単、みたいに書いてあったと思うんですが、パッと理解できませんでした。

僕は微妙な実力のまま学ばずに問題を解いてきたので(そして自分の手が出ない問題は早々に諦める)、解き方がエレガントじゃないまま固まってきてるんですよね。その分、初心者にも分かりやすめのコードなのかなぁとか思っていますが。
ただ自分が理解さえできれば、エレガントなコードの方がわかりやすく、そして打つのも簡単、となるハズなので、なんとかしていきたいです。
でも、なかなかやる気出ないんですよね。
自分の中の、「汚くても、時間がかかっても解けたら同じ」みたいな考えが邪魔してきます。むむぅ


あと、D問題は時間内で解けなかったんですが(追加で30分あったりしても解けなかったと思います)、これは高等なデータ構造もアルゴリズムもなく、いわば僕の知識を組み合わせれば解ける問題だったと思うので、だいぶ悔しいです。
こういうのを解くのが競技プログラミングの醍醐味だと思っているので、ちゃんと解きたいところです。


最後に、テンプレの話をします。
上で紹介したコードの後には、全て次のコードが付いています。

 //ここからテンプレ
  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 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);
      }
  }
}

つまり、テンプレート(=解き始める段階でのコード)の全体は次のようになります。

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.LinkedList;


 
public class Main {
  public static void main(String[] args) {
    InputReader sc = new InputReader(System.in);
 

  }
 
  
 

 //ここからテンプレ
  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 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);
      }
  }
}

これでやると、大分早くなりました。
他の方のコードを参考に(どなたのかは忘れました、申し訳ございません)、自分でnextStr()とかを付けてみて、作成しました。

以上です。