AtCoder157振り返り

競技プログラミング

2020/3/1(日) に3回目のAtCoderに挑戦

結果としては遺憾の２完。。。ABは20分でしたがCでドツボにはまりました。

今回の内容を改めて振り返っていきます。

 

■解決

第1問:Duplex Printing

 

atcoder.jp

    

この問題は両面印刷に必要な部数を求めるプログラムです。

頭では秒で解けましたが若干コーディングに手間取りました。

 

■回答コード

  1. import java.util.Scanner;
  2.  
  3. //Distinct or Not
  4. public class Main {
  5. public static void main(String args){
  6.  
  7. Scanner sc = new Scanner(System.in);
  8.  
  9. int n = sc.nextInt();
  10. int adj = n %2;
  11. System.out.println(n/2 + adj);
  12. }
  13. }

 

 

      

第2問 

atcoder.jp

2問目は3×3のビンゴ問題でした。

これはさほど複雑ではないですが、今までのAB問題に比べるとややコーディングの量が多くなりました。

単純に3×3にした後に、ビンゴした数値を0に置換して最後にチェックしています。

解答では30行程度でしたのでもっと短くできるはずですね。。。

 

■回答コード

  1. import java.util.Scanner;
  2.  
  3. //Distinct or Not
  4. public class Main {
  5. public static void main(String args){
  6.  
  7. Scanner sc = new Scanner(System.in);
  8.  
  9. int bingo = new int[3][3];
  10. for(int i = 0; i < 3; i++) {
  11. for(int j = 0; j < 3; j++) {
  12. bingo[i][j] = sc.nextInt();
  13.  
  14. }
  15. }
  16.  
  17. int max = sc.nextInt();
  18. for(int x = 0; x < max; x++) {
  19. int num = sc.nextInt();
  20. for(int i = 0; i < 3; i++) {
  21. for(int j = 0; j < 3; j++) {
  22. if(bingo[i][j] == num) {
  23. bingo[i][j] = 0;
  24. }
  25. }
  26. }
  27. }
  28.  
  29.  
  30. //正解チェック
  31. int cnt = 0;
  32. boolean flg = false;
  33. //横チェック
  34. for(int i = 0; i < 3; i++) {
  35. for(int j = 0; j < 3; j++) {
  36. if(bingo[i][j] == 0) {
  37. cnt++;
  38. }
  39. if(cnt == 3) {
  40. flg = true;
  41. }
  42. }
  43. cnt = 0;
  44. }
  45.  
  46. //縦チェック
  47. for(int i = 0; i < 3; i++) {
  48. for(int j = 0; j < 3; j++) {
  49. if(bingo[j][i] == 0) {
  50. cnt++;
  51. }
  52. if(cnt == 3) {
  53. flg = true;
  54. }
  55. }
  56. cnt = 0;
  57. }
  58.  
  59. //斜めチェック
  60. if(bingo[0][0] == 0) cnt++;
  61. if(bingo[1][1] == 0) cnt++;
  62. if(bingo[2][2] == 0) cnt++;
  63.  
  64. if(cnt == 3) flg = true;
  65. cnt = 0;
  66.  
  67. if(bingo[0][2] == 0) cnt++;
  68. if(bingo[1][1] == 0) cnt++;
  69. if(bingo[2][0] == 0) cnt++;
  70.  
  71. if(cnt == 3) flg = true;
  72.  
  73. if(flg) {
  74. System.out.println("Yes");
  75. } else {
  76. System.out.println("No");
  77. }
  78.  
  79. }
  80. }

 

        

■未解決

第3問    

atcoder.jp

第3問ですがやや複雑でした。がそこまで難しい内容ではないです。

1～3桁に対して、各桁ごとの値が提案されるのでその値の条件に合致する候補の最小値を設定するというものです。

そして、条件を満たす値がなければ-1を返します。

"最小値を設定する"という点でドツボにはまったのですが、例えば

引数が以下の場合

3 1

2 4

3 9

3桁の値に対して、2桁目が4、3桁目が9となります。

x49という値が候補に挙がりますが、先頭1桁目が未確定なので最小値の0を設定して

049が答え、、、ではないです。

先頭が0という値はあり得ないとしているので、この場合の答えは194が正解です。

私はこのロジックが考慮されていなかったがために時間切れでした。。。（解答見直したときやっちまった。。。と思いましたね。）

 

 

■回答コード

  1. import java.util.Scanner;
  2.  
  3.  
  4. public class Main {
  5.  
  6.  
  7. public static void main(String args) {
  8. // TODO 自動生成されたメソッド・スタブ
  9.  
  10. Scanner sc = new Scanner(System.in);
  11. int N = sc.nextInt();
  12. int M = sc.nextInt();
  13.  
  14. boolean flgM = new boolean[N];
  15. int[] intN = new int[N];
  16. boolean NG = false;
  17. for(int i = 0; i < M; i++) {
  18. int s = sc.nextInt();
  19. int c = sc.nextInt();
  20.  
  21. if(flgM[s-1] == false || intN[s-1] == c) {
  22. intN[s-1] = c;
  23. flgM[s-1] = true;
  24. } else {
  25. NG = true;
  26. }
  27. }
  28. if(NG) {
  29. System.out.println(-1);
  30. } else {
  31. int result = 0;
  32. int kakeru = 1;
  33. for(int i = N-1; i >= 0; i--) {
  34. result = result + intN[i] * kakeru;
  35. if(N > 1 && i == 0 && flgM[i] == false) result = result + 1 * kakeru;
  36. kakeru = kakeru * 10;
  37. }
  38. if(String.valueOf(result).length() != N) {
  39. result = -1;
  40. }
  41. System.out.println(result);
  42. }
  43. }
  44.  
  45. }

                  

            

            

 

■未受講

第4問

 

atcoder.jp

人1～Nの友達候補がそれぞれ何人いるかを求めるアルゴリズムです。

パット見て解けなくはなさそうですが、、、ブロック関係がよくわからないです。

DFS(深さ優先探索)というものを使えば解けるとのこと

今度勉強しておこう。。。

 

Ｑiita：DFS (深さ優先探索) 超入門！ 〜 グラフ・アルゴリズムの世界への入口 〜【前編】

https://qiita.com/drken/items/4a7869c5e304883f539b

第5問

 

atcoder.jp

引数として渡されるクエリを順に処理していく処理ですが、

あまり難しくないように思えますがどうでしょうか？

クエリはType1, Type2に分かれますがType1は並行二分探索木で解けるとのこと

Type2はlower_bound関数(探索したいKey以上のイテレータを返す）で行けるらしい。。。

ここら辺のアルゴリズムもまだ勉強しないとですね。

 

第6問

atcoder.jp

 

（　＾ω＾）・・・？？？

数か月後にはここら辺もわかるのでしょうか。。。

 

参考

 

AtCoder157解説

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