始めに

競技プログラミングサイトAtCoder にて、ソートがあると便利な問題を COBOL で解きました。

先の記事にて、クイックソートを実装しました。
https://qiita.com/ShinjiSHIBATA/items/1ef8cbf4b87969a46015

プログラミング言語には多くの場合ソートが備わっている為使うとラクができます。

「OpenCOBOL」「opensourceCOBOL」にもソートがあるのでこの記事に書きました。

1. 配列

COBOLでは変数や配列を「WORKING-STORAGE SECTION」に書きます。

VARIABLES_AND_ARRAYS.cob


WORKING-STORAGE                  SECTION.
    01 var     PIC 9(1).
    01 card1.
        03 card_num1  PIC 9(3).
        03 card_num2  PIC 9(3).
        03 card_num3  PIC 9(3).
        ～ 中略 ～
        03 card_num10 PIC 9(3).

ここで「01」や「03」はレベル番号と呼ばれます。
最上位「01」はレコードと呼ばれます。

レベル番号でデータ構造の従属関係を表現します。

「var」はレコードで符号なし数字 1 桁の変数。

「card1」はレコードでその従属項目として card_num1 ～ card_num10 の
10項目の符号なし数字 3 桁があります。

同じ属性の繰り返しを表現したものが配列になります。

ARRAYS.cob


    01 card1.
        03 card_num PIC 9(3) OCCURS 10 TIMES.

要素数 10 の配列ができました。
要素の 7 番目は card_num(7) で表現されます。

次に複数項目の繰り返しを表現した配列も定義できます。

MULTI_ITEM_ARRAYS.cob


    01 card1.
        03 card11 OCCURS 10 TIMES.
            05 card_num   PIC 9(3).
            05 card_color PIC X(10).

要素数 10 の配列で 2つの項目があります
card_num 符号なし数字 3 桁
card_color 文字 10 個の文字列
要素の 7番目は card_num ( 7 ) や card_color ( 7 ) で表現されます。

2. ABC 088 B Card Game for Two を解く

【問題概要】
N 枚のカード、i 番目のカードには ai という数が書かれています。
2 人が交互に最大の数のカードを取ります。取った数の合計が点数になります。
すべてのカードを取り終わった時、先手は後手より何点多く取るでしょうか。

【説明】
カードを並び替えて大きな数から
先手の取った数の合計、後手の取った数の合計を計算します。

カードを並び替えるクイックソートを実装しました。
実際の問題の Accepted なソースコードは下記になります。
https://beta.atcoder.jp/contests/abc088/submissions/2765069

行数を数えると 167 行。

「OpenCOBOL」「opensourceCOBOL」のソートを使ってもっとラクをしましょう。

「OpenCOBOL」「opensourceCOBOL」のソートの概要は下記の通りです。

【構文どおり】

SYNTAX_FORM.cob


    01 card1.
        03 card PIC 9(3) OCCURS 100 TIMES DEPENDING ON N.

    SORT card ON DESCENDING KEY card.

ソートの部分は配列の定義の 2 行を含めてたったの 3 行です。

「DEPENDING ON N」を説明します。
配列は最大 100 回の繰り返し項目です。要素数 100 です。
実際に配列に値が入っている (先頭からの) 要素の数は変数 N の値によるという定義です。

ソートするのに値が入っていない要素まで入れてしまうと結果がおかしくなる為
ソートする場合には必ず指定します。

「SORT card ON DESCENDING KEY card」を説明します。

最初の「card」は OCCURS を指定した項目 (OCCURS項目) です。
「DESCENDING」は「降順」、「ASCENDING」は「昇順」です。
二番目の「card」は実際にソートする時のキー項目 (KEY項目) です。

二回「card」が登場するところに違和感を感じるかもしれませんが
配列が複数の項目の場合には最初 (OCCURS項目) と二番目 (KEY項目) に指定する項目は
異なることがありますので必要となります。

ここで昇順ならば「ASCENDING」が省略できそうに思えますが
「DESCENDING」か「ASCENDING」は必ず指定する必要があります。

ここからさらに省略した書き方ができるので書きます。

【慣用的に略した書き方】

CONVENTIONAL_FORM.cob


    01 card1.
        03 card PIC 9(3) OCCURS 100 DEPENDING N.

    SORT card DESCENDING card.

配列定義の「TIMES」「ON」、ソートの「ON」「KEY」を慣用的に省略することができます。
忘れても思い出せる感じがとても良いと思います。

「OpenCOBOL」「opensourceCOBOL」のソートを使用した
実際の問題の Accepted なソースコードは下記になります。
https://beta.atcoder.jp/contests/abc088/submissions/2921407

行数を数えると 69 行。
行数 59 % の削減に成功しました。
それだけソースコードの見通しも良くなりバグが少なくなります。

3. ABC 042 B Iroha Loves Strings (ABC Edition) を解く

【問題概要】
長さ L の文字列が N 個あります。
これらの文字列を結合してできる文字列のうち辞書順最小を求めて下さい。

【説明】
要素数 N 個、文字 L 個の文字列の配列に、文字列を格納して昇順ソートします。
ソート後の文字列を順に結合することで解答となります。

「OpenCOBOL」「opensourceCOBOL」のソートを使用した
実際の問題の Accepted なソースコードは下記になります。
https://beta.atcoder.jp/contests/abc042/submissions/2918629

4. ABC 018 A 豆まき (改) を解く

【問題概要】
長男、次男、三男が豆まきをしました。
長男、次男、三男の得点が順に与えられます。得点が高いほうが上の順位です。
長男、次男、三男のそれぞれの順位を答えて下さい。

※長男、次男、三男の得点は異なるのが実際の問題ですが
　ここでは同じ得点の場合は、長男よりも次男、次男よりも三男のほうが上の順位とします。

【説明】
以下のような配列を用意します。

要素数 3
num 符号なし数字 1 桁
score 符号なし数字 3 桁
rank 符号なし数字 1 桁

num に何番目の値か (長男なら 1 次男なら 2 三男なら 3)
score に得点を格納してソートします。

この時のソートキーを以下のようにします。
複数キーソートです。

MULTI_KEY_SORT.cob


    SORT mame DESCENDING score
              DESCENDING num.

第 1 KEY項目は score で降順
第 2 KEY項目は num で降順

ソート後に最初から 1 から順に rank に格納します。

次に num で昇順ソートします。
ソート後に順に rank を出力することで解答となります。

【ソースコード】

MAME.cob

PROGRAM-ID.                      MAME.
DATA                             DIVISION.
WORKING-STORAGE                  SECTION.
    01 N       PIC 9(1).
    01 i       PIC 9(1).
    01 val     PIC 9(3).
    01 mame1.
        03 mame11 OCCURS 3 DEPENDING ON N.
            05 num   PIC 9(1).
            05 score PIC 9(3).
            05 rank  PIC 9(1).

PROCEDURE                        DIVISION.
    MOVE 3 TO N.

    PERFORM VARYING i FROM 1 BY 1 UNTIL N < i
        ACCEPT val
        MOVE i TO num(i)
        MOVE val TO score(i)
    END-PERFORM.

    SORT mame11 ON DESCENDING KEY score
                ON DESCENDING KEY num.

    PERFORM VARYING i FROM 1 BY 1 UNTIL N < i
        MOVE i TO rank(i)
    END-PERFORM.

    SORT mame11 ON ASCENDING KEY num.

    PERFORM VARYING i FROM 1 BY 1 UNTIL N < i
        DISPLAY rank(i)
    END-PERFORM.

    STOP RUN.

【入力】
100
100
100

【出力結果】
3
2
1

5. ABC 100 D Patisserie ABC を解く

【問題概要】
N 種類のケーキから重複なしで M 種類のケーキを選びます。

各種類のケーキには 3つの値があります。
「きれいさ xi」「おいしさ yi」「人気 zi」

3つの値 xi yi zi は 0 やマイナスの可能性もあります。

ケーキを選ぶときには
(xi の合計の絶対値)＋(yi の合計の絶対値)＋(zi の合計の絶対値) が
最大になるように選びます。

選んだ M 種類のケーキの
(xi の合計の絶対値)＋(yi の合計の絶対値)＋(zi の合計の絶対値) の
最大値を求めて下さい。

制約は下記の通りです。
N 1 以上 1000 以下。
M 0 以上 N 以下。
xi yi zi それぞれマイナス10の11乗以上プラス10の11乗以下。

【説明】
5 種類のケーキから重複なしで 3 種類のケーキを選ぶ場合を考えます。

「きれいさ xi」「おいしさ yi」「人気 zi」の 3つの値には正と負があります。

合計の絶対値を大きくするように取得する為 3つの値で
「正の方向に最大化する」「負の方向に最大化する」のどちらを選ぶか
2の3乗 = 8 通りについて計算します。

次にそれぞれを降順ソートして上から 3 種類選びます。
選んだ 3種類を合計したもののうち最大値が解答となります。

実際の問題の Accepted なソースコードは下記になります。
https://beta.atcoder.jp/contests/abc100/submissions/2964768

6. ABC 105 D Candy Distribution を解く

【問題概要】
左右一列に並んだ N 個の箱があります。
左から i 番目の箱には Ai 個のあめが入っています。

連続した箱からあめを取り出して M人に均等にくばります。

左端を l 右端を r としたとき、以下の関係が成り立ちます。
1 <= l <= r <= N
Al + Al+1 + … + Ar は Mの倍数

組 (l, r) の総数を求めて下さい。

制約は下記の通りです。
N 1 以上 10の5乗以下
M 2 以上 10の9乗以下
Ai 1 以上 10の9乗以下

【説明】
13 個の箱から選び 17人に均等にくばる以下の場合を考えます。

10 番目の箱 ( i = 10 ) から、13 番目の箱 ( i = 13 ) まで
4 個の箱のあめの合計が 187 個で 17 で割り切れます。

これは 10 番目の箱 ( i = 10 ) の直前の
9 番目の箱 ( i = 9 ) までのあめの累積和を 17 で割った余りが 0 で
13 番目の箱 ( i = 13 ) までのあめの累積和を 17 で割った余りが 0 の為
17 で割りきれます。

割った余りが 0 でなくても、左端の直前と右端で割った余りが同じであれば良いです。
例えば 11 番目の箱から、12 番目の箱のあめの合計 51 は 17 で割り切れます。
この場合左端の直前 ( i = 10 ) と右端 ( i = 12 ) で割った余りが 4 で同じです。

したがって、累積和と余りをもとめて余りごとに同じ余りの数をもとめて
左端と右端の組の数をもとめます。

さらに余りがゼロの場合だけ
一番左端から左端の直前までと一番左端から右端までの 2 通りを
先にもとめた数にたしあわせることで解答となります。

余りと同じ余りの数は、C++では map などの連想配列が便利ですが
「OpenCOBOL」「opensourceCOBOL」にはありませんので一旦余りをソートしてから
同じ余りの数をかぞえます。

余りについては「OpenCOBOL」「opensourceCOBOL」に MOD関数がありますが
大きな数の MOD で誤った数が算出される事象を観測しました。

※具体的な値は不明ですが、以下の Wrong Answer と Accepted のソースコード差分は
　MOD をするか自力で計算をするかのごくわずかの違いでした。

【Wrong Answer】
https://beta.atcoder.jp/contests/abc105/submissions/3002200

【Accepted】
https://beta.atcoder.jp/contests/abc105/submissions/3002251

【差分】左：Wrong Answer 右：Accepted

自力で計算することをおすすめします。

X を M で割った商を D に余りを R に格納する下記の構文を使います。
DIVIDE M INTO X GIVING D REMAINDER R

実際の問題の Accepted なソースコードは下記になります。
https://beta.atcoder.jp/contests/abc105/submissions/3002629

当問題では入力が 8,191 桁以上となる為 ACCEPTコマンドは使用できません。
記事「AtCoder ABC 入力大き目を COBOL で解いてみた」の内容をもとに
標準入力を READ 文にリダイレクトすることで回避しています。
https://qiita.com/ShinjiSHIBATA/items/af3c9a6a8dd26233dc7e

以上です。

AtCoder ABC ソート を COBOL で解いてみた

始めに