久々にリアルタイムで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なんだと思います。
全探索は間に合わないので、かってにこっちで手順を指定すればいいのでは？と思いました。
ということで、『左上から順の下記のような順番でチェック』していき、
そこが奇数枚になっていれば、『右か下に移すのみ』に制限することにしました。
そして、『移す先は"できれば"奇数(=奇数がなくても移すは移す)』としました。
調べる順番も操作も制限したわけです。
ただ、これは恐らく最大化としては問題ないハズ・・・。
・最大化するやり方の、操作の順を変えても結果は変わらないこと
・『左か上に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個奇数で他全部偶数
まで持って行けるんですね・・・！
ちなみに解説記事の方では、僕のやり方とは違うやり方でした。
ただ、「勝手に見ていく手順を決める」点では同じでした。
奥深い問題ですね。
