始めに
競技プログラミングサイトAtCoder にて
AtCoder Beginner Contest (以下ABC) 最新回 (2018年7月15日現在) の
第102回から さかのぼって第55回まで、AとBの問題を全て解いてみました。
競技プログラミングは C++ で参加していましたが
仕事で COBOL を使うことになりそうなので練習することが目的でした。
結論を先に申し上げておきます。
とても楽しかったです。
※2018年8月4日
投稿当初は「競技プログラミングとして COBOL を選択することは厳しい」主旨で書きました。
ところが ACCEPTコマンド 8,191 桁 以上 入力ができない件について 回避策がありました。
今は「競技プログラミング を COBOL で出来るところまでやってみよう」と思います。
※2018年9月21日
「OpenCOBOL」や「opensource COBOL」での
競技プログラミングのコンテストへの参加をあきらめました。
理由は
競技プログラミングサイトAtCoder の AtCoder Beginner Contest
D問題 (ABC 107 D Median of Medians) でどのように工夫しても
解くことが出来なかった為です (TLE:Time Limit Exceeded [実行時間制限超過] )。
ボトルネックとなったのは、演算なかでもビット演算の遅さです。
この点について、いずれは書きたいと思っています。
ただ 時間 も 体力 も 現在のところ追いついていません。
しばらく先のことになりそうです。
AtCoder Beginner Contest でも、Java以上のパフォーマンスが必要とされる問題があり
コンテストで使用する言語を別の言語とした次第です。
自宅環境
Windows
Panasonic Let's note CF-SX1GEPDR
Windows 7 Professional Service Pack 1
Intel Core i5-2540M CPU @ 2.60GHz
メモリー 8GB
64bit
フットペダル Kinesis Foot Switch［FP30A］左:Ctrl 中:Tab 右:Alt
仮想マシン
Oracle VM VirtualBox バージョン5.2.12 r122591 (Qt5.6.2)
Ubuntu 16.04.4 LTS (Xenial Xerus)
ブラウザ Conkeror 1.0.4
テキストエディタ Emacs 25.3.2
スニペット yasnippet
COBOL
opensource COBOL 1.5.1J
下記を参照しました。
https://kunst1080.hatenablog.com/entry/2017/05/27/001523
競技プログラミングサイトAtCoder では 言語 として下記を選択します。
COBOL-Free (OpenCOBOL)
「opensource COBOL」 は
OSSコンソーシアムにより2012年に 「OpenCOBOL」 1.1 Pre-release より
フォークされたものであり、「OpenCOBOL」 は 「opensource COBOL」の親です。
COBOL-Free と COBOL-Fixed
コンパイルオプションの違い
【COBOL-Freeの場合】 cobc -x -free a.cob
【COBOL-Fixedの場合】 cobc -x -fixed a.cob
COBOL-Free は 正書法の自由形式
COBOL-Fixed は 正書法の固定形式、可変形式
COBOL-Fixed は 何桁目はこの文字でないとダメみたいな
プログラムの記述制約があります。
7文字目は「標識領域」と呼ばれ、入力は下記あるいは半角スペースに限定されます。
・「-」ハイフン 行つなぎ
・「*」「/」アスタリスクまたはスラッシュ コメント行
・「D」 コメント行
このようなプログラムの記述制約のない「COBOL-Free」を選択した方が
競技プログラミングする上で吉と判断しました。
1. ローカル変数がない
COBOLでの変数はすべてグローバル変数でスタティックな変数です。
この事が思わぬ事態を招くことになります。
「再帰」が出来ないのです。
昇順に並び替えするクイックソートを
あたかも「再帰」が出来るように書いてみます。
3箇所の「PERFORM QSORT」に注目して下さい。
長いなりに秩序立てて書けました。コンパイルも通るのですが。
PROGRAM-ID. QUICK_SORT_NG.
DATA DIVISION.
WORKING-STORAGE SECTION.
01 INP PIC X(600).
01 maxlen PIC 9(3).
01 cur PIC 9(3) VALUE 1.
01 i PIC 9(18).
01 j PIC 9(18).
01 len PIC 9(3).
01 N PIC 9(3).
01 qary1.
03 qary11 OCCURS 100.
05 qary PIC 9(3).
01 a PIC 9(3).
01 b PIC 9(3).
01 t PIC 9(3).
01 x PIC 9(3).
01 qfirst PIC 9(3) VALUE 1.
01 qlast PIC 9(3).
01 q PIC 9(3).
01 ZS PIC Z(4)9.
01 ans PIC X(3).
01 DUMMY PIC X(1).
PROCEDURE DIVISION.
ACCEPT N.
ACCEPT INP.
MOVE N TO maxlen.
PERFORM VARYING i FROM 1 BY 1 UNTIL maxlen < i
PERFORM VARYING j FROM cur BY 1
UNTIL INP(j:1) = SPACE
END-PERFORM
COMPUTE len = j - cur
MOVE INP(cur:len) TO qary(i)
COMPUTE cur = j + 1
END-PERFORM.
MOVE N TO qlast.
PERFORM QSORT.
PERFORM VARYING i FROM 1 BY 1 UNTIL N < i
MOVE qary(i) TO ZS
PERFORM UNANS
DISPLAY ans(1:FUNCTION STORED-CHAR-LENGTH(ans))
END-PERFORM.
STOP RUN.
UNANS SECTION.
UNSTRING
ZS DELIMITED BY ALL SPACE
INTO DUMMY ans
END-UNSTRING.
PARTITION SECTION.
MOVE qary(qlast) TO x
MOVE qfirst TO a
SUBTRACT 1 FROM a
PERFORM VARYING b FROM qfirst BY 1 UNTIL qlast <= b
IF qary(b) <= x THEN
ADD 1 TO a
MOVE qary(a) TO t
MOVE qary(b) TO qary(a)
MOVE t TO qary(b)
END-IF
END-PERFORM
ADD 1 TO a
MOVE qary(a) TO t
MOVE qary(qlast) TO qary(a)
MOVE t TO qary(qlast)
MOVE a TO q.
QSORT SECTION.
IF qfirst < qlast THEN
PERFORM PARTITION
*> qfirst そのまま
*> qlast マイナス1
SUBTRACT 1 FROM qlast
PERFORM QSORT
*> qfirst プラス1
*> qlast そのまま
ADD 1 TO qfirst
PERFORM QSORT.
【入力】
7
11 56 22 42 87 81 52
【出力結果】
11
22
42
52
81
87
56
52 の次が 56 になるべきところに 81 が来ています。
このプログラムでは 分割統治法 ならびに クイックソート を用いています。
まず左側を処理して残りの右側を処理します。
ところが、変数はグローバルであり、スタティックだから
右側を処理する時には本来処理しなければならないパラメータ値は
左側を処理した時に上書きされ、失われることになるのです。
仕方がありません。
最初に左右分けた時に、値を配列に保持するしかありません。
PROGRAM-ID. QUICK_SORT_OK.
DATA DIVISION.
WORKING-STORAGE SECTION.
01 INP PIC X(600).
01 maxlen PIC 9(3).
01 cur PIC 9(3) VALUE 1.
01 i PIC 9(18).
01 j PIC 9(18).
01 len PIC 9(3).
01 N PIC 9(3).
01 qary1.
03 qary11 OCCURS 100.
05 qary PIC 9(3).
01 a PIC 9(3).
01 b PIC 9(3).
01 t PIC 9(3).
01 x PIC 9(3).
01 qfirst PIC 9(3) VALUE 1.
01 qlast PIC 9(3).
01 q PIC 9(3).
01 ZS PIC Z(4)9.
01 ans PIC X(3).
01 DUMMY PIC X(1).
*> 変数追加 ここから
01 stack1.
03 stack11 OCCURS 1000.
05 st PIC 9(3).
05 ed PIC 9(3).
01 sidx PIC 9(4) VALUE 0.
01 nowidx PIC 9(4) VALUE 0.
01 sttmp PIC 9(3).
01 edtmp PIC 9(3).
01 ret PIC 9(3).
01 bk PIC 9(3).
01 FLG PIC 9(1).
*> 変数追加 ここまで
PROCEDURE DIVISION.
ACCEPT N.
ACCEPT INP.
MOVE N TO maxlen.
PERFORM VARYING i FROM 1 BY 1 UNTIL maxlen < i
PERFORM VARYING j FROM cur BY 1
UNTIL INP(j:1) = SPACE
END-PERFORM
COMPUTE len = j - cur
MOVE INP(cur:len) TO qary(i)
COMPUTE cur = j + 1
END-PERFORM.
MOVE N TO qlast.
*> ここから
*> 1行でよかったつもりが
*> PERFORM QSORT.
PERFORM PARTITION.
MOVE 1 TO FLG.
PERFORM UNTIL FLG = 0
PERFORM QSORT
IF FLG = 0 THEN
IF nowidx < sidx THEN
MOVE 1 TO FLG
ADD 1 TO nowidx
MOVE st(nowidx) TO qfirst
MOVE ed(nowidx) TO qlast
PERFORM PARTITION
END-IF
END-IF
END-PERFORM.
*> ここまで
PERFORM VARYING i FROM 1 BY 1 UNTIL N < i
MOVE qary(i) TO ZS
PERFORM UNANS
DISPLAY ans(1:FUNCTION STORED-CHAR-LENGTH(ans))
END-PERFORM.
STOP RUN.
UNANS SECTION.
UNSTRING
ZS DELIMITED BY ALL SPACE
INTO DUMMY ans
END-UNSTRING.
PARTITION SECTION.
MOVE qary(qlast) TO x
MOVE qfirst TO a
SUBTRACT 1 FROM a
PERFORM VARYING b FROM qfirst BY 1 UNTIL qlast <= b
IF qary(b) <= x THEN
ADD 1 TO a
MOVE qary(a) TO t
MOVE qary(b) TO qary(a)
MOVE t TO qary(b)
END-IF
END-PERFORM
ADD 1 TO a
MOVE qary(a) TO t
MOVE qary(qlast) TO qary(a)
MOVE t TO qary(qlast)
MOVE a TO q.
QSORT SECTION.
*> 値の保持を行う為、大幅に修正
*> IF qfirst < qlast THEN
*> PERFORM PARTITION
*>
*> SUBTRACT 1 FROM qlast
*> PERFORM QSORT
*>
*> ADD 1 TO qfirst
*> PERFORM QSORT.
IF qfirst < qlast THEN
MOVE q TO ret
MOVE qlast TO bk
SUBTRACT 1 FROM ret GIVING qlast
ADD 1 ret GIVING sttmp
MOVE bk TO edtmp
IF sttmp < edtmp THEN
ADD 1 TO sidx
MOVE sttmp TO st(sidx)
MOVE edtmp TO ed(sidx)
END-IF
IF qfirst < qlast THEN
PERFORM PARTITION
ELSE
MOVE 0 TO FLG
END-IF
ELSE
MOVE 0 TO FLG
END-IF.
【入力】
7
11 56 22 42 87 81 52
【出力】
11
22
42
52
56
81
87
手間はかかりますが、なんとか想定通りソートできました。
実際の問題の Accepted なソースコードは下記になります。
https://beta.atcoder.jp/contests/abc088/submissions/2765069
ここで注意があります。
本記事記載のプログラムは、競技プログラミングサイトAtCoder の
コードテストページにて「言語」COBOL-Free (OpenCOBOL)で実行可能です。
「ソースコード」テキストボックス入力の際には
～最後の処理～.←ここで改行
←最後にもう一度改行
で終わるようにして下さい。(そうでなければコンパイルエラーになります。)
「標準入力」テキストボックス入力の際には
入力値末尾に半角スペース(下記△)を入れて下さい。
7△
11 56 22 42 87 81 52△
HTML画面からの入力では末尾に半角スペースをつけないと
上手くいきません。
※2018年7月30日
実際 ソート を 最初から 手作り する必要はなく
「OpenCOBOL」や「opensource COBOL」 には 既に ソート が備わっています。
記事「AtCoder ABC ソート を COBOL で解いてみた」を追加しました。
https://qiita.com/ShinjiSHIBATA/items/ea1fb8b3e98c752f3dac
2. ACCEPTコマンド は 8,191 桁 以上は入力できない (回避策あり)
次のプログラムを実行してみます。
PROGRAM-ID. INPUT_LENGTH.
DATA DIVISION.
WORKING-STORAGE SECTION.
01 INP PIC X(10000).
PROCEDURE DIVISION.
ACCEPT INP.
DISPLAY FUNCTION STORED-CHAR-LENGTH(INP)
STOP RUN.
【入力】
12345678901234567890… (同じ要領で1万桁)
こちらも 競技プログラミングサイトAtCoder のコードテストページで実行する場合は
「ソースコード」テキストボックス、～最後の処理～.改行、最後にもう一度改行とします。
「標準入力」テキストボックス、入力値末尾に半角スペースを入れます。
作業端末でコンソールから実行する場合はどちらも不要です。
【出力】
【コードテストページ】
00008190
【作業端末】
00004095
ソースコード上の FUNCTION STORED-CHAR-LENGTH は
変数に格納されている値の桁数 (末尾スペースを除く) を
取得する関数です。
残念ながら 1万桁 の文字列を入力しても
変数には途中までしか格納されていないことが分かります。
先人の方からも以下のサイトで同様のご指摘があります。
https://qiita.com/moment/items/be1f62f423ee0d5c91d2
いろいろ調べましたが、はっきりとした根拠は見つかりませんでした。
試した結果から申し上げますと、ACCEPTコマンドでは一定桁数以上入力が出来ず
その桁数は環境依存で、これは言語(opensource COBOL)の仕様であるようです。
実際の問題の Wrong Answer なソースコードは下記になります。
https://beta.atcoder.jp/contests/abc072/submissions/2798600
こんなことで競技プログラミングで競い合うことができるのでしょうか。
競技プログラミングサイトAtCoder の ABC 最新回の第102回まで
問題A〜問題Dまでの制約を確認しました。
8,191 桁 以上の入力が制約より想定される問題数
| A問題 | B問題 | C問題 | D問題 |
|---|---|---|---|
| 0 | 5 | 28 | 26 |
ひとつのコンテストにつき A問題 から D問題 までに
一つでも 8,191 桁 以上の入力が制約より想定されるコンテスト数は
42回 でした。
大きな入力桁を求められている制約で多く見かけるのは
文字列 |S| < 10 の 5乗 や
空白区切りの数列、要素数がやはり 10 の 5 乗くらいですね。
※2018年8月4日
ACCEPTコマンド 8,191 桁 以上 入力ができない件について 回避策がありました。
記事「AtCoder ABC 入力大き目 を COBOL で解いてみた」を追加しました。
https://qiita.com/ShinjiSHIBATA/items/af3c9a6a8dd26233dc7e
3. ビット演算 の 組み込み関数 について (CBL_AND) (CBL_OR) (CBL_XOR) (CBL_NOT)
シフト演算 や ビット演算 を 使いたくなる時があります。
シフト演算 くらいなら、掛ける割るで良い気がしますが
ビット で 何かしたくなる時があります。
C++ならば色々あります。
/* Nビット目を取り出す */
(n >> N) & 1
/* Nビット目に1をセットする */
n = n | (1 << N);
/* Nビット目に0をセットする */
n = n & ~(1 << N);
/* Nビット目を反転 */
n = n ^ (1 << N);
ビット演算から話は異なりますが
「OpenCOBOL」や「opensource COBOL」 には bool型 がありません。
数字 1桁 の 0 、1 になります。
※hanotchさんから貴重なコメントを頂きました。
ビット演算について知見が深まりました。
まず『OpenCOBOL Programmer's Guide』で Google 検索して
PDFをダウンロードしました。
内容は英語ですが、とても充実した内容となっております。
もし 「OpenCOBOL」や「opensource COBOL」 でプログラミングされるご予定がある方は
是非、手に入れて参考にされる事をお勧めします。
8.2 節のサンプルプログラム「COBDUMP」で
変数の値をダンプすることができます。
PROGRAM-ID. BITWISE_OPERATION.
DATA DIVISION.
WORKING-STORAGE SECTION.
01 v PIC X(4) value X"【入力2】".
PROCEDURE DIVISION.
CALL "【CALLするプログラム】" USING X"【入力1】", v, BY VALUE 4.
CALL "COBDUMP" USING v.
END PROGRAM BITWISE_OPERATION.
>>SOURCE FORMAT IS FIXED
IDENTIFICATION DIVISION.
PROGRAM-ID. COBDUMP.
～以降、8.2 節のサンプルプログラム「COBDUMP」～
【入力1】
10101111
【入力2】
00010101
【CALLするプログラム】が CBL_AND の場合の出力
出力結果
00 00 01 01
【CALLするプログラム】が CBL_OR の場合の出力
出力結果
10 11 11 11
【CALLするプログラム】が CBL_XOR の場合の出力
出力結果
10 11 10 10
【CALLするプログラム】が CBL_NOT の場合の出力
単一の変数 (結果が自身の変数に入る) なので文法は下記となります。
～前略～
01 v PIC X(4) value X"10101111".
～中略～
CALL "CBL_NOT" USING v, BY VALUE 4.
出力結果
EF EF EE EE
16進数での演算結果の為、このようになります。
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | A | B | C | D | E | F |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| F | E | D | C | B | A | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
(上段：CBL_NOT の 演算対象 の 数字)
(下段：CBL_NOT の 演算結果 の 数字、上段を反対にひっくり返したものです。)
1 の CBL_NOT で対応する項目は E です。
0 の CBL_NOT で対応する項目は F です。
たとえば「AAAAAAAA」ならば
出力結果「55555555」になります。
「COBDUMP」は嬉しいことにサンプルプログラムだから
内容を理解して工夫すれば、意図したビットを操作することができるかもしれません。
※2018年7月22日
記事「AtCoder ABC ビット演算 を COBOL で解いてみた」を追加しました。
https://qiita.com/ShinjiSHIBATA/items/a668b1c9ecebde58287d
hanotchさん
勉強になります。
有難うございます。
4. プライオリティーキューなどがない
ダイクストラ法で使用することになります。
ないと言っても仕方がなく、C# にもないわけで、その場合は自作になります。
余談:「仕事でプログラミングをする人」にとっての競技プログラミング
「仕事でプログラミングをする人」は、競技プログラミングサイトAtCoder の コンテスト で
どのくらいの パフォーマンス レーティング となるか関心のある方はいらっしゃいませんか。
個人差があり一概に言えませんが、私個人で考えていることを書きます。
仕事で使う、あるいは近いうちに使う予定がある言語であれば、
その言語で AtCoder Beginner Contest の A～B問題 を 制限時間内 にやっつけることが
出来なければ、仕事では使えない実力でしょう。
実際にコンテストで正答 (AC:Accepted) にかかる時間によって
レーティング も大きく変わりますが、A～B問題 を 確実 に 制限時間内 に
やっつけることが出来るのが レーティング 800～1200 (緑色) 相当です。
競技プログラミングは 標準入出力 を使いますが、仕事で意識しない方もいらっしゃいます。
「仕事でプログラミングをする人」ならば、このあたりの知識は
いろいろなサイト 他の参加者の解答より容易に習得することでしょう。
もちろん「仕事でプログラミングをする人」でも準備期間は必要です。
一生懸命やるのであれば、上記 レーティング に到達するのに 1～2週間 でしょう。
ただ、少し弁解 (言い訳?) をさせて下さい。「仕事でプログラミングをする人」と言えども、
一つの言語だけを使っていれば一生過ごせる時代ではないのです。
従事する案件によって、言語が変わることはめずらしくなく、
その都度 新しい言語を意欲的に学習する必要があるのです。
コンテストに参加する言語を、仕事にあわせて挑戦している人もいます。(私です)
全くの初心者が上記レーティングに到達するのはそれなりに大変でしょう。
でも、「仕事でプログラミングをする人」も目先の案件の為に日夜努力していて
苦労しています。
強くなりたい、早く解けるようになりたいと強く思い、努力を惜しまなければ、
必ず人は成長します。
その意味では、上記の目安もまた、個人差はあれ、努力次第と言えますし、
上記のような「仕事でプログラミングをする人」なら
この パフォーマンス レーティング といった目安すら必要無いと言えるでしょう。
終わりに
最初の意気込みとしては
『できる人は配列があればなんでもできる』という意気込みでした。
色々試しているなかで、出来ないことがあると意気込みが弱くなったりもします。
世の中には数多くの プログラミング言語 があるので、人により合う合わないもあります。
自分にあった プログラミング言語 で 競技プログラミング を 楽しめると良いですね。
COBOL はプログラミング言語の歴史の中ではかなり初期に登場し
現在動いているプログラムの中でも多いと聞きます。
各時代のパラダイムの中でプログラミング言語は誕生しています。
COBOL が誕生した時の使われ方として、8,191桁 も渡ってくることもなければ
ローカル変数が必要となる再帰も必要なかったのでしょう。
再帰は何か障害があった時に、原因究明が難しくなってしまうことがあるようです。
グローバル変数の値がこの値で、何行目でエラーが発生したというのがより簡単であり、
COBOL は再帰が出来ないではなくて、やらなかったのかもしれません。
以上です。