始めに
競技プログラミングサイトAtCoder にて ビット演算 が必要な問題 を COBOL で解きました。
先の記事にて
https://qiita.com/ShinjiSHIBATA/items/1ef8cbf4b87969a46015
「OpenCOBOL」「opensourceCOBOL」には ビット演算 の 組み込み関数 がある事に触れました。
(CBL_AND) (CBL_OR) (CBL_XOR) (CBL_NOT)
これらは 16進数 で演算される為、10進数 と 16進数 の相互の変換が必要になります。
また ビット演算 の 成功と失敗 を 2進数 で確認します。
その準備 と 競技プログラミングサイトAtCoder ABC の ビット演算が必要な問題 を
解くところまで この記事に書きました。
※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以上のパフォーマンスが必要とされる問題があり
コンテストで使用する言語を別の言語とした次第です。
1. 16進数について
「OpenCOBOL」「opensourceCOBOL」では
16進数 は 英数字(Alphanumeric) で、その値を表示しようとすると文字化けします。
先の記事では サンプルプログラム「COBDUMP」を用いて表示させていました。
PROGRAM-ID. HEXADECIMAL.
DATA DIVISION.
WORKING-STORAGE SECTION.
01 X PIC X(4) VALUE X"7FFFFFFE".
PROCEDURE DIVISION.
DISPLAY X.
STOP RUN.
【入力】
(なし、プログラムの定数 X"7FFFFFFE")
【出力結果】
◆◆◆
(文字化け)
ここで 2つの疑問 があります。
1. 16進数は X"(16進数文字列)" でしか与えることは「できない」のでしょうか。
2. 16進数を 目視 で確認することは「できない」のでしょうか。
いずれも No 。「できます」。
ただし手間はかかります。
16進数 は 見ることはできませんが 文字列 です。
「OpenCOBOL」「opensourceCOBOL」 では 文字列 を切り出す以下の 構文 があり
これを使うことが出来ます。
文字列が格納された変数 ( start : length )
ここで start は 開始位置 (最小1) です。
「OpenCOBOL」「opensourceCOBOL」は 文字列 も 配列 も 1-indexed です。
length は 切り出す文字数 です。終了位置 ではないので 注意 が必要です。
「2. 2進数、10進数、16進数 の 変換プログラム」にて、自作プログラム を書きました。
その 自作プログラム について解説します。
概要
何でも一旦 16進数 を経由しても良いですが、用途や繰り返す回数も考えると
何度も都度イチから書くわけではなく、何度も使い改良するものだから
用途別に少し細かくても良いと思いました。
図を描いてみました。
外部データ とは、実行単位中の複数のプログラムにおいて参照可能となる領域です。
今回はここで 定数 を設定します。
サブプログラム「HEX_TO_OTHER」の解説
16進数 → 2進数、10進数 を行います。
16進数 を 1byte ずつ切り出します。
この段階では文字化けで見れませんが、数字で割った商と余りを求めることができます。
このやり方で、16進数 → 10進数、16進数 → 2進数 を行うことができます。
サブプログラム「DCM_TO_HEX」の解説
10進数 → 16進数 を行います。
16進数 の 1byte ずつ処理を行うことは同じですが、今度は逆になります。
10進数 を 256 で割って余り(10進数 1byte)から 16進数 を得て
16進数 の 文字列にコピーすることで、10進数 → 16進数を行うことができます。
その他のサブプログラムについては、上記以外に特別な事は行っていません。
2. 2進数、10進数、16進数 の 変換プログラム
今後使うことも念頭に入れて、サブプログラム化しました。
PROGRAM-ID. BITWISE_OPERATION_4BYTE_32BIT.
DATA DIVISION.
WORKING-STORAGE SECTION.
01 NUM_OFF EXTERNAL PIC 9(1).
01 NUM_ON EXTERNAL PIC 9(1).
01 NUM_X EXTERNAL PIC 9(1).
01 h_num PIC X(4) VALUE X"00000000".
01 h_txt PIC X(8) VALUE SPACE.
01 b_txt PIC X(32) VALUE SPACE.
01 d_num PIC 9(10) VALUE ZERO.
01 x_th PIC 9(2) VALUE ZERO.
01 x_div PIC 9(1) VALUE ZERO.
01 n_bit PIC 9(1).
PROCEDURE DIVISION.
*> 外部データ
*> 実行単位中の複数のプログラムで使用する定数を設定
CALL "SET_EXTERNAL".
*> 2進数 対応表 0 〜 15
CALL "B_TABLE".
*> 演算対象 の 10進数 設定
MOVE 2506784507 TO d_num.
*> 10進数 を 16進数 に変換
CALL "DCM_TO_HEX" USING BY CONTENT d_num
BY REFERENCE h_num.
*> 16進数 を 2進数、10進数 に変換
CALL "HEX_TO_OTHER" USING BY CONTENT h_num
BY REFERENCE b_txt
BY REFERENCE d_num
BY REFERENCE h_txt.
DISPLAY "【演算前】"
DISPLAY "16進数 : " h_txt.
DISPLAY " 2進数 : " b_txt.
DISPLAY "10進数 : " d_num.
MOVE 16 TO x_th.
DISPLAY x_th "ビット目 を取り出す"
CALL "GET_NTH_BIT" USING BY CONTENT x_th
BY CONTENT d_num
BY REFERENCE n_bit.
DISPLAY x_th "ビット目 は " n_bit.
*> 16ビット目 に 1 を セットする
MOVE 16 TO x_th.
MOVE NUM_ON TO x_div.
DISPLAY x_th "ビット目 に " x_div " を セット"
CALL "SET_NTH" USING BY CONTENT x_th
BY CONTENT x_div
BY REFERENCE d_num
BY REFERENCE h_num.
*> 11ビット目 に 0 を セット
MOVE 11 TO x_th.
MOVE NUM_OFF TO x_div.
DISPLAY x_th "ビット目 に " x_div " を セット"
CALL "SET_NTH" USING BY CONTENT x_th
BY CONTENT x_div
BY REFERENCE d_num
BY REFERENCE h_num.
*> 30ビット目 を 反転
MOVE 30 TO x_th.
MOVE NUM_X TO x_div.
DISPLAY x_th "ビット目 を 反転"
CALL "SET_NTH" USING BY CONTENT x_th
BY CONTENT x_div
BY REFERENCE d_num
BY REFERENCE h_num.
*> 16進数 を 2進数、10進数 に変換
CALL "HEX_TO_OTHER" USING BY CONTENT h_num
BY REFERENCE b_txt
BY REFERENCE d_num
BY REFERENCE h_txt.
DISPLAY "【演算後】"
DISPLAY "16進数 : " h_txt.
DISPLAY " 2進数 : " b_txt.
DISPLAY "10進数 : " d_num.
STOP RUN.
END PROGRAM BITWISE_OPERATION_4BYTE_32BIT.
PROGRAM-ID. SET_EXTERNAL.
*> 外部データ
*> 実行単位中の複数のプログラムで使用する定数を設定
*> external data
*> Set constants used for multiple programs in running unit
DATA DIVISION.
WORKING-STORAGE SECTION.
01 BNY EXTERNAL PIC 9(1).
01 BIT4 EXTERNAL PIC 9(1).
01 BYT4 EXTERNAL PIC 9(1).
01 BYT32 EXTERNAL PIC 9(2).
01 BYT256 EXTERNAL PIC 9(3).
01 HXD EXTERNAL PIC 9(2).
01 NUM_OFF EXTERNAL PIC 9(1).
01 NUM_ON EXTERNAL PIC 9(1).
01 NUM_X EXTERNAL PIC 9(1).
01 OCT EXTERNAL PIC 9(1).
*> 16進数 対応表 0 〜 15
01 H_TBL1 EXTERNAL.
03 H_TBL11 OCCURS 16.
05 H_TBL PIC X(1).
PROCEDURE DIVISION.
MOVE 2 TO BNY.
MOVE 4 TO BIT4.
MOVE 4 TO BYT4.
MOVE 32 TO BYT32.
MOVE 256 TO BYT256.
MOVE 16 TO HXD.
MOVE 0 TO NUM_OFF.
MOVE 1 TO NUM_ON.
MOVE 9 TO NUM_X.
MOVE 8 TO OCT.
MOVE "0123456789ABCDEF" TO H_TBL1.
END PROGRAM SET_EXTERNAL.
PROGRAM-ID. B_TABLE.
*> 2進数 対応表 0 〜 15
*> 0001
*> 0010
*> 中略
*> 1111
DATA DIVISION.
WORKING-STORAGE SECTION.
*> 16
01 HXD EXTERNAL PIC 9(2).
*> 2
01 BNY EXTERNAL PIC 9(1).
*> 4
01 BYT4 EXTERNAL PIC 9(1).
*> 8
01 OCT EXTERNAL PIC 9(1).
01 p PIC 9(1).
01 i PIC 9(8).
01 j PIC 9(8).
01 q PIC 9(2).
01 r PIC 9(1).
01 s PIC X(1).
01 str PIC X(4).
01 len PIC 9(1).
01 idx PIC 9(2).
*> 2進数 対応表 0 〜 15
01 B_TBL1 EXTERNAL.
03 B_TBL11 OCCURS 16.
05 B_TBL PIC X(4).
PROCEDURE DIVISION.
*> 0 〜 15
PERFORM VARYING i FROM 0 BY 1 UNTIL HXD <= i
MOVE i TO q
MOVE ALL ZERO TO str
*> 繰り返し 2 で割る
PERFORM VARYING j FROM 0 BY 1 UNTIL q <= 0
DIVIDE BNY INTO q GIVING q REMAINDER r
COMPUTE p = FUNCTION STORED-CHAR-LENGTH(str)
SUBTRACT j FROM p
MOVE r TO s
STRING
s
INTO str WITH POINTER p
END-STRING
END-PERFORM
ADD 1 TO i GIVING idx
*> 2進数 対応表 設定
MOVE str TO B_TBL(idx)
END-PERFORM.
END PROGRAM B_TABLE.
PROGRAM-ID. DCM_TO_HEX.
*> 10進数 を 16進数 に変換
*> 4 byte (32 bit) 用
*> Convert decimal number to hexadecimal number
*> For 4 byte (32 bit)
DATA DIVISION.
WORKING-STORAGE SECTION.
*> 2
01 BNY EXTERNAL PIC 9(1).
*> 4
01 BYT4 EXTERNAL PIC 9(1).
*> 256
01 BYT256 EXTERNAL PIC 9(3).
*> 8
01 OCT EXTERNAL PIC 9(1).
01 d PIC 9(3) BINARY.
01 filler REDEFINES d.
03 filler PIC X.
03 dbyte PIC X.
01 i PIC 9(1).
01 idx PIC 9(1).
01 q PIC 9(10).
01 r PIC 9(3).
LINKAGE SECTION.
*> (IN) d_num
*> (OUT) h_num
01 d_num PIC 9(10).
01 h_num PIC X(4).
PROCEDURE DIVISION USING d_num h_num.
INITIALIZE h_num
MOVE d_num TO q
*> 1 byte ずつ処理
PERFORM VARYING i FROM 1 BY 1 UNTIL LENGTH of h_num < i
*> 4 - i
COMPUTE idx = BYT4 - i
*> 10進数 を 256 で割る
DIVIDE BYT256 INTO q GIVING q REMAINDER r
*> 余り(10進数 1 byte) を 代入することで
MOVE r TO d
*> 16進数 を得ることができる
MOVE dbyte TO h_num(idx + 1:1)
END-PERFORM.
END PROGRAM DCM_TO_HEX.
PROGRAM-ID. HEX_TO_OTHER.
*> 16進数 を 2進数、10進数 に変換
*> 4 byte (32 bit) 用
*> Convert hexadecimal number to binary number, decimal number
*> For 4 byte (32 bit)
DATA DIVISION.
WORKING-STORAGE SECTION.
*> 4
01 BIT4 EXTERNAL PIC 9(1).
*> 2
01 BNY EXTERNAL PIC 9(1).
*> 4
01 BYT4 EXTERNAL PIC 9(1).
*> 256
01 BYT256 EXTERNAL PIC 9(3).
*> 16
01 HXD EXTERNAL PIC 9(2).
*> 8
01 OCT EXTERNAL PIC 9(1).
01 d PIC 9(3) BINARY.
01 filler REDEFINES d.
03 filler PIC X.
03 dbyte PIC X.
01 i PIC 9(1).
01 j PIC 9(1).
01 k PIC 9(2).
01 m PIC 9(1).
01 q PIC 9(10).
01 r PIC 9(2).
*> 2進数 対応表 0 〜 15
01 B_TBL1 EXTERNAL.
03 B_TBL11 OCCURS 16.
05 B_TBL PIC X(4).
*> 16進数 対応表 0 〜 15
01 H_TBL1 EXTERNAL.
03 H_TBL11 OCCURS 16.
05 H_TBL PIC X(1).
LINKAGE SECTION.
*> (IN) h_num
*> (OUT) b_txt
*> d_num
*> h_txt
01 h_num PIC X(4).
01 b_txt PIC X(32).
01 d_num PIC 9(10).
01 h_txt PIC X(8).
PROCEDURE DIVISION USING h_num b_txt d_num h_txt.
INITIALIZE b_txt
INITIALIZE d_num
INITIALIZE h_txt
*> 1 byte ずつ処理
PERFORM VARYING i FROM 1 BY 1 UNTIL LENGTH OF h_num < i
*> 2 * i - 1
COMPUTE j = BNY * i - 1
*> 8 * i - 7
COMPUTE k = OCT * (i - 1) + 1
*> 7 - (2 * i - 1)
COMPUTE m = OCT - BNY * i
*> 16進数 1 byte を 代入することで
MOVE h_num(i:1) TO dbyte
*> 得られた 10進数 を 16 で割る
DIVIDE HXD INTO d GIVING q REMAINDER r
*> 前から格納していく
*> [F]
MOVE H_TBL(q + 1) TO h_txt(j:1)
*> [FF]
MOVE H_TBL(r + 1) TO h_txt(j + 1:1)
*> [1111]
MOVE B_TBL(q + 1) TO b_txt(k:BIT4)
*> [11111111]
MOVE B_TBL(r + 1) TO b_txt(k + BIT4:BIT4)
*> 16^0 の位 から 16^7 の位 までの 8桁
*> 10進数 上位桁 足し込み
COMPUTE d_num = d_num + HXD ** (m + 1) * q
*> 10進数 下位桁 足し込み
COMPUTE d_num = d_num + HXD ** m * r
END-PERFORM.
END PROGRAM HEX_TO_OTHER.
PROGRAM-ID. DCM_TO_BNY.
*> 10進数 を 2進数 に変換
*> 4 byte (32 bit) 用
*> Convert decimal number to binary number
*> For 4 byte (32 bit)
DATA DIVISION.
WORKING-STORAGE SECTION.
*> 4
01 BIT4 EXTERNAL PIC 9(1).
*> 2
01 BNY EXTERNAL PIC 9(1).
*> 4
01 BYT4 EXTERNAL PIC 9(1).
*> 32
01 BYT32 EXTERNAL PIC 9(2).
*> 256
01 BYT256 EXTERNAL PIC 9(3).
*> 16
01 HXD EXTERNAL PIC 9(2).
*> 8
01 OCT EXTERNAL PIC 9(1).
01 i PIC 9(2).
01 j PIC 9(1).
01 k PIC 9(2).
01 m PIC 9(1).
01 q PIC 9(10).
01 r PIC 9(2).
*> 2進数 対応表 0 〜 15
01 B_TBL1 EXTERNAL.
03 B_TBL11 OCCURS 16.
05 B_TBL PIC X(4).
*> 16進数 対応表 0 〜 15
01 H_TBL1 EXTERNAL.
03 H_TBL11 OCCURS 16.
05 H_TBL PIC X(1).
LINKAGE SECTION.
*> (IN) d_num
*> (OUT) b_txt
01 d_num PIC 9(10).
01 b_txt PIC X(32).
PROCEDURE DIVISION USING d_num b_txt.
MOVE ALL ZERO TO b_txt
MOVE d_num TO q
PERFORM VARYING i FROM 1 BY 1 UNTIL q <= 0
*> 32 - 4 * i + 1
COMPUTE k = BYT32 - BYT4 * i + 1
*> 10進数 を 16 で割る
DIVIDE HXD INTO q GIVING q REMAINDER r
*> 後ろから格納していく
*> [1111]
MOVE B_TBL(r + 1) TO b_txt(k:BIT4)
END-PERFORM.
END PROGRAM DCM_TO_BNY.
PROGRAM-ID. BNY_TO_DCM.
*> 2進数 を 10進数 に変換
*> 4 byte (32 bit) 用
*> Convert binary number to decimal number
*> For 4 byte (32 bit)
DATA DIVISION.
WORKING-STORAGE SECTION.
*> 4
01 BIT4 EXTERNAL PIC 9(1).
*> 2
01 BNY EXTERNAL PIC 9(1).
*> 4
01 BYT4 EXTERNAL PIC 9(1).
*> 32
01 BYT32 EXTERNAL PIC 9(2).
*> 256
01 BYT256 EXTERNAL PIC 9(3).
*> 16
01 HXD EXTERNAL PIC 9(2).
*> 8
01 OCT EXTERNAL PIC 9(1).
01 i PIC 9(2).
01 j PIC 9(2).
01 tmp PIC 9(1).
LINKAGE SECTION.
*> (IN) b_num
*> (OUT) d_num
01 b_txt PIC X(32).
01 d_num PIC 9(10).
PROCEDURE DIVISION USING b_txt d_num.
INITIALIZE d_num
MOVE ZERO TO i
*> 32 bit 処理
PERFORM BYT32 TIMES
*> 32 - i
COMPUTE j = BYT32 - i
MOVE b_txt(j:1) TO tmp
*> 2^0 の位 から 2^31 の位 までの 32 bit
*> 10進数 足し込み
COMPUTE d_num = d_num + BNY ** i * tmp
ADD 1 TO i
END-PERFORM.
END PROGRAM BNY_TO_DCM.
PROGRAM-ID. BNY_TO_HEX.
*> 2進数 を 16進数 に変換
*> 4 byte (32 bit) 用
*> Convert binary number to hexadecimal number
*> For 4 byte (32 bit)
DATA DIVISION.
WORKING-STORAGE SECTION.
*> 4
01 BIT4 EXTERNAL PIC 9(1).
*> 2
01 BNY EXTERNAL PIC 9(1).
*> 4
01 BYT4 EXTERNAL PIC 9(1).
*> 256
01 BYT256 EXTERNAL PIC 9(3).
*> 16
01 HXD EXTERNAL PIC 9(2).
*> 8
01 OCT EXTERNAL PIC 9(1).
01 d PIC 9(4) BINARY.
01 filler REDEFINES d.
03 filler PIC X.
03 dbyte PIC X.
01 i PIC 9(2).
01 j PIC 9(2).
01 k PIC 9(2).
01 tmp PIC 9(1).
LINKAGE SECTION.
*> (IN) b_txt
*> (OUT) h_num
01 b_txt PIC X(32).
01 h_num PIC X(4).
PROCEDURE DIVISION USING b_txt h_num.
INITIALIZE h_num
*> 1 byte ずつ処理
PERFORM VARYING i FROM 1 BY 1 UNTIL LENGTH OF h_num < i
MOVE ZERO TO d
*> 8 * (i - 1) + 1
COMPUTE k = OCT * (i - 1) + 1
*> 2進数 から 1 byte 取得 10進数 を 代入することで
PERFORM VARYING j FROM 1 BY 1 UNTIL OCT < j
MOVE b_txt(k + j - 1:1) TO tmp
COMPUTE d = d + BNY ** (OCT - j) * tmp
END-PERFORM
*> 16進数 を得ることができる
MOVE dbyte TO h_num(i:1)
END-PERFORM.
END PROGRAM BNY_TO_HEX.
PROGRAM-ID. GET_NTH_BIT.
*> Nビット目 を 取り出す
*> 4 byte (32 bit) 用
*> Get N-th bit
*> For 4 byte (32 bit)
DATA DIVISION.
WORKING-STORAGE SECTION.
*> 2
01 BNY EXTERNAL PIC 9(1).
*> 4
01 BYT4 EXTERNAL PIC 9(1).
*> 32
01 BYT32 EXTERNAL PIC 9(2).
*> 256
01 BYT256 EXTERNAL PIC 9(3).
*> 16
01 HXD EXTERNAL PIC 9(2).
*> 8
01 OCT EXTERNAL PIC 9(1).
01 b_tmp PIC X(32).
LINKAGE SECTION.
*> (IN) x_th
*> d_num
*> (OUT) n_bit
01 x_th PIC 9(2) VALUE ZERO.
01 d_num PIC 9(10).
01 n_bit PIC 9(1).
PROCEDURE DIVISION USING x_th d_num n_bit.
INITIALIZE n_bit
CALL "DCM_TO_BNY" USING BY CONTENT d_num
BY REFERENCE b_tmp
*> 右から x_th 番目を取り出す
MOVE b_tmp(BYT32 - x_th + 1:1) TO n_bit.
END PROGRAM GET_NTH_BIT.
PROGRAM-ID. SET_NTH.
*> Nビット目 操作
*> 4 byte (32 bit) 用
*> Set N-th bit operation
*> For 4 byte (32 bit)
DATA DIVISION.
WORKING-STORAGE SECTION.
*> 2
01 BNY EXTERNAL PIC 9(1).
*> 4
01 BYT4 EXTERNAL PIC 9(1).
*> 32
01 BYT32 EXTERNAL PIC 9(2).
*> 256
01 BYT256 EXTERNAL PIC 9(3).
*> 16
01 HXD EXTERNAL PIC 9(2).
*> 0
01 NUM_OFF EXTERNAL PIC 9(1).
*> 1
01 NUM_ON EXTERNAL PIC 9(1).
*> 9
01 NUM_X EXTERNAL PIC 9(1).
*> 8
01 OCT EXTERNAL PIC 9(1).
01 b_tmp PIC X(32).
01 h_tmp PIC X(4).
LINKAGE SECTION.
*> (IN) x_th
*> x_div
*> d_num
*> (OUT) d_num
*> h_num
01 x_th PIC 9(2).
01 x_div PIC 9(1).
01 d_num PIC 9(10).
01 h_num PIC X(4).
PROCEDURE DIVISION USING x_th x_div d_num h_num.
MOVE ALL ZERO TO b_tmp
IF x_div = NUM_OFF THEN
*> 1111 1111 1111 1111 1111 1111 1111 1111
MOVE ALL '1' TO b_tmp
END-IF
*> フラグ設定
MOVE x_div TO b_tmp(BYT32 - x_th + 1:1)
IF x_div = NUM_X THEN
*> 1
MOVE NUM_ON TO b_tmp(BYT32 - x_th + 1:1)
END-IF
CALL "BNY_TO_HEX" USING BY CONTENT b_tmp
BY REFERENCE h_tmp
*> Nビット目 操作
*> 0 をセットする
IF x_div = NUM_OFF THEN
CALL "CBL_AND" USING h_tmp, h_num, BY VALUE BYT4
ELSE
*> 1 をセットする
IF x_div = NUM_ON THEN
CALL "CBL_OR" USING h_tmp, h_num, BY VALUE BYT4
*> 反転する
ELSE
CALL "CBL_XOR" USING h_tmp, h_num, BY VALUE BYT4
END-IF
END-IF.
END PROGRAM SET_NTH.
【入力】
(なし、プログラムの 10進数 の 定数 2506784507)
【出力結果】
【演算前】
16進数 : 956A7EFB
2進数 : 10010101011010100111111011111011
10進数 : 2506784507
16ビット目 を取り出す
16ビット目 は 0
16ビット目 に 1 を セット
11ビット目 に 0 を セット
30ビット目 を 反転
【演算後】
16進数 : B56AFAFB
2進数 : 10110101011010101111101011111011
10進数 : 3043687163
ビット演算 の 組み込み関数 を使わなくてもできますが
ここでは 組み込み関数 を使って、次のようにビット演算しました。
本記事記載のプログラムは、競技プログラミングサイトAtCoder の
コードテストページにて「言語」COBOL-Free (OpenCOBOL)で実行可能です。
競技プログラミングサイトAtCoder での実行時の注意点については
先の記事を参照下さい。
https://qiita.com/ShinjiSHIBATA/items/1ef8cbf4b87969a46015
3. ABC 104 C All Green を解く
【問題概要】
難易度 1 以上 D 以下のそれぞれの 整数 i に対して 問題 が pi 問 存在します。
難易度 1 の 基本スコア は 1 × 100 点、難易度 D の 基本スコア は D × 100 点 です。
各難易度の pi 問 すべて解いたら、コンプリートボーナス ci 点 がもらえます。
基本スコア と コンプリートボーナス の 和 を 総合スコア とします。
総合スコア を G 点 以上 にする場合、少なくとも 何問 解く必要があるでしょうか。
制約 は 下記の通りです。
D 1 以上 10 以下。
pi 1 以上 100 以下。
ci 100 以上 10の6乗 以下。
すべての問題を解けば 必ず G 点 以上 にすることが可能。
【説明】
難易度 D を 2、総合スコア を 700 点 以上にする場合を考えます。
各難易度の問題の数 pi、コンプリートボーナス ci を 以下の図 とします。
コンプリートする 難易度 の 組合せ すべてにおいて 最小問題数 を求めます。
そのなかで 最も小さな 最小問題数 が 解答となります。
ある 難易度 で 1 問 以上 pi 問 未満 の 解き方 をする場合
ほかの 難易度 では pi 問 コンプリート か まったく解かないかのどちらかになります。
1 問 以上 pi 問 未満 の 解き方 をする 難易度 が
コンプリートしていない 最大 の 難易度 の場合に 最小問題数 になります。
すべての 難易度 で コンプリートしない 場合から
難易度 1 と 難易度 2 両方を コンプリートする 場合までの 組合せ は
10 進数 を 2 進数 にしたときの ビット から 求めます。
コンプリートする 難易度 を 決めたら 他の難易度では コンプリートしないようにします。
もし 他の難易度で コンプリートしなければ G 点 以上にならない場合
その 組合せ より得られた 最小問題数 は 無視するようにします。
Accepted なソースコードは下記になります。
https://beta.atcoder.jp/contests/abc104/submissions/2968494
4. ABC 041 D 徒競走 を解く
【問題概要】
N匹 の うさぎ が 徒競走 をします。(うさぎ は 最大 で 16 匹)
M人 の 目撃者 によると うさぎ xi は yi よりも先にゴールしました。
全ての情報に合致する着順が何通り考えられるでしょうか。
すべての観客の情報に合致するような着順が少なくともひとつ存在します。
【説明】
3匹 の うさぎ、2件 の 目撃 (x1, y1) = (1, 2)、(x2, y2) = (1, 3) とします。
うさぎ 1 が 1 ビット目、うさぎ 2 が 2 ビット目に対応するものとして
以下の要領で、rabbit 配列に ビット をもたせます。
着順の数 は 動的計画法 (この問題では bit DP) を用いて求めることができます。
dp 配列 の インデックス を 既にゴールしたうさぎに見立てます。
ただし「OpenCOBOL」「opensourceCOBOL」では 配列 が 1-indexed の為
変数 dp0 の値を、うさぎは 1匹 もゴールしていない状態とし
すべての観客の情報に合致するような着順が少なくともひとつ存在することから
dp0 = 1 とします。
目撃情報がなかった場合を考えてみます。
dp 配列を 以下の要領で更新します。
dp 配列 の インデックス と
rabbit [ 1 ] から rabbit [ 3 ] の ビット を 比較して
全ての ビット で一致しない場合、dp 値 を足し込みます。
dp [ dp 配列 の インデックス | シフト ] += dp [ dp 配列 の インデックス ]
ここで「|」は ビット演算 の OR 演算、「+=」は 足し込みの意味です。
rabbit 配列 の 各要素 について
「シフト」 は rabbit 配列 の インデックス の ビット に 1 をたてたものです。
1 の 場合 001、2 の 場合 010、3 の 場合 100 になります。
ある dp 配列の要素から、他の要素に配っているように見える為
「配るDP」と呼ばれています。
dp [ 7 ] の 値 が 解答となります。
目撃情報があった場合も rabbit 配列 の ビット が違うだけで やり方は同じ です。
Accepted なソースコードは下記になります。
https://beta.atcoder.jp/contests/abc041/submissions/2913960
実行時間が 2823 ms です。
問題の実行時間制限が 3 sec であり、ギリギリでした。
「OpenCOBOL」や「opensource COBOL」の
ビット演算 の 組み込み関数 CBL_AND ならびに CBL_OR がボトルネックになっています。
ビット演算 の AND 演算、OR 演算 の 自作 も トライ しましたが
組み込み関数 CBL_AND ならびに CBL_OR には 全く 及ばす、むしろ遅くなりました。
なんとかギリギリ Accepted することが出来たのは
CBL_AND と CBL_OR を使う時の サイズ (byte) を ちょうど 2 byte (16bit) とした為です。
これまでに紹介した 4 byte (32bit) で実行すると Time Limit Exceeded となります。
Time Limit Exceeded なソースコードは下記になります。
https://beta.atcoder.jp/contests/abc041/submissions/2911764
ビット演算 の 組み込み関数 を使う時には、サイズを意識することで
パフォーマンスを改善できる分かりました。
以上です。