AtCoder Grand Contest 058 に参加しました - プログラミングを上達させたい

久々に Rated なコンテストに参加しました。しました達郎
atcoder.jp

しかも Grand Contest です。Rated 対象は水色以上という、自分以上の人を対象としたコンテスト。3 時間みっちりと時間が取れそうだったので、自分の立ち位置を思い知ろうと意気込んで参加しました。
配点は 400-700-900-1000-1400-2000 だったので、
・400 点の A 問題を迅速に解き
・残った時間で B 問題と向き合う（今まで解けたことのない配点）
という目標を立てて参加しました。

結果は、
・A 問題に正解したのが 99 分 47 秒（経過時間 74 分 47 秒＋ペナルティ 5 分 × 5 回）
・B 問題はサンプル 2 つを AC できたが、ほとんど WA or TLE という提出
で終わりました。A 問題にかなり時間がかかってしまいました・・・

とりあえず、解けた A 問題の説明と、B 問題の思考の過程を残します。B 問題、サンプルに正解して舞い上がっていただけに悔しい。ちなみにどちらも Java で書きました。

A 問題

1 〜 2n までを並び替えた数列が与えられて、それを最終的にジグザグ数列にしたい。
※ジグザグ数列・・・P(1) < P(2) > P(3) < ... となる数列。
できる操作は、「隣り合う 2 つの数を交換すること」で、この操作を n 回以内行ってジグザグ数列にせよ、とのこと。

①先頭から 2 要素ずつ見ていって交換すべきならする → ダメ
②作戦①でダメだった場合、後ろから同じようにやる→ダメ
③注目するのを 2 要素から 3 要素に増やす→ AC
となりました。かなり手こずってしまいました。
証明などもせず、積み重なる WA と RE に焦って提出した③のコードが無事に通りました。

通ったものの・・・というモヤつきが残っていましたが、解説もこの解き方で、ちゃんと論理も通っていました。こういう「目標からの遠さを減らしていく」とか、ふんわりした指定を定量的に評価する方法を考えられたら、序盤の WA や RE が減らせたなぁと反省です。

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[] nums = new int[2 * n];
    int[] keepnums = new int[2 * n];
    int[] swappedArray = new int[2 * n];
    for(int i = 0; i < 2 * n; i++){
      nums[i] = sc.nextInt();
      swappedArray[i] = nums[i];
      keepnums[i] = nums[i];
    }

    int changecount = 0;
    int[] changelog = new int[n];

    for(int i = 0; i < 2 * n - 2; i++){
      if(i % 2 ==0){
        if(nums[i] > nums[i + 1]){
          if(nums[i] < nums[i + 2]){
            swappedArray[i] = nums[i + 2];
            swappedArray[i + 2] = nums[i];
            nums[i + 2] = nums[i + 1];
            nums[i + 1] = swappedArray[i];
            changelog[changecount] = i + 1;
            changecount++;
          }else{
            swappedArray[i] = nums[i + 1];
            swappedArray[i + 1] = nums[i];
            nums[i + 1] = nums[i];
            changelog[changecount] = i;
            changecount++;
          }
        }
      }else{
        if(nums[i] < nums[i + 1]){
          if(nums[i] > nums[i + 2]){
            swappedArray[i] = nums[i + 2];
            swappedArray[i + 2] = nums[i];
            nums[i + 2] = nums[i + 1];
            nums[i + 1] = swappedArray[i];
            changelog[changecount] = i + 1;
            changecount++;
          }else{
            swappedArray[i] = nums[i + 1];
            swappedArray[i + 1] = nums[i];
            nums[i + 1] = nums[i];
            changelog[changecount] = i;
            changecount++;
          }
        }
      }
    }
    if(nums[2 * n - 2] > nums[2 * n - 1]){
      changelog[changecount] = 2 * n - 2;
      changecount++;
    }


    System.out.println(changecount);
    if(changecount > 0){
      for(int i = 0; i < changecount; i++){
        System.out.print(changelog[i] + 1);
        if(i + 1 < changecount){
          System.out.print(" ");
        }else{
          System.out.println("");        
        }
      }
    }
 
 
 
 
  }
 
 //ここからテンプレ
  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 問題

数え上げ問題。順列の最大値で分割して・・・というのを繰り返せばできる？と思ったが、シンプルな例でも試すことができず、別の解法を考えることに。
なんかこう、階段の図で、右と上だけに行けて、みたいにやればどうか・・・？と色々やった結果、下記のような図にして数えていけば、サンプルケースで正解となりました。

最後に一番右列の数字を足して、このケースだと 11 が答えになります。
実装にとても手間がかかりましたが、この考え方で答えを出すコードを書き上げ、提出しました。開始から 2 時間 45 分経過、残りでできるのは微修正のみ、というところ・・・！
しかし、結果はほとんどのケースで WA or TLE でした。いや TLE もあるんかい。

ということで、ここでタイムアップとなりました。

B問題の解説を見てみると DP で解ける、とのこと。
ほんま DP 、DP って・・・便利どすなぁほんまに

レーティング変化

パフォーマンスは1165、新レーティングは1307（15ダウン）でした。
あまり悪いパフォーマンスではなかったですが、どうやら A 問題を一発で通せていたらパフォーマンスは 1600 超えだったもよう。
最近少し Project Euler は解いていたものの、制限時間とノーミスを意識しながら問題を解いてはいなかったのが出たなぁという反省です。
とりあえず DP やりましょうね。