はじめに
前々回の記事、前回の記事でCOBOLの基礎知識について記載してきました。
では実際に、AtCoderに登録したら解くべき精選過去問10問ことAtCoder Beginners Selectionの問題を解いていきます。
- はじめに
- 0. PracticeA : Welcome to AtCoder
- 1. ABC086A : Product
- 2. ABC081A : Placing Marbles
- 3. ABC081B : Shift only
- 4. ABC087B : Coins
- 5. ABC083B : Some Sums
- 6. ABC088B : Card Game for Two
- 7. ABC085B : Kagami Mochi
- 8. ABC085C : Otoshidama
- 9. ABC049C : 白昼夢
- 10. ABC086C : Traveling
- 最後に
0. PracticeA : Welcome to AtCoder
UNSTRING
文で入力をB
とC
に分解しましょう。
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
を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
なので、の枚数の選び方を全探索すればよいです。
多重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)のようなものが存在しないため、楽には解けません。
幸いこの問題は条件がと緩いため、長さ100の配列を用意して要素を入れていき、要素が入っている数をカウントする方法(バケット法)が使えます。
計算量はです。
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.
ただしこの方法はのような条件では使えないため、その場合はをソートして前後が異なる要素をカウントしていく方法を使えばで解けます。
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 : 白昼夢
制約がのため、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
最初の場所をとして、点と点のマンハッタン距離を、次までの時間とすると、かつが偶数であればよいです。
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になるまで頑張ってみたいなと思います。