AtCoder158振り返り(1-3)

競技プログラミング

毎度毎度Javaで競プロやっていますがそろそろC++に乗り換えるべきだよなーと思いますが一旦転職活動が落ち着いたら文法など勉強しようかと思います。

 

取り急ぎ今回の結果を振り返っていきます。

 

 

成績

今回の実績は以下の通りです。（思っていた以上に才能がないかもしれません。。。）

いや、これからこれから。まだレートは上がり続けているのでこの調子で茶色目指したいですね。

f:id:lawrence-twin:20200308084226p:plain

AtCoderBeginner158

解説は以下の通りです。

AtCoder解説:PDF

https://img.atcoder.jp/abc158/editorial.pdf

 

AtCoder解説：Youtube

www.youtube.com

 

問1

atcoder.jp

3つの駅 ①　②　③　の鉄道会社のうち、それぞれの駅を結ぶ鉄道管理会社が違う場合バスを利用する。バスを利用する場合は"Yes"を返却する。という処理です。

 

例えば、　①：A, ②：B, ③:A　ならば、①-②間と　②-③間が異なるためYES

"No"を返すのは、①②③がすべてA またはBの場合のみです。

 

■回答コード

  1. import java.util.Scanner;
  2.  
  3.  
  4. public class Main {
  5.  
  6. public static void main(String args) {
  7. // TODO 自動生成されたメソッド・スタブ
  8. Scanner sc = new Scanner(System.in);
  9.  
  10. String S = sc.next();
  11.  
  12. boolean bass = false;
  13. if(!S.substring(0, 1).equals( S.substring(1, 2))) bass = true;
  14. if(!S.substring(2, 3).equals(S.substring(1, 2))) bass = true;
  15.  
  16.  
  17. if(bass) {
  18. System.out.println("Yes");
  19. } else {
  20. System.out.println("No");
  21. }
  22. }
  23.  
  24. }

もっと簡単に実装できたはずですが、今回は一文字ずつチェックしてしまいました。。。

問2

 atcoder.jp

全然関係ないですが、「根気のある高橋君」が妙にツボってしまいました。

この問題は全量がN個のボール、

以下の処理を10^100繰り返す。

・A個の赤色ボールを並べる

・その後ろに青色B個のボールを並べる。

という処理です。

最初は馬鹿正直にfor文を利用して計算をしようとしてしまいました。しかし、さすがに根気のある高橋君でも無理でした。10^18回繰り返す可能性があるので単純に時間内では終わりません。

また自分はint型使いましたが、桁あふれを起こしてしまいこちらもダメです。

最終的には時間切れとなりましたが、時間切れ1分後に提出した以下コードでACとなったので良かった？です。

 

■ソースコード

  1. import java.util.Scanner;
  2.  
  3.  
  4. public class Main {
  5.  
  6. //残り数問が結果合わない
  7. public static void main(String args) {
  8. // TODO 自動生成されたメソッド・スタブ
  9. Scanner sc = new Scanner(System.in);
  10.  
  11. String strN = sc.next();
  12. String strA = sc.next();
  13. String strB = sc.next();
  14. // 1 <= N <= 10^18
  15. long N = Long.parseLong(strN);
  16.  
  17. //A >= 0
  18. long A = Long.parseLong(strA);
  19.  
  20. //B >= 0
  21. long B = Long.parseLong(strB);
  22.  
  23. boolean flg = false;
  24.  
  25. if(A == 0) {
  26. System.out.println(0);
  27. return;
  28. }
  29.  
  30. long roop = N / (A+B);
  31. long amari = N % (A+B);
  32. if(amari > A) {
  33. amari = A;
  34. }
  35.  
  36. System.out.println(roop * A + amari);
  37.  
  38. }
  39.  
  40. }

import java.util.Scanner; public class Main { //残り数問が結果合わない public static void main(String args) { // TODO 自動生成されたメソッド・スタブ Scanner sc = new Scanner(System.in); String strN = sc.next(); String strA = sc.next(); String strB = sc.next(); // 1 <= N <= 10^18 long N = Long.parseLong(strN); //A >= 0 long A = Long.parseLong(strA); //B >= 0 long B = Long.parseLong(strB); boolean flg = false; if(A == 0) { System.out.println(0); return; } long roop = N / (A+B); long amari = N % (A+B); if(amari > A) { amari = A; } System.out.println(roop * A + amari); } }さい

 

最後の調整用のあまり処理をミスってしまい、

あまり または Aの小さいほうの値を設定すべきところをあまり- Aとしてしまいエラーとなりました。。。

 

ちなみに解説の方では以下の通り。5行で実装可能とは、、、

1 N, A, B = map(int, input().split())
2 ans = N // (A + B) * A
3 rem = N % (A + B)
4 ans += min(rem, A)
5 print(ans)

 

問3

 atcoder.jp

消費税の元金を求める問題です。

引数として、消費税額A(税率0.08) と、消費税額B(税率0.10)が渡されるので

それぞれの消費税額をもとに最小の元金を求める問題です。

なお、日本の消費税と同様小数点以下の消費税は切り捨てとなります。

※過去小数点が考慮されてしまい会計時に1円を多く払う事態が以前ニュースでありましたが今回は関係ありません。

 

制約に 1 ≦ A ≦ B ≦100とあるため、少なくとも元金は1010円以上となることはあり得ません。

自分は多めにfor文で10000まで処理することとしました。（どうせ途中でbreakしますし。）

■回答コード

  1. import java.math.BigDecimal;
  2. import java.util.Scanner;
  3.  
  4.  
  5. public class Main {
  6.  
  7. public static void main(String args) {
  8. // TODO 自動生成されたメソッド・スタブ
  9. Scanner sc = new Scanner(System.in);
  10.  
  11. int A = sc.nextInt();
  12. int B = sc.nextInt();
  13.  
  14. BigDecimal tax08 = BigDecimal.valueOf(0.08);
  15. BigDecimal tax10 = BigDecimal.valueOf(0.10);
  16. BigDecimal taxA = new BigDecimal(0);
  17. BigDecimal taxB = new BigDecimal(0);
  18.  
  19. int result = -1;
  20. for(int i = 1; i < 10000; i++) {
  21. taxA = BigDecimal.valueOf(i);
  22. taxB = BigDecimal.valueOf(i);
  23. taxA = taxA.multiply(tax08);
  24. taxB = taxB.multiply(tax10);
  25.  
  26. taxA = taxA.setScale(0, BigDecimal.ROUND_DOWN);
  27. taxB = taxB.setScale(0, BigDecimal.ROUND_DOWN);
  28.  
  29. if(BigDecimal.valueOf(A).equals(taxA)
  30. && BigDecimal.valueOf(B).equals(taxB)) {
  31. result = i;
  32. break;
  33. }
  34. }
  35.  
  36. System.out.println(result);
  37.  
  38. }
  39.  
  40. }

 

これは一発でACだったのでうれしかったです。

小数点やBigDecimal型の扱いにやや苦労しましたが(doubleでもよかったのかな？）

 

ここからは殆ど問題が見れていないので予習です。

問4

 atcoder.jp

問題を見るとそこまで難しくはないですね。

時間さえあれば実装できそうです。

操作方法は3パターンで以下(1), (2) を順に処理していけば何とかなりそうです。

(1) 引数列の一つ目の値が 1の場合は文字列を反転する。

(2) 引数列の一つ目の値が 2の場合は、

　(2-1) 次の引数が1ならば先頭に次の文字列を追加

　(2-2) 次の引数が2ならば末尾に次の文字列を追加

 

と思いましたが、問題文の通りに直接記載すると反転クエリが拘束に処理できないとあり恐らくTLEになってしまいます。

対応策として反転クエリによる反転は実際に行わず現在どちらが先頭かの情報を保持しておけば反転処理量が激減するため問題なくなるとのこと。

※ただし、最後に反転処理は入れる必要あり。

 

問5

atcoder.jp

文字列を指定した素数で割り切れるかどうかをチェックする処理です。

単純な計算はO(N^2)ですが、例外として2, 5であれば右端が10である場合割り切れるため左端の数値がいくつであるか気にする必要がなくなります。

あとは 右から順にUi mod P を計算していき、x mod Pで解ける？？？ようですがちょっとよく分かりません。。。

 

 

以上。ABCは安定してとれるようになりたい。。。