久々にRatedなやつに出ました。
転職するんですよ、転職。放送局(テレビ・ラジオCMの営業をやってました)に勤めてたんですけど、舞台俳優になるため会社を辞めて上京しました。一体オレっちの人生、どうなっちゃうの〜〜〜！？？
ちなみに次に出演する予定の公演は
演劇集団ワンダーランド第48回公演 「アチャラカ 昭和の喜劇人・古川ロッパ、ハリキる」 作・演出/竹内一郎 会期 2021年1月28日（木）～31日（日） 会場 MOMO
です。
ということで、モチベーション上がっています。上記の話は全て本当です。
出たのはコチラ。
atcoder.jp
A〜F問題の計6問で、結果はD問題以外の5問正解でした！これまでの最高戦績かと。特に、500点以上の問題をリアルタイムで解けたのは多分初めてでは・・・？(E=500点問題、F=600点問題)
では、解答コードを書いていきます。
Problem B
全パターン試す。
(define a (read)) (define b (read)) (define c (read)) (define d (read)) (display (max (* a c) (* a d) (* b c) (* b d))) (newline)
Problem C
(N桁の並び全パターン)-(0-8を使うパターン)-(2-9を使うパターン)+(1-8を使うパターン)ですね。
moduloをするタイミングの関係で、負の値が出てしまうようなプログラムで一度提出してしまい、1ペナルティくらいました。もったいない。
(define N (read)) (define (modruijo n i) (define (sub kata now) (if (= kata i) now (sub (+ kata 1) (modulo (* now n) 1000000007)))) (sub 0 1)) (display (modulo (+ (- (modruijo 10 N) (* 2 (modruijo 9 N)) (* 25 1000000007)) (modruijo 8 N)) 1000000007)) (newline)
ここまでで10分(+1ペナルティ)。
D問題があまりにピンと来なかったので、E、Fにチャレンジする方針にしました。
Problem E
確か、ユークリッド距離の最大値がどうっていうのあったよな・・・と思い「マンハッタン距離 最大 探す」で検索。そこで出てきたコチラの方の記事がわかりやすかったので、書いているままに実装。そして一発でACでした！知見に頼るのは大切・・・
(define N (read)) (define (read-n-points n) (if (= n 0) '() (let* ((first (read)) (second (read))) (cons (cons first (cons second '())) (read-n-points (- n 1)))))) (define (cheb point) (let ((first (car point)) (second (car (cdr point)))) (cons (- first second) (cons (+ first second) '())))) (define (chebtrans points) (if (null? points) '() (cons (cheb (car points)) (chebtrans (cdr points))))) (define (div1-trans chebpoints) (if (null? chebpoints) '() (cons (car (car chebpoints)) (div1-trans (cdr chebpoints))))) (define (div2-trans chebpoints) (if (null? chebpoints) '() (cons (car (cdr (car chebpoints))) (div2-trans (cdr chebpoints))))) (define (listmax list) (define (sub sublist maxval) (if (null? sublist) maxval (sub (cdr sublist) (max (car sublist) maxval)))) (sub (cdr list) (car list))) (define (listmin list) (define (sub sublist minval) (if (null? sublist) minval (sub (cdr sublist) (min (car sublist) minval)))) (sub (cdr list) (car list))) (display (let* ((points (read-n-points N)) (chebpoints (chebtrans points)) (div1 (div1-trans chebpoints)) (div2 (div2-trans chebpoints))) (max (- (listmax div1) (listmin div1)) (- (listmax div2) (listmin div2))))) (newline)
Problem F
手順としては、
・解答となる配列の先頭から順に、Bの後ろから入れていく ・もしA[i]==B[i]となる部分が来ちゃったら、解答配列の後ろから、「Bの後ろから入れていく」を続ける ・そのまま入れきれたらYes、またA[i]==B[i]となる部分が来ちゃったらNo
というので一回実装して提出。
すると、サンプル50個中3個のみWA・・・めちゃくちゃ惜しい。
Dに戻るよりFを通し切ることに賭けた方がいいだろう！と決断し、3個のWAがどんなケースだったか想像。
すると、下記のようなケースを思いつきました。
A=[1,2,2,3] B=[1,2,2,3]
これは、答えを
[2,1,3,2]
とすればYesとなるが、僕のプログラムだとNoになってしまいます。
よって、コード内にもう一段階階層を作ってみます。方針としてはこう。
・解答となる配列の先頭から順に、Bの後ろから入れていく
・もしA[i]==B[i]となる部分が来ちゃったら、解答配列の後ろから、「Bの後ろから入れていく」を続ける
・そのまま入れきれたらYes、またA[i]==B[i]となる部分が来ちゃったら、そのA[i]("NGナンバー"と呼びます)を覚えておく
・「配列AのNGナンバーの個数」と「配列BのNGナンバー以外の数の個数」で前者<=後者なら、うまくやればいけるハズ
・具体的には、まず配列AのNGナンバーの位置に配列BのNGナンバー以外の数を配置していき、残った部分に関してAの昇順の位置にBの降順で値を入れるこれでいけるのでは・・・？と思い通すと、無事AC。というわけで、初めてリアルタイムで600点まで解けました。
コードはこんな感じ。
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[] array1 = new int[n]; int[] array2 = new int[n]; for(int i = 0; i < n; i++){ array1[i] = sc.nextInt(); } for(int i = 0; i < n; i++){ array2[i] = sc.nextInt(); } int[] ansarray = new int[n]; boolean noteasy = false; int index = 0; for(; index < n; index++){ if(array1[index] == array2[n - index - 1]){ noteasy = true; break; }else{ ansarray[index] = array2[n - index - 1]; } } boolean canclear = true; int ngnum = 0; if(noteasy){ for(int i = n - 1; i >= index; i--){ if(array1[i] == array2[i - index]){ canclear = false; ngnum = array1[i]; break; }else{ ansarray[i] = array2[i - index]; } } } //ここからがWA後に追加した部分 boolean cancanclear = canclear; if(!cancanclear){ int count1 = 0; int count2 = 0; for(int i = 0; i < n; i++){ if(array1[i] == ngnum){count1++;} if(array2[i] == ngnum){count2++;} } if(count1 <= n - count2){cancanclear = true;} if(cancanclear){ int index2 = 0; boolean[] usecheck = new boolean[n]; for(int i = 0; i < n; i++){ usecheck[i] = false; } for(int i = 0; i < n; i++){ if(ngnum == array1[i]){ while(array2[index2] == ngnum){ index2++; } ansarray[i] = array2[index2]; usecheck[index2] = true; index2++; } } index2 = n - 1; for(int i = 0; i < n; i++){ if(ngnum != array1[i]){ while(usecheck[index2]){ index2--; } ansarray[i] = array2[index2]; index2--; } } } } //ここまでがWA後に追加した部分 if(cancanclear){ System.out.println("Yes"); for(int i = 0; i < n - 1; i++){ System.out.print(ansarray[i]); System.out.print(" "); } System.out.println(ansarray[n-1]); }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); } } }
想定解は、僕のコードで言う「ngnum」に関して二分探索を行うのかな・・・と予想してます。まぁダサいアルゴリズムですが、通ったので万事OK！
そしてD問題を見て色々検索するも、あえなくタイムオーバー。
E問題、F問題まで解けた分、D問題が解けなかったのが悔やまれる・・・どうせなら6問全完してみたかったです。
ただ、おそらくABCにおける最高戦績かと。レーティング上がりますように！！！！
これから次の会社の仕事、そして舞台の稽古や公演が入ってきますが、なんとかAtCoderは続けていきたいところです。行き当たりばったりで出るだけじゃなく、蟻本あたりを通読したいですね。
なんであれ、とても楽しいコンテストでした！時間を作って今後もチャレンジします！！！
P.S.(同日23:20)パフォーマンスは過去最高の1824、レーティングも78アップして1315になりました！嬉しい！！！！！
P.S.2 この方のツイートを見て、Dも解いてみました。一発でACでした。1つの問題をツイート1つに収まるように説明できるのはすごいですね。
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[] table = new int[n+3]; table[0] = 0; table[1] = 0; table[2] = 0; table[3] = 1; for(int i = 4; i <= n; i++){ int count = 1; for(int j = 3; j <= i; j++){ count = (count + table[i-j]) % 1000000007; } table[i] = count; } System.out.println(table[n]); } //ここからテンプレ 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); } } }
