始めに
競技プログラミングサイトAtCoder にて 入力大き目 (文字列の大きさが10の5乗レベル) の
問題 を COBOL で解きました。
先の記事にて
https://qiita.com/ShinjiSHIBATA/items/1ef8cbf4b87969a46015
ACCEPTコマンド は 8,191 桁 以上は入力できない事に触れました。
「OpenCOBOL」「opensourceCOBOL」でも 入力大き目(文字列の大きさが10の5乗レベル) の
問題 を 解くことが出来る ACCEPTコマンド に 代わる方法 がありますので
この記事に書きました。
#1. サンプルプログラム
「OpenCOBOL」「opensourceCOBOL」では
標準入力 を READ 文 に リダイレクトすることができます。
PROGRAM-ID. READ_INPUT_LENGTH.
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(10000).
WORKING-STORAGE SECTION.
01 INP PIC X(10000).
PROCEDURE DIVISION.
OPEN INPUT SYSIN.
READ SYSIN INTO INP.
CLOSE SYSIN.
DISPLAY FUNCTION STORED-CHAR-LENGTH(INP)
STOP RUN.
本記事記載のプログラムは、競技プログラミングサイトAtCoder の
コードテストページにて「言語」COBOL-Free (OpenCOBOL)で実行可能です。
競技プログラミングサイトAtCoder での実行時の注意点については
先の記事を参照下さい。
https://qiita.com/ShinjiSHIBATA/items/1ef8cbf4b87969a46015
【入力】
12345678901234567890… (同じ要領で1万桁)
【出力】
【コードテストページ】
00010000
1万桁 の文字列を入力した場合に 変数に 1万桁 格納されていることが分かります。
これで 入力大き目 (文字列の大きさが10の5乗レベル) の問題に挑戦できます。
#2. ABC 072 B OddString を解く
【問題概要】
ある半角の文字列 s が与えられます。
前から奇数文字目だけ抜き出して作った文字列を出力してください。
与えられる文字列の大きさ | s | は 1 以上 10の5乗 以下です。
【説明】
まずは 単一の文字列 の操作における 入力大き目 を見ていきます。
「OpenCOBOL」「opensourceCOBOL」 では 文字列 を切り出す以下の 構文 があります。
文字列が格納された変数 ( start : length )
ここで start は 開始位置 (最小1) です。
「OpenCOBOL」「opensourceCOBOL」は 文字列 も 配列 も 1-indexed です。
length は 切り出す文字数 です。終了位置 ではないので 注意 が必要です。
これを使って 文字列の 1文字目 から 文字列の最後まで
奇数文字列だけ 1文字 を 文字列 に追記していくことで 解答 となります。
「OpenCOBOL」「opensourceCOBOL」 では 文字列を配列としても扱う事が出来ます。
WORKING-STORAGE SECTION.
01 s1.
03 s PIC X(1) OCCURS 100000.
上記は 文字 1 個 の 10の5乗 回 繰り返しの文字列 s1 を 定義 しています。
文字 の 7番目 は s ( 7 ) で表現されます。
文字列 s1 の 長さ は FUNCTION STORED-CHAR-LENGTH ( s1 ) で 取得 できます。
実際の問題の Accepted なソースコードは下記になります。
https://beta.atcoder.jp/contests/abc072/submissions/2939143
#3. ABC 049 C 白昼夢/Daydream を解く
【問題概要】
ある半角の文字列 S が与えられます。
与えられる文字列の大きさ | S | は 1 以上 10の5乗 以下です。
この半角の文字列 S が 以下の単語を単語単位で組み合わせることで
同じ文字列にすることできるか判定して下さい。
指定の単語 = {"dream", "dreamer", "erase", "eraser"}
【説明】
まず文字列 S から 指定の単語 を 取り除いていくことが考えられます。
よく考えてみると そのやり方では 以下のようなケースがうまくいきません。
文字列 S が dredreamam の場合、同じ文字列に出来ないことが解答となりますが
文字列 S から dreamを取り除くと dre「dream」am から dream が現れた結果
同じ文字に出来るという間違えた解答となります。
そこで 最末尾から 指定の単語 と 一致した場合にのみ
最末尾の 指定の単語 を取り除くことで 正しく 判定できます。
取り除く方法 は いくつかあると思いますが 今回は以下の方法を紹介します。
MOVE ALL SPACE TO S ( len - wordlen + 1 : wordlen )
ここで len は 文字列 S の 長さ
wordlen は 指定単語の文字数 dreamer ならば 7 になります。
先に 文字列 を切り出す構文を紹介しました。
その構文により 切り出した位置に 切り出した文字数分 特定の文字で上書き出来ます。
ここでは 最末尾の 指定の単語 の「全ての文字」 を 半角スペース としています。
ALL を指定することで 「全ての文字」という解釈になります。
この構文の注意点は「:」以降の数字が表すのは 文字数 で 終了位置ではない事です。
実際の問題の Accepted なソースコードは下記になります。
https://beta.atcoder.jp/contests/abc049/submissions/2940114
#4. ABC 103 C Modulo Summation を解く
【問題概要】
N 個 の 正整数 a1 ～ aN が与えられます。
非負整数 m に対して f ( m ) = ( m mod a1 ) + ( m mod a2 ) + … + ( m mod aN ) とします。
ここで X mod Y は X を Y で割った余りです。
f の 最大値 を求めてください。
制約が 2 <= N <= 3000、2 <= ai <= 10 の 5乗 です。
入力の形式は 下記の通りです。
N
a1 a2 … aN
【説明】
空白区切りの数列 における 入力大き目 の問題です。
「OpenCOBOL」「opensourceCOBOL」 では 入力 は 行単位で取得します。
制約から 空白区切りの数列 の 行 が 最大で何桁になるか を確認します。
数列の数字は 1つにつき最大で 10 の 5乗 よって 6桁。
それが 最大で 3000 個 あり、区切りの空白が 2999 個
よって 6 × 3000 + 2999 = 20999 桁になります。
空白 で 要素 を 切り出す為 末尾にスペースが一つ欲しいので 21000 桁
これより大きな項目定義であれば 入力された数列を取得できます。
数列が 3 と 4 だった場合
余りの最大 2 と 余りの最大 3 を足した 5 が 解答になります。
これは 3 × 4 - 1 = 11 が 数列の要素の 3 で割った余りの最大 ( 2 ) であり
数列の要素の 4 で割った余りの最大 ( 3 ) であるからです。
その為、得られた数列 の 各要素 から 1 引いたもの を足し込むことで解答となります。
実際の問題の Accepted なソースコードは下記になります。
https://beta.atcoder.jp/contests/abc103/submissions/2948036
#5. ABC 104 D We Love ABC を解く
【問題概要】
文字列 S が 与えられます。
与えられる文字列の大きさ | s | は 3 以上 10の5乗 以下です。
S の それぞれの文字 は 'A'、'B'、'C'、'?' の いずれかです。
'?' を 'A'、'B'、'C' いずれかに 置き換える ことで
3の ('?'の数) 乗 の文字列が得られます。
得られた文字列 の 文字 のうち 3文字 に ○ をつけます。
○ をつけた 文字 を 左から読むと 「ABC」となる 場合の数 を求めて下さい。
この 場合の数 は 非常に大きくなりうるため 場合の数 を
10の9乗 + 7 で 割った 余り を 出力して下さい。
【説明】
2次元 dp配列 を 使います。
他の多くの言語では dp [ i ] [ j ] という 書き方をしますが
「OpenCOBOL」「opensourceCOBOL」は dp ( i △ j ) と書きます。
ここで △ は 半角スペース です。
*> 定義 例
01 dp1.
03 dp11 OCCURS 100001.
05 dp PIC 9(20) OCCURS 4.
*> 初期化 例
MOVE ZERO TO dp(len + 1 2).
MOVE ZERO TO dp(len + 1 2).
MOVE ZERO TO dp(len + 1 3).
MOVE 1 TO dp(len + 1 4).
文字列 S が 「ABC?」 の 場合 を考えます。
見ている文字 が 何文字目 か ( i ) と これまで ○ にした 文字数 + 1 ( j ) の
2次元 dp配列 dp ( i j ) を 以下の要領で i j の 降順 に 更新していきます。
ある dp 配列の要素に、他の要素からもらっているように見える為
「もらうDP」と呼ばれています。
dp ( 1 1 ) が 解答となります。
実際の問題の Accepted なソースコードは下記になります。
https://beta.atcoder.jp/contests/abc104/submissions/2979978
余談
自宅環境では 入力大き目 (文字列の大きさが10の5乗レベル) に 対応出来ていません。
Ubuntu 16.04.4 LTS (Xenial Xerus)
opensource COBOL 1.5.1J
その原因が 厳密には 作業端末(Ubuntu) の コンソール の 入力値上限 なのか
「opensource COBOL」の 入力値上限 なのか 判断が付きません。
自宅環境の コンソール から以下のコマンドを実行します。
$ xargs --show-limits
結果として以下が出力されます。
環境変数が 3723 バイトを占めます
POSIX の引数の長さ上限 (このシステム): 2091381
POSIX の最小の引数の長さの上限 (すべてのシステム): 4096
実際に使用できるコマンド長の最大値: 2087658
実際に使用しているコマンドバッファの大きさ: 131072
Maximum parallelism (--max-procs must be no greater): 2147483647
POSIX の最小の引数の長さの上限 というのが _POSIX_ARG_MAX というパラメータで
この値 と 実際に格納される文字数 4095 が近いことから
現在 作業端末(Ubuntu) の コンソール の 入力値上限と考えています。
この点について 進展がありましたら この記事に書きます。
終わりに
ACCEPTコマンド は 8,191 桁 以上は入力できない事には 大変衝撃を覚えました。
競技プログラミングとして COBOL を選択することは厳しいと思いました。
ところが「OpenCOBOL」「opensourceCOBOL」では
標準入力 を READ 文 に リダイレクトすることができ 回避出来ることが分かった為
解くことができる問題が多くなりました。
以上です。