徒然

思いついたら書きます

AtCoderで始めるCOBOL入門 ~演習編~

はじめに

前々回の記事前回の記事COBOLの基礎知識について記載してきました。
では実際に、AtCoderに登録したら解くべき精選過去問10問ことAtCoder Beginners Selectionの問題を解いていきます。

0. PracticeA : Welcome to AtCoder

問題のリンク

UNSTRING文で入力をBCに分解しましょう。
TRIM関数を使えば数字の無駄なスペースが消せます。

       PROGRAM-ID. MAIN.
       ENVIRONMENT DIVISION.
       INPUT-OUTPUT SECTION.
       FILE-CONTROL.
       DATA DIVISION.
       WORKING-STORAGE SECTION.
           01 INP PIC X(10000).
           01 A PIC 9(4).
           01 B PIC 9(4).
           01 C PIC 9(4).
           01 X PIC ZZZ9.
           01 S PIC X(100).
       PROCEDURE DIVISION.
           ACCEPT A.
           ACCEPT INP.
           UNSTRING INP DELIMITED BY " " INTO B C.
           ACCEPT S.
           COMPUTE  X = A + B + C.
           DISPLAY FUNCTION TRIM(X) " " S.
           STOP RUN.
       END PROGRAM ATCODER.

1. ABC086A : Product

問題のリンク

偶奇判定はMOD関数でできます。

       IDENTIFICATION DIVISION.
       PROGRAM-ID. ATCODER.
       ENVIRONMENT DIVISION.
       INPUT-OUTPUT SECTION.
       FILE-CONTROL.
       DATA DIVISION.
       WORKING-STORAGE SECTION.
           01 INP PIC X(10000).
           01 A PIC 9(5).
           01 B PIC 9(5).
           01 C PIC 9(10).
       PROCEDURE DIVISION.
           ACCEPT INP.
           UNSTRING INP DELIMITED BY SPACE INTO A B.
           COMPUTE C = A * B.
           IF FUNCTION MOD(C, 2) = 0 THEN
               DISPLAY "Even"
           ELSE
               DISPLAY "Odd"
           END-IF.
           STOP RUN.
       END PROGRAM ATCODER.

2. ABC081A : Placing Marbles

問題のリンク

先頭から1文字ずつ見ていって、"1"なら答えに加算しましょう。

       IDENTIFICATION DIVISION.
       PROGRAM-ID. ATCODER.
       ENVIRONMENT DIVISION.
       INPUT-OUTPUT SECTION.
       FILE-CONTROL.
       DATA DIVISION.
       WORKING-STORAGE SECTION.
           01 S PIC X(3).
           01 I PIC 9(1).
           01 ANS PIC 9(1).
       PROCEDURE DIVISION.
           ACCEPT S.
           PERFORM VARYING I FROM 1 BY 1 UNTIL I > 3
               IF S(I:1) = "1" THEN
                   ADD 1 TO ANS
               END-IF
           END-PERFORM.
           DISPLAY ANS.
           STOP RUN.
       END PROGRAM ATCODER.

3. ABC081B : Shift only

問題のリンク

A_iを2で割れる回数の最小値が答えです。

       IDENTIFICATION DIVISION.
       PROGRAM-ID. ATCODER.
       ENVIRONMENT DIVISION.
       INPUT-OUTPUT SECTION.
       FILE-CONTROL.
       DATA DIVISION.
       FILE SECTION.
       WORKING-STORAGE SECTION.
           01 INP PIC X(10000).
           01 PT PIC 9(18) VALUE 1.
           01 N PIC 9(3).
           01 AI.
               03 A PIC 9(10) OCCURS 200 TIMES.
           01 I PIC 9(10).
           01 J PIC 9(10).
           01 X PIC 9(10).
           01 ANS PIC 9(18) VALUE HIGH-VALUE.
           01 ANS-Z PIC Z(17)9.
       PROCEDURE DIVISION.
           ACCEPT N.
           ACCEPT INP.
           PERFORM VARYING I FROM 1 BY 1 UNTIL I > N
               UNSTRING INP DELIMITED BY SPACE INTO A(I) WITH POINTER PT
           END-PERFORM.
           PERFORM VARYING I FROM 1 BY 1 UNTIL I > N
               MOVE 0 TO J
               MOVE A(I) TO X
               PERFORM UNTIL FUNCTION MOD(X, 2) NOT = 0
                   COMPUTE X = X / 2
                   ADD 1 TO J
               END-PERFORM
               IF J < ANS THEN
                   MOVE J TO ANS
               END-IF
           END-PERFORM.
           MOVE ANS TO ANS-Z.
           DISPLAY FUNCTION TRIM(ANS-Z).
           STOP RUN.
       END PROGRAM ATCODER.

4. ABC087B : Coins

問題のリンク

0 \leq A,B,C \leq 50なので、A,B,Cの枚数の選び方を全探索すればよいです。
多重IF文の最後のEND-PERFORM以外に.を書くとエラーになるところが注意点です。

       IDENTIFICATION DIVISION.
       PROGRAM-ID. ATCODER.
       ENVIRONMENT DIVISION.
       INPUT-OUTPUT SECTION.
       FILE-CONTROL.
       DATA DIVISION.
       FILE SECTION.
       WORKING-STORAGE SECTION.
           01 WK.
               03 INP PIC X(100000).
               03 A PIC 9(5).
               03 B PIC 9(5).
               03 C PIC 9(5).
               03 X PIC 9(5).
               03 I PIC 9(5).
               03 J PIC 9(5).
               03 K PIC 9(5).
               03 ANS PIC 9(17).
               03 ANS-Z PIC Z(14)9.
       PROCEDURE DIVISION.
           ACCEPT A.
           ACCEPT B.
           ACCEPT C.
           ACCEPT X.
           PERFORM VARYING I FROM 0 BY 1 UNTIL I > A
               PERFORM VARYING J FROM 0 BY 1 UNTIL J > B
                   PERFORM VARYING K FROM 0 BY 1 UNTIL K > C
                       IF I * 500 + J * 100 + K * 50 = X THEN
                           ADD 1 TO ANS
                       END-IF
                   END-PERFORM
               END-PERFORM
           END-PERFORM.
           MOVE ANS TO ANS-Z.
           DISPLAY FUNCTION TRIM(ANS-Z).
           STOP RUN.
       END PROGRAM ATCODER.

5. ABC083B : Some Sums

問題のリンク

I-R REDEFINES I PIC X(5)とすることで、Iを数値としてインクリメントしつつI-Rで文字列として各桁の数値を切り出すことができます。
切り出した文字列を数値に変換するにはNUMVAL関数を使います。

       IDENTIFICATION DIVISION.
       PROGRAM-ID. ATCODER.
       ENVIRONMENT DIVISION.
       INPUT-OUTPUT SECTION.
       FILE-CONTROL.
       DATA DIVISION.
       FILE SECTION.
       WORKING-STORAGE SECTION.
           01 WK.
               03 INP PIC X(100000).
               03 N PIC 9(5).
               03 A PIC 9(5).
               03 B PIC 9(5).
               03 I PIC 9(5).
               03 I-R REDEFINES I PIC X(5).
               03 J PIC 9(5).
               03 S PIC 9(5).
               03 ANS PIC 9(15).
               03 ANS-Z PIC Z(14)9.
       PROCEDURE DIVISION.
           ACCEPT INP.
           UNSTRING INP DELIMITED BY SPACE INTO N A B.
           PERFORM VARYING I FROM 1 BY 1 UNTIL I > N
               MOVE 0 TO S
               PERFORM VARYING J FROM 1 BY 1 UNTIL J > 5
                  ADD FUNCTION NUMVAL(I-R(J:1)) TO S
               END-PERFORM
               IF A <= S AND S <= B THEN
                   ADD I TO ANS
               END-IF
           END-PERFORM.
           MOVE ANS TO ANS-Z.
           DISPLAY FUNCTION TRIM(ANS-Z).
           STOP RUN.
       END PROGRAM ATCODER.

6. ABC088B : Card Game for Two

問題のリンク

このゲームでは、自分の手番に残っているカードのうち最も大きいカードを取るのが最適です。
そのためaを降順(DESCENDING)にソートして、インデックスが奇数のとき(Aliceの取り分)は答えに加算し、偶数のとき(Bobの取り分)は答えから引けばよいです。

       IDENTIFICATION DIVISION.
       PROGRAM-ID. ATCODER.
       ENVIRONMENT DIVISION.
       INPUT-OUTPUT SECTION.
       FILE-CONTROL.
       DATA DIVISION.
       FILE SECTION.
       WORKING-STORAGE SECTION.
           01 WK.
               03 INP PIC X(100000).
               03 PT PIC 9(18) VALUE 1.
               03 N PIC 9(5).
               03 I PIC 9(5).
               03 ANS PIC 9(18).
               03 ANS-Z PIC Z(17)9.
           01 AL.
               03 AI OCCURS 1 TO 100 TIMES DEPENDING ON N.
                   05 A PIC 9(5).
       PROCEDURE DIVISION.
           ACCEPT N.
           ACCEPT INP.
           PERFORM VARYING I FROM 1 BY 1 UNTIL I > N
               UNSTRING INP DELIMITED BY SPACE INTO A(I) WITH POINTER PT
           END-PERFORM.
           SORT AI ON DESCENDING KEY A.
           PERFORM VARYING I FROM 1 BY 1 UNTIL I > N
               IF FUNCTION MOD(I, 2) = 1 THEN
                   ADD A(I) TO ANS
               ELSE
                   SUBTRACT A(I) FROM ANS
               END-IF
           END-PERFORM.
           MOVE ANS TO ANS-Z.
           DISPLAY FUNCTION TRIM(ANS-Z).
           STOP RUN.
       END PROGRAM ATCODER.

7. ABC085B : Kagami Mochi

問題のリンク

COBOLには連想配列(dictionary)や集合(set)のようなものが存在しないため、楽には解けません。
幸いこの問題は条件が1 \leq N \leq 100, 1 \leq d_i​ \leq 100と緩いため、長さ100の配列Lを用意して要素をL_{d_i}入れていき、要素が入っている数をカウントする方法(バケット法)が使えます。
計算量はO(N + (max(d_i) - min(d_i)))です。

       IDENTIFICATION DIVISION.
       PROGRAM-ID. ATCODER.
       ENVIRONMENT DIVISION.
       INPUT-OUTPUT SECTION.
       FILE-CONTROL.
       DATA DIVISION.
       FILE SECTION.
       WORKING-STORAGE SECTION.
           01 WK.
               03 INP PIC X(10000).
               03 N PIC 9(5).
               03 I PIC 9(5).
               03 D PIC 9(5).
               03 L PIC 9(1) OCCURS 100 TIMES.
               03 ANS PIC 9(18).
               03 ANS-Z PIC Z(17)9.
       PROCEDURE DIVISION.
           ACCEPT N.
           PERFORM VARYING I FROM 1 BY 1 UNTIL I > N
               ACCEPT D
               MOVE 1 TO L(D)
           END-PERFORM.
           PERFORM VARYING I FROM 1 BY 1 UNTIL I > 100
               IF L(I) = 1 THEN
                  ADD 1 TO ANS
               END-IF
           END-PERFORM.
           MOVE ANS TO ANS-Z.
           DISPLAY FUNCTION TRIM(ANS-Z).
           STOP RUN.
       END PROGRAM ATCODER.

ただしこの方法は1 \leq d_i​ \leq 10^{9}のような条件では使えないため、その場合はdをソートして前後が異なる要素をカウントしていく方法を使えばO(N log N)で解けます。

       IDENTIFICATION DIVISION.
       PROGRAM-ID. ATCODER.
       ENVIRONMENT DIVISION.
       INPUT-OUTPUT SECTION.
       FILE-CONTROL.
       DATA DIVISION.
       FILE SECTION.
       WORKING-STORAGE SECTION.
           01 WK.
               03 INP PIC X(10000).
               03 N PIC 9(5).
               03 I PIC 9(5).
               03 D PIC 9(5).
               03 ANS PIC 9(17).
               03 ANS-Z PIC Z(16)9.
           01 A-L.
               03 AI OCCURS 1 TO 100 TIMES DEPENDING ON N.
                   05 A PIC 9(5).
       PROCEDURE DIVISION.
           ACCEPT N.
           PERFORM VARYING I FROM 1 BY 1 UNTIL I > N
               ACCEPT D
               MOVE D TO A(I)
           END-PERFORM.
           SORT AI ON ASCENDING KEY A.
           MOVE 1 TO ANS.
           PERFORM VARYING I FROM 1 BY 1 UNTIL I > N - 1
               IF A(I) NOT = A(I + 1) THEN
                  ADD 1 TO ANS
               END-IF
           END-PERFORM.
           MOVE ANS TO ANS-Z.
           DISPLAY FUNCTION TRIM(ANS-Z).
           STOP RUN.
       END PROGRAM ATCODER.

8. ABC085C : Otoshidama

問題のリンク

10000円札、5000円札の枚数を全探索する(1000円札の枚数は自動的に決まる)想定解で書いてます。

       IDENTIFICATION DIVISION.
       PROGRAM-ID. ATCODER.
       ENVIRONMENT DIVISION.
       INPUT-OUTPUT SECTION.
       FILE-CONTROL.
       DATA DIVISION.
       FILE SECTION.
       WORKING-STORAGE SECTION.
           01 WK.
               03 INP PIC X(10000).
               03 N PIC 9(5).
               03 Y PIC 9(15).
               03 I PIC 9(15).
               03 J PIC 9(15).
               03 K PIC 9(15).
               03 I-Z PIC Z(14)9.
               03 J-Z PIC Z(14)9.
               03 K-Z PIC Z(14)9.
       PROCEDURE DIVISION.
           ACCEPT INP.
           UNSTRING INP DELIMITED BY SPACE INTO N Y.
           PERFORM VARYING I FROM 0 BY 1 UNTIL I > N
               PERFORM VARYING J FROM 0 BY 1 UNTIL I + J > N
                   COMPUTE K = N - I - J
                   IF 10000 * I + 5000 * J + 1000 * K = Y THEN
                       MOVE I TO I-Z
                       MOVE J TO J-Z
                       MOVE K TO K-Z
                       DISPLAY FUNCTION TRIM(I-Z) " " FUNCTION TRIM(J-Z)
                        " " FUNCTION TRIM(K-Z)
                       STOP RUN
               END-PERFORM
           END-PERFORM.
           DISPLAY "-1 -1 -1".
           STOP RUN.
       END PROGRAM ATCODER.

9. ABC049C : 白昼夢

問題のリンク

制約が1 \leq \mid S \mid \leq 10^{5}のため、READ文を使ってインプットを読み取る方法でないと終端が切れてしまうので注意です。
文字列を逆から読んでいく想定解ではこのようなコードになります。

       IDENTIFICATION DIVISION.
       PROGRAM-ID. ATCODER.
       ENVIRONMENT DIVISION.
       INPUT-OUTPUT SECTION.
       FILE-CONTROL.
           SELECT SYSIN ASSIGN TO KEYBOARD ORGANIZATION LINE SEQUENTIAL.
       DATA DIVISION.
       FILE SECTION.
           FD SYSIN.
               01 INDATA PIC X(100000).
       WORKING-STORAGE SECTION.
           01 WK.
               03 INP PIC X(100000).
               03 S PIC X(100000).
               03 N PIC 9(15).
               03 I PIC 9(15) VALUE 1.
       PROCEDURE DIVISION.
           OPEN INPUT SYSIN.
           READ SYSIN INTO INP.
           CLOSE SYSIN.
           MOVE FUNCTION REVERSE(FUNCTION TRIM(INP)) TO S.
           MOVE FUNCTION STORED-CHAR-LENGTH(S) TO N.
           PERFORM UNTIL I > N
               IF S(I:5) = "maerd" THEN
                   ADD 5 TO I
               ELSE IF S(I:7) = "remaerd" THEN
                   ADD 7 TO I
               ELSE IF S(I:5) = "esare" THEN
                   ADD 5 TO I
               ELSE IF S(I:6) = "resare" THEN
                   ADD 6 TO I
               ELSE
                   DISPLAY "NO"
                   STOP RUN
               END-IF
               END-IF
               END-IF
               END-IF
           END-PERFORM.
           DISPLAY "YES".
           STOP RUN.
       END PROGRAM ATCODER.

別解としてDP解法も載せておきます。

       IDENTIFICATION DIVISION.
       PROGRAM-ID. ATCODER.
       ENVIRONMENT DIVISION.
       INPUT-OUTPUT SECTION.
       FILE-CONTROL.
           SELECT SYSIN ASSIGN TO KEYBOARD ORGANIZATION LINE SEQUENTIAL.
       DATA DIVISION.
       FILE SECTION.
           FD SYSIN.
               01 INDATA PIC X(100000).
       WORKING-STORAGE SECTION.
           01 WK.
               03 S PIC X(100000).
               03 N PIC 9(15).
               03 I PIC 9(15).
               03 DP PIC X(1) OCCURS 100010 TIMES.
               03 ANS PIC 9(15).
               03 ANS-Z PIC Z(14)9.
       PROCEDURE DIVISION.
           OPEN INPUT SYSIN.
           READ SYSIN INTO S.
           CLOSE SYSIN.
           MOVE FUNCTION STORED-CHAR-LENGTH(S) TO N.
           MOVE "1" TO DP(1).
           PERFORM VARYING I FROM 1 BY 1 UNTIL I > N + 1
               IF DP(I) = "1" THEN
                   IF S(I:5) = "dream" THEN
                       MOVE "1" TO DP(I + 5)
                   END-IF
                   IF S(I:7) = "dreamer" THEN
                       MOVE "1" TO DP(I + 7)
                   END-IF
                   IF S(I:5) = "erase" THEN
                       MOVE "1" TO DP(I + 5)
                   END-IF
                   IF S(I:6) = "eraser" THEN
                       MOVE "1" TO DP(I + 6)
                   END-IF
               END-IF
           END-PERFORM.
               IF DP(N + 1) = "1" THEN
                   DISPLAY "YES"
               ELSE
                   DISPLAY "NO"
               END-IF.
           STOP RUN.
       END PROGRAM ATCODER.

10. ABC086C : Traveling

問題のリンク

最初の場所を(0,0)として、点i+1と点iのマンハッタン距離をD、次までの時間t_{i+1} - t_i = Tとすると、D \leq TかつT - Dが偶数であればよいです。

       IDENTIFICATION DIVISION.
       PROGRAM-ID. ATCODER.
       ENVIRONMENT DIVISION.
       INPUT-OUTPUT SECTION.
       FILE-CONTROL.
       DATA DIVISION.
       FILE SECTION.
       WORKING-STORAGE SECTION.
           01 WK.
               03 INP PIC X(100000).
               03 N PIC 9(15).
               03 I PIC 9(15).
               03 P OCCURS 100001 TIMES.
                   05 T PIC 9(6).
                   05 X PIC 9(6).
                   05 Y PIC 9(6).
               03 TI PIC 9(15).
               03 DIST PIC 9(15).
       PROCEDURE DIVISION.
           ACCEPT N.
           PERFORM VARYING I FROM 2 BY 1 UNTIL I > N + 1
               ACCEPT INP
               UNSTRING INP DELIMITED BY SPACE INTO T(I) X(I) Y(I)
           END-PERFORM.
           PERFORM VARYING I FROM 1 BY 1 UNTIL I > N
               COMPUTE TI = T(I + 1) - T(I)
               COMPUTE DIST = FUNCTION ABS(X(I + 1) - X(I)) +
                      FUNCTION ABS(Y(I + 1) - Y(I))
               IF TI < DIST OR FUNCTION MOD(TI - DIST, 2) = 1 THEN
                   DISPLAY "No"
                   STOP RUN
               END-IF
           END-PERFORM.
           DISPLAY "Yes".
           STOP RUN.
       END PROGRAM ATCODER.

最後に

これでAtCoder Beginners Selectionの問題はすべて解けました。
みなさんもコボラーになってみませんか?
自分も気力があればLanguage Ownerになるまで頑張ってみたいなと思います。