AtCoder Beginners selection 終わりました
AtCoder Beginners Selection 問題集が終わったので、最後の問題(ABC086C - Traveling)をどのように解決したかの記録を残そうと思います。
問題
ABC086C - Traveling問題文
https://atcoder.jp/contests/abs/tasks/arc089_a制約
- 一単位時間ごとにX又はYを+1 or -1 できる。
- 同じ場所にとどまることが出来ない
解決方針
- 現在の位置から目的地まで移動する距離(X方向, Y方向)を算出する。
- (移動距離 - 時間) >= 0 か確認する。
- 2.が真ならば残り時間(移動距離 - 時間)を2で割った余りが0か確認する。
(残り時間が奇数だった場合、目的地から動くと戻れないため) - 2. 3.が真なら"Yes"を返し、そうでないなら"No"を返す。
実際のコード
import java.util.Arrays; import java.util.Scanner; public class Main { static String T = ""; public static void main(String args[]) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int currentX = 0; int currentY = 0; int currentTime = 0; boolean boo = true; // 途中までいると思ってたけど要らない子でした for(int i = 0; i < n; i++){ int t = sc.nextInt(); int x = sc.nextInt(); int y = sc.nextInt(); int distanceX = Math.abs(x - currentX); int distanceY = Math.abs(y - currentY); int restTime = t - currentTime; if((distanceX + distanceY) - restTime > 0){ System.out.println("No"); return; }else if ((distanceX + distanceY - restTime) % 2 == 0){ }else{ System.out.println("No"); return; } } System.out.println("Yes"); } }
感想
伝説のMLE問題と比べると簡単だったイメージこの問題も他の解き方があると思うので知識を増やす意味を込めて見ておきます(なおJava以外あまりわからない)
次回からはAtCoderのBeginner Contestから問題を引っ張ってきてやろうと思います。
それではバイバイ
やっとこさMLEから抜け出した話
前回の記事で発生したMLEがなんとか解決できたので報告します。
よかったら前回の記事も見てください。
y-koki1023.hatenablog.com前回までの問題点
コードの判定の際に一部のケースでMLE(メモリ超過?)が発生した
理由はよくわからないが 要するに無駄が多いってことだろう(ヤケクソ)
今回の解決プラン
- 不要なメソッドの呼び出し回数を減らす。
- 判定に必要な文字列の改善
- 無駄そうなところを減らす(適当)
改善後のコード
import java.util.Arrays; import java.util.Scanner; public class Main { static String T = ""; public static void main(String args[]) { Scanner sc = new Scanner(System.in); String str = sc.next(); String[] strs = str.split(""); String temp = ""; for(int i = 0; i < strs.length;){ if(strs[i].equals("d")){ temp = checkDream(i,strs); if(!temp.equals( "error")){ T += temp; }else{ System.out.println("NO"); return; } }else if(strs[i].equals("e")){ temp = checkErase(i,strs); if(!temp.equals("error")){ T += temp; }else{ System.out.println("NO"); return; } }else{ System.out.println("NO"); return; } i = T.length(); } if(T.equals(str)){ System.out.println("YES"); }else{ System.out.println("NO"); } } public static String checkDream(int index, String[] strs){ String temp = ""; try{ /* for(int i = index; i < index + 5;i++){ temp = temp + strs[i]; } */ String copy[] = Arrays.copyOfRange(strs,index,index+5); temp = String.join("",copy); if(temp.equals("dream")){ temp += strs[index + 5] + strs[index + 6]; if(temp.equals("dreamer")){ temp = checkErase(index + 5,strs); if( temp != "error"){ return "dream" + temp; }else{ return "dreamer"; } }else{ return "dream"; } }else{ return "error"; } }catch(Exception e){ if(!temp.equals("dream")){ return "error"; }else{ return "dream"; } } } public static String checkErase(int index, String[] strs){ String temp = ""; try{ /* for(int i = index; i < index + 5;i++){ temp = temp + strs[i]; } */ String copy[] = Arrays.copyOfRange(strs,index,index+5); temp = String.join("",copy); if(temp.equals("erase")){ temp += strs[index + 5]; if(temp.equals("eraser")){ return "eraser"; }else{ return "erase"; } }else{ return "error"; } }catch(Exception e){ if(!temp.equals("erase")){ return "error"; }else{ return "erase"; } } } }
結果は....?
問答無用のMLEでした....本当にビギナー用なんだろうか
どうしようもなくなった僕はフラグ建築士1級の友人Yに教えてもらった
"文字列後ろから見れば判定楽じゃね?" 戦法にシフトすることにしました。
文字列後ろから見れば判定楽じゃね? とは
入力される文字列を後ろから判定していくことで、前から判定していくときに必要だった "dreamer" の"er" + 後の3文字から "erase" を判定する手間を省くことができる素晴らしい技法である。実際に書いてACだったコード
import java.util.Arrays; import java.util.Scanner; public class Main { static String T = ""; public static void main(String args[]) { Scanner sc = new Scanner(System.in); String str = sc.next(); String keyWords[] = {"dream","dreamer","erase","eraser"}; //sub_Stringの呼び出しが多い問題? int length = str.length(); while(length > 0){ String temp = str.substring(length - 5,length); if(length - 5 >= 0 ) { if (temp.equals(keyWords[0]) || temp.equals(keyWords[2])) { length -=5; continue; } } temp = str.substring(length -6 ,length); if(length - 6 >= 0 && temp.equals(keyWords[3])){ length -=6; continue; } temp = str.substring(length - 7,length); if(length- 7 >= 0 &&temp.equals(keyWords[1])){ length -=7; continue; }else{ System.out.println("NO"); return; } } System.out.println("YES"); } }
教訓
急がば回れ これに尽きる問題を解くためゴリ押しした結果メモリを大量に使う消費文化もびっくりなコードを書いてしまった。
書くまえに無駄な処理が多くないか、方法自体がゴリ押しすぎないかを確認してからコードを書くことで今回のようなことが起こらないように心掛けたい(絶対やらかす btw)
友人Yありがとう。
自信満々に書いたコードの評価が MLEだった話
はぁ...
ブログ用に始めて解いた問題でMLEが出たので報告します。
問題
ABC049C - 白昼夢 / Daydream
問題文
https://atcoder.jp/contests/abs/tasks/arc065_a
解決方針
- 文字列を左から5文字見て "dream","erase" かを確かめる
- それぞれ"dreamer","eraser" にならないかを確かめる
- "dreamer"が検出された場合"dreamerase", "dreameraser" になるかもしれないのでそれも確かめる
- 文字列を最後まで見終わったら結果を出力
当時これでいけるだろうとたかをくくっていた
感想
正直どこが原因なのか分かってないので再度考え直します。
コードをチェックしてくれた友人が"TLE"起きなさそうだしとかいってたら"MLE"が出たので、 もしかしたらやまこーさんはフラグ回収能力が高いのかもしrフラグ回収能力が高いのかもしれない(?)
解決したらまたブログ更新します。バイバイ(下におまけのコードがあるよ)
実際のコード
import java.util.Scanner; public class Main { static String T = ""; public static void main(String args[]) { Scanner sc = new Scanner(System.in); String str = sc.next(); String[] strs = str.split(""); for(int i = 0; i < strs.length;){ if(checkDream(i,strs) != "error"){ T += checkDream(i,strs); }else if(checkErase(i,strs) != "error"){ T += checkErase(i,strs); }else{ System.out.println("NO"); return; } i = T.length(); } if(T.equals(str)){ System.out.println("YES"); }else{ System.out.println("NO"); } } public static String checkDream(int index, String[] strs){ String temp = ""; try{ for(int i = index; i < index + 5;i++){ temp = temp + strs[i]; } if(temp.equals("dream")){ temp += strs[index + 5] + strs[index + 6]; if(temp.equals("dreamer")){ if(checkErase(index + 5,strs) != "error"){ return "dream" + checkErase(index + 5,strs); }else{ return "dreamer"; } }else{ return "dream"; } }else{ return "error"; } }catch(Exception e){ if(!temp.equals("dream")){ return "error"; }else{ return "dream"; } } } public static String checkErase(int index, String[] strs){ String temp = ""; try{ for(int i = index; i < index + 5;i++){ temp = temp + strs[i]; } if(temp.equals("erase")){ temp += strs[index + 5]; if(temp.equals("eraser")){ return "eraser"; }else{ return "erase"; } }else{ return "error"; } }catch(Exception e){ if(!temp.equals("erase")){ return "error"; }else{ return "error"; } } } }
ブログ始めました!
初めまして 現役高専生のやまこーです。
まあ現役って言っても今年の3月で卒業するんですが...そんなことは問題ではない。
今回は競技プログラミングをしっかり始めてみようということでその記録を残すためにブログを始めようと思ったのがきっかけで今ブログを書いている感じです。
競技プログラミングの問題はAtCoderさんのコンテストの過去問が載っているという噂のAtCoder Problems さんを利用させてもらおうと思っています。
自分の学習記録を残すのが目的なのでブログとしては面白くないかもしれませんが、継続は力なりということで競プロもブログも頑張ってみたいと思ってます。
では、皆さんが次の記事(まで書いてもない)に来てくれることを祈りながら、今日も頑張ります。
バイバイ