情報処理学会研究報告
IPSJ SIG Technical Report

遺伝的アルゴリズムを用いた自動プログラム修正手法を応用した
プログラミングコンテストの回答の自動生成に向けて
富田 裕也1 , a)

松本 淳之介1 , b) 柗本 真佑1 , c) 肥後 芳樹1 , d)
倉林 利行2 , f) 切貫 弘之2 , g) 丹野 治門2 , h)

楠本 真二1 , e)

概要：本稿では，遺伝的アルゴリズムを用いた自動プログラム修正手法を応用したプログラミングコンテ
ストの回答の自動生成に向けた取り組みについて報告する．本研究では，プログラミングコンテストの問
題文，テストケースおよび過去のプログラミングコンテストの回答を格納したデータベースを用いて，プログラミングコンテストの回答を生成する．まず，問題文から必要とする制御構文を推定する．次に，必要とする制御構文のみを含む回答の雛形を作成し，作成した雛形に対して過去に開催されたプログラミン
グコンテストの回答に含まれるプログラム文を再利用して回答を生成する．過去のプログラミングコンテ
ストの回答に含まれるプログラム文の再利用によって回答の生成が行えるかを検証するために，必要とする制御構文の推定に成功したと仮定した上で実験を行った．AtCoder というプログラムコンテストサイトで開催されたプログラミングコンテストの問題のうち条件分岐や繰り返し処理を使わずに解ける平易な問
題を実験の対象にした．実験の結果，全ての問題に対して与えられたテストケースに成功する回答の生成に成功した．

自動プログラム生成とは，プログラムを自動で生成する

Becker らが提案した AI Programmer[4] は，遺伝的ア
ルゴリズムを用いてプログラムを生成する手法である．AI
Programmer は，与えられた入出力仕様からポインタの操技術である．つまり，開発者はプログラムを書くのではな

作やメモリの内容の書き換えなどのプリミティブな操作をく，作成したいプログラムの仕様を与えると与えられた仕繰り返し行いその入出力仕様を満たすプログラムを生成様を満たすプログラムが生成される．

する．

1. はじめに自動プログラム生成の手法には，Microsoft 社が開発した入出力仕様ではなく自然言語からプログラムを生成する

DeepCoder[3] がある．DeepCoder は与えられた入出力仕様からその入出力仕様を満たす 34 種類ある命令の組み合
わせを深さ優先探索を行い探索する．DeepCoder は深層手法もある．それらの手法の 1 つに Gvero らが提案した学習を用いて制御構文，演算子や定数などの出現確率を予

本稿では，自動プログラム生成の実現に向けた第一歩と測したモデルを利用して，効率的に深さ優先探索を行う．

して，プログラミングコンテストの問題の回答を過去に開AnyCode[7] がある．AnyCode は関数の機能を自然言語で与えるとその機能を持つ関数の候補を出力する．

催されたプログラミングコンテストの問題に対する回答を
1

2
a)
b)
c)
d)
e)
f)
g)
h)

大阪大学大学院情報科学研究科
Graduate School of Information Science and Technology, Osaka University
日本電信電話株式会社
Nippon and Telephone Corporation
y-tomida@ist.osaka-u.ac.jp
j-matumt@ist.osaka-u.ac.jp
shinsuke@ist.osaka-u.ac.jp
higo@ist.osaka-u.ac.jp
kusumoto@ist.osaka-u.ac.jp
kurabayashi.toshiyuki@lab.ntt.co.jp
kirinuki.hiroyuki@lab.ntt.co.jp
tanno.haruto@lab.ntt.co.jp

c 1959 Information Processing Society of Japan⃝

再利用することで自動生成する取り組みについて紹介する．
生成を試みる前に，過去に開催されたプログラミングコン
テストの問題に対する回答中のプログラム文の再利用によって理論上回答を生成できるかを確認するために調査を行った．調査対象は，AtCoder というプログラミングコン
テストサイトで開催されているプログラミングコンテストの問題に対する回答である．調査の結果，80%の回答は過去の問題の回答に含まれるプログラム文の再利用によって生成できることがわかった．プログラミングコンテストの1

情報処理学会研究報告
IPSJ SIG Technical Report

問題にはさまざまな種類があるため，プログラム文の再利

修正対象プログラム
テストケースの集合用だけでは現実的な時間内での回答の生成は難しい．プロ
グラミングコンテストの問題を分類するために回答中に存

⽋陥限局

在する制御構文の構造に着目し，140 問の問題を対象に調査を行った．調査の結果，90%の回答が上位 5 つの構造でプログラム⽣成あった．この調査結果を踏まえ，過去に開催されたプログ
ラミングコンテストの問題に対する回答の再利用による回

テスト実⾏

NO

答の生成を試みた．本手法の入力は，プログラミングコン
テストの問題文・テストケース，過去の回答を集めたデー

テスト成功?

タベース（以降，回答データベースという）である．出力YESとして与えられたプログラミングコンテストの問題文に対修正済みのプログラムする回答が得られる．本手法の流れは，最初に入力として
図 1 GenProg の流れ与えられたプログラミングコンテストの問題文から回答に必要である制御構文を推定し，回答の雛形を作成する．次に，作成した雛形に対して回答データベースに保存されているプログラム文を再利用し与えられた全てのテストケー

プログラムの評価には適応度を用いる．適応度はプログラ

スに成功する回答を生成する．

ムの良さを表しており，適応度にはテストの通過率が用い現段階でプログラムを生成できるか検証するために，られる．GenProg は全てのテストケースに成功するプロ

AtCoder で開催された問題のうち分岐や繰り返しを用いずに解ける 4 つの問題を対象として実験を行った．実験の結グラムが得られるまでプログラムの生成および評価を繰り果，対象とした全ての問題に対して与えられたテストケー

選択 生成されたプログラムに対してテストを実行する．

スに成功する回答の生成に成功した．さらに，3 つの問題

それらから適応度が高いプログラムを一定数取り出す．

に対してオーバーフィットの無い回答が得られた．

取り出されたプログラムは変異や交叉の対象となる．

2. 準備

返す．プログラム生成処理で行われる操作を以下に示す．

変異 選択によって取り出されたプログラムの欠陥箇所に変更を加え，新しいプログラムを生成する．加える変更はプログラム文の挿入・削除・置換のいずれかであ

2.1 自動プログラム修正
ソフトウェア開発においてデバッグは多大な労力を必要る．挿入や置換で用いるプログラム文は入力プログラとする作業であり，開発工数の半数以上を占めるといわれ

ムに含まれるプログラム文からランダムに選ばれる．

ている [5]．そのため，デバッグの支援はソフトウェア開発

変異の際に，変更を加えた箇所と変更内容を記録する．

の効率化やソフトウェアの信頼性および安全性の向上に有交叉 親となる 2 つのプログラムに記録されている変更箇益である．デバッグの労力を削減するために，デバッグの所と変更内容をいくつか選び，新たなプログラムを生支援に関する研究が数多く行われている [6], [9], [12], [13]．

成する．生成されたプログラムは親に記録されている

デバッグの支援に関する研究の 1 つに自動プログラム修正

変更箇所と変更内容の一部を持っている．

がある．

テストケースに成功するプログラムを出力する手法である．

2.2 AtCoder
AtCoder*1 は，AtCoder 社が運営しているプログラミン
グコンテストサイトである．AtCoder では，定期的にい自動プログラム修正の手法の 1 つに GenProg[10] がある．

くつかのコンテストが開催されている．それらで最も難易

GenProg は遺伝的アルゴリズム [11] を用いた自動プログ

度が低いコンテストは AtCoder Beginner Contest（以降，

ラム修正手法である．遺伝的アルゴリズムとは，解の候補

ABC という）である．ABC はプログラミングコンテスト
初心者向けのコンテストであり，最も難易度が低い A 問
題から最も難易度が高い F 問題の 6 つの問題で構成され自動プログラム修正は，欠陥を含むプログラムおよびそのプログラムに対するテストケースを入力として，全てのを生物の個体に見立て，遺伝的操作を繰り返し行い解を探索するアルゴリズムである．

GenProg の流れを図 1 に示す．まず，GenProg は欠陥
限局 [2] を行う．欠陥限局とはプログラム中の欠陥の位置ている．各問題は問題を説明する問題文，入力の制約，入を推定する手法である．欠陥限局後に，欠陥を含むプログ構成されている．図 2(a)，(b) に A 問題の例および回答例

ラムに対して推定した欠陥箇所に変更を加え，プログラムを示す．

を複数生成する．次に，生成したプログラムの評価を行う．

c 1959 Information Processing Society of Japan⃝

力・出力の形式およびテストケースに当たる入出力例から*1*2

https://atcoder.jp
https://atcoder.jp/contests/abc130/tasks/abc130 a2

情報処理学会研究報告
IPSJ SIG Technical Report

問題⽂
𝑋，𝐴 は0以上9以下の整数である．
𝑋 が 𝐴 未満の時 0，𝐴 以上の時10を出⼒せよ．

public int solveA (int r) {制約
• ⼊⼒は全て整数• 0 ≤ 𝐴, 𝑋 ≤ 9}

⼊⼒

return単⽂

⼊⼒は以下の形式で標準⼊⼒から与えられる．

X

式

𝐴

(a) ﬂat テンプレート

出⼒
𝑋 が 𝐴 未満の時0，𝐴 以上の時10を標準出⼒に出⼒せよ．

public String solveA (int N, int M) {
if (
) {

⼊出⼒例
⼊⼒

出⼒

X = 3，A = 10
X = 7，A = 5
X = 6，A = 6

010

return} else {;return;10(a) 問題import java.util.Scanner;}public class Main {}if (X < A) {System.out.println(0);} else {System.out.println(10);}(b) 回答例
図 2 A 問題の例（Rounding）*2

2.3 テンプレート
テンプレートとは，回答に出現する制御構文のうち if
文，for 文，switch 文，while 文および do-while 文の構造である．テンプレートの分類は排他的である．2 つのテンプレートの例を図 3 に示す．図 3(a) は分岐や繰り返しがない ﬂat テンプレートである．図 3(b) は分岐が 1 つだけある if{}テンプレートである．水色の部分に単文，緑色の部分に式が入る．

3. 調査

}

単⽂

public static void main(String[] args) {// 標準⼊⼒から読み込む
Scanner scanner = new Scanner(System.in);
int X = scanner.nextInt();
int A = scanner.nextInt();};

式(b) if{}テンプレート
図 3 テンプレート

に対する回答のプログラム文の割合を調査した．調査対
象は，ABC1〜140 の A 問題に対する Java で記述された

35,275 個の回答である．変数の正規化をした回答としていない 2 種類の回答に対して本調査を行った．変数の正規化の流れを図 4 に示す．まず，Java のソースコード解析ツー
ルである Java Development Tools*3（以降，JDT という）を用いて回答からプログラム文を抽出する．次に，抽出したプログラム文に対して変数を出現順に正規化する．

3.1.3 調査結果
再利用率を箱ひげ図にプロットした結果を図 5 に示す．
図 5(a) は，対象にした全ての回答の再利用率をプロットした箱ひげ図である．図 5(b) は，対象にした各 A 問題に対して再利用率の最大値をプロットした箱ひげ図である．
いずれの図も橙色が変数の正規化をしていない回答，青色
が変数の正規化をした回答である．図 5(a) より調査対象の回答の半分に含まれるプログラム文の 80%は過去に出題

3.1 再利用率の調査
3.1.1 調査目的された A 問題の回答に含まれるプログラム文であった．また，図 5(b) より調査対象にした 140 問の A 問題の半分に

本調査の目的は，過去に ABC で出題された A 問題に対当たる 70 問の回答中のプログラム文は，変数を正規化すする回答中のプログラム文の再利用によって ABC の A 問

れば過去に開催された ABC の A 問題に対する回答中のプ

題の回答を生成できるかの確認である．

ログラム文と一致した．

3.1.2 調査方法
ABC の A 問題の回答に含まれる過去の ABC の A 問題
c 1959 Information Processing Society of Japan⃝*3

https://www.eclipse.org/jdt

3情報処理学会研究報告
IPSJ SIG Technical Reportpublic int solveA(int A, int B) {int width = (A – 1);
int height = (B – 1);}}• 回答を生成したいプログラミングコンテストの問題文

int width = (A – 1);
int height = (B – 1);
return width * height;

int width = (A – 1);
int height = (B – 1);
return width * height;

各プログラム⽂中の変数を出現順に正規化{}

明する．図 6 は手法の流れである．入力は以下の 3 つである．

return width * height;

プログラム⽂を抽出{ストの回答を GenProg を応用し生成する手法について説

int $_0 = ($_1 – 1);
int $_2 = ($_3 – 1);
return $_0 * $_2;

int $_0 = ($_1 – 1);
int $_0 = ($_1 – 1);
return $_0 * $_1;

図 4 変数の正規化の流れ
再利⽤率• テストケース• 回答データベース
出力として与えられたテストケースに成功する回答が得られる．
本手法は以下のステップで構成される．

Step 0 前準備
Step 1 テンプレートの推定
Step 2 拡張した GenProg への適用
Step 0 では，前準備として JDT を用いて過去に開催されたプログラミングコンテストの問題に対する Java で記述された回答からプログラム文を抽出し，回答データベースに保存する．この Step は一度だけ実行すればよい．

Step 1 では，プログラミングコンテストの問題文からテンプレートを推定し，回答の雛形を作成する．

再利⽤率

1

1

Step 2 では，Step 1 で作成した雛形と入出力例をテス

0.8

0.998

トケースとして拡張した GenProg に与え，プログラムの

0.6

0.986

生成を行う．GenProg は雛形ではなく回答データベース

0.4

0.984

0.2

0.982

0

0.980

から再利用するプログラム文を検索する．

4.2 回答データベース
回答データベースのスキーマを以下に示す．

変数の正規化あり

変数の正規化あり

変数の正規化無し

変数の正規化無し• コンテスト名(a) 各回答の再利用率(b) 各回答の再利用率• プログラム文

図 5 再利用率の調査結果• プログラム文の種類• プログラム文に含まれる変数の情報（型，ﬁnal 修飾子

3.2 テンプレートの調査
3.2.1 調査目的
本調査の目的は ABC の A 問題の分類である．
3.2.2 調査方法
3.1 節の調査で対象にした各 A 問題（計 140 問）に対して再利用率が最大であった回答を対象に調査を行った．本
調査時に以下の処理は著者が手動で削除あるいは変形した．
独自実装の入出力処理

問題を解くための処理とは関係ないため，全て削除した．
三項演算子

全て if 文に変形した．

3.2.3 調査結果
テンプレートの調査結果を表 1 に示す．A 問題の回答はの有無）
回答データベースのレコード数を削減するために，プロ
グラム文に含まれる変数を正規化し，回答データベースに保存する．変数の正規化は，3.1 節と同じ方法を用いて行
表 1 テンプレートの調査結果
テンプレート数
割合
割合の累積和

ﬂat

60

0.43

0.43

if{}

47

0.34

0.76

if{if{}}

8

0.06

0.82
0.88

for{}

8

0.06

if{}if{}

3

0.02

0.9

for{if{}}

3

0.02

0.92

if{}if{}if{}

3

0.02

0.94

if{}if{}if{}if{}

2

0.01

0.96

for{if{}if{}}if{}

1

0.01

0.96

while{}

1

0.01

0.97

4. 現在の取り組み

for{if{}}if{}

1

0.01

0.98

for{}if{}

1

0.01

0.99

4.1 概要if{if{if{}}}

1

0.01

0.99

if{}if{}if{if{}}

1

0.01

1.00

14 種類のテンプレートに分類でき，90%の回答は 5 種類のテンプレートのいずれかであった．さらに，43%の回答は繰り返しや分岐がない ﬂat テンプレートに分類できた．

本節では，現在取り組んでいるプログラミングコンテ

c 1959 Information Processing Society of Japan⃝4

情報処理学会研究報告
IPSJ SIG Technical Report
前準備
過去の回答群．．．

回答データベース

挿⼊前のプログラム

挿⼊するプログラム⽂...
10 public int solveA(int n, String m) {11
String k = n + m;
int i = n * n;
12
13
...

int $_0 = $_1 + $_2;

プログラム⽂中の変数を正規化し保存する

変数名

型

宣⾔済みか

$_0

int

T

$_1

int
int

F
F

$_2

挿⼊先

挿⼊後のプログラム

問題⽂
テンプレート

テストケース

問題⽂から
テンプレートを推定する

回答...
10 public int solveA(int n, String m) {11
String k = n + m;
int i = n * n;
12
int $_0 = i + n;13...

拡張したGenProgに適⽤する

図 8 変数の書き換え例

図 6 手法の流れで宣言されている変数は，挿入先よりも前の行で宣言され変換前ている変数と変数名が衝突しないように変数名を書き換え

System.out.println((A - 1) * (B - 1));

る．挿入するプログラム文内で宣言されていない変数は挿
入先よりも前の行で宣言されているかつ型が一致する変数のうちいずれか 1 つと同じ変数名に書き換える．条件を満

変換後int $_0 = ($_1 - 1) * ($_2 - 1);

たす変数が存在しない場合はプログラム文の挿入をしない．
変数の書き換えの例を図 8 に示す．13 行目（緑色の行）図 7 出力処理の変換の例

がプログラム文の挿入先である．挿入するプログラム文にう．回答データベースには全く同じプログラム文は存在し含まれる宣言されている変数は$ 0 である．13 行目以前でない．さらに，再利用しても回答の生成に影響しないと考宣言されているかつ int 型である変数は n および i であり，えられるプログラム文は回答データベースに保存しない．

そのままの変数名でも変数名は衝突しないため，$ 0 の変例えば，int j; のような初期化をしていない変数宣言文は，数名は書き換えない．挿入するプログラム文に含まれる宣その変数を利用した式から回答を得られるとは考えにく言されていない変数は$ 1, $ 2 である．これらの変数名をい．また，標準出力への出力処理は図 7 のように出力を行

n または i のいずれかに書き換える．

うメソッドへの引数を抽出し変数を正規化した上で変数宣言文に変換する．

5. 実験
5.1 実験対象

4.3 GenProg の拡張
GenProg の Java 実装である kGenProg[8] をプログラ

以下の条件を満たす ABC の A 問題 23 問から 2019 年 9月 9 日時点で最新の 4 問を実験対象とした．

ム文の挿入時に変数名の書き換えを行うように拡張した．

• 入力および出力が整数のみである．

挿入するプログラム文内で変数が宣言済みか否かによって• 分岐や繰り返しをせずに解ける，すなわち ﬂat テンプ

変数名の書き換え方法が異なる．挿入するプログラム文内
*4
*5
*6
*7

レートを用いれば解ける問題である．

•

https://atcoder.jp/contests/abc121/tasks/abc121 a
https://atcoder.jp/contests/abc125/tasks/abc125 a
https://atcoder.jp/contests/abc128/tasks/abc128 a
https://atcoder.jp/contests/abc134/tasks/abc134 a

3.1 節の調査結果において再利用割合の最大値が 1 である．

対象とした問題を表 2 に示す．
表 2 実験対象

名前

概要

回答

White Cells*4

H 行 W 列の白色のマス目から h 個の行と w 列の行を選(H − h) ∗ (W − w)

テストケース数

3(T /A) ∗ B

3(A ∗ 3 + P )/2

3

3∗r∗r

3

び，黒色に塗った時に残った白色のマスの数を求める．

Biscuit Generator*5

A 秒毎に B 枚のビスケットを作る機械が T + 0.5 秒後までに作るビスケットの数を求める．

Apple Pie*6

A 個のリンゴと P 個のリンゴの欠片でできるアップルパ
イの数を求める．1 個のリンゴからは 3 個の欠片ができ，2 個の欠片から 1 個のアップルパイができる．
Dodecagon*7

半径 r の円に内接している正十二角形の面積を求める．

c 1959 Information Processing Society of Japan⃝5

情報処理学会研究報告
IPSJ SIG Technical Report

5.2 実験方法
過去のプログラミングコンテストの回答に含まれるプロ
グラム文の再利用によって回答の生成が行えるかの検証が本実験の目的である．そのため，テンプレートの推定に成功したと仮定して実験を行った．つまり，著者が手動で作成した回答の雛形を拡張した kGenProg に入力として与えた．実験に用いた計算機の性能を表 3，kGenProg のパラ
メータを表 4 に示す．各パラメータに対して制限時間を 2
時間に設定し，Seed 値を変えて実験を 10 回行った．与えられた全てのテストケースに成功する回答が得られた場合
は，残り時間に関わらず kGenProg を停止させた．

ABC の各問題に対する入出力例の数は 2〜4 個であるため，与えれられたテストケースのみ成功する回答が得られる可能性がある．得られた回答が以下の条件を満たす場合
のみ，オーバーフィットがない回答と判断した．

• 無作為に作成した全てのテストケースに成功する．

// (H - h) * (W - w) が答え
public int solveA(int H, int W, int h, int w) {W = (W - w) * (H - h);w = w + ((H - W) * h);double $_0 = ((double) (H + w) / 2);
return W;}
回答に影響しないプログラム⽂

図 9 オーバーフィットがない回答の例（White Cells）// 3 * r * r が答え
public int solveA(int r) {int $_0 = r - r / 2 * 2;
int $$_6 = Math.max(r * r, r + r);$_0 = 24 + (24 - $_0);
int $$_7 = ($_0 + $_0 + 2 - 1) / 2;$_0 = $_0 * (-1);$_0 -= 999;$_0 = r + r;$$_6 = $$_6 + (2 * $$_6);
return $$_6;}• 著者が目視で正しい答えが得られると判断する．

回答に影響しないプログラム⽂
図 10 オーバーフィットがある回答の例（Dodecagon）

5.3 実験結果
実験の結果を表 5 に示す．表 5 より，対象とした全てのA 問題に対して与えられたテストケースに成功する回答が得られ，Biscuit Generator 以外に対してオーバーフィッ
トがない回答が得られたことがわかる．以降では実験で得られた回答の例を紹介する．
図 9 は White Cells に対するオーバーフィットがない回
答の例である．図中の灰色の部分は回答に影響しないプロ
グラム文である．この回答は (W − w) ∗ (H − h) を返している．White Cells は (H − h) ∗ (W − w) を返せば解ける問題であるから，図 9 の回答にはオーバーフィットがない．
図 10 は Dodecagon に対するオーバーフィットがある回
答の例である．図中の灰色の部分は回答に影響しないプロ

実⾏時間(s)
7,000
6,000
5,000
4,000
3,000
2,000
1,000
0

White Cells

CPU

表 3 実験に用いた計算機の性能
AMD Ryzen 9 3900X（3.8GHz，12 コア）

メモリ

64GB

Apple Pie
Dodecagon

図 11 オーバーフィットがない回答が得られるまでに要した時間

表 4 kGenProg のパラメータ
変異で生成する交叉で生成する
1 世代あたりに選択する（秒）プログラムの数プログラムの数

400プログラムの数

4

100

0

10

大きい数の 3 倍を返している．Dodecagon は 3 ∗ r ∗ r を返

400

0

40

せば解ける問題であるから，この回答にはオーバーフィッ

グラム文である．この回答は 10 と r + r と r ∗ r を比較し，

トがある．例えば，入力が r = 1 の時正しい出力は 3 であるが，図 10 の回答の出力は 6 となる．

表 5 実験結果
問題名

テストケースにオーバフィットがない

成功した回答の数

回答の数

図 11 はオーバーフィットがない回答が得られるまでに要した時間である．図の縦軸は実行時間（秒）である．横191軸は対象とした A 問題の名前であり，左から White Cells，Biscuit Generator

20Apple Pie，Dodecagon である．いずれの A 問題も実行時

Apple Pie

109間に大きなばらつきがあった．

Dodecagon

87White Cells

c 1959 Information Processing Society of Japan⃝6

情報処理学会研究報告
IPSJ SIG Technical Report// (A * 3 + P) / 2 が答え
public int solveA(int A, int P) {int $_0 = A + ((P + A) / 2);
A = P * P + P;
return $_0;}
回答に影響しないプログラム⽂// 3 * r * r が答え
public int solveA(int r) {r = (r * r);r += r + r;
int $_0 = 24 + 24 - r;
int $$_7 = Math.min($_0, ($_0 + r));int $$_8 = Math.min(r, r * $$_7);

図 12 Apple Pie の回答の例}
public static void main(String[] args) {// 標準⼊⼒から読み込む
Scanner sc = new Scanner(System.in);
int a = sc.nextInt();
int b = sc.nextInt();
int c = 0;
if ((a + b) % 2 != 0) {c = 1;}}

System.out.println(c + ((a + b) / 2));再利⽤したと考えられるプログラム⽂

図 13 再利用元と考えられる回答*9

6. 考察
本節では，各問題について回答の生成に成功あるいは失敗した理由について述べる．
回答の生成に成功した理由として，以下の 2 点が挙げられる．

• 似ていないが同じ値を返す式を用いれば解ける問題が存在した．

• 正しい答えを得られるようにプログラム文を組み合わせた．

return r;

回答に影響しないプログラム⽂

図 14 Dodecagon の回答の例

回答// (T / A) * B が答え
public int solveA(int A, int B, int T) {T = 10;
int $_0 = A % 1000;$_0 = $_0 % 10;// 10 と B * (A % 1000 % 10) を⽐較し// ⼩さい数を返す
int $$_9 = Math.min(T, B * $_0);
String $$_7 = String.valueOf(A + "¥n");
int $$_11 = (T + B) * T / 2;
return $$_9;}
回答に影響しないプログラム⽂

テストケース
⼊⼒

期待値 出⼒成否A = 3，B = 5，T = 7
A = 3，B = 2，T = 9
A = 20，B = 20，T = 19

10

10

○

6

6

○

0

0

○

図 15 Biscuit Generator の回答の例および各テストケースに対する出力

ゆえに，これらの回答は正しい値を出力するようにプログ

White Cells と Apple Pie に対して生成した回答には似ラム文を組み合わせた結果，偶然正しい回答と出力が得ていないが同じ値を返す式を用いれば解ける問題が存在しられる回答が生成できたと考えられる．Dodecagon の回た．例えば，Apple Pie に対して生成したオーバーフィッ

答の例を図 14 に示す．この回答は 3 つの r の和を返してトがない 9 個の回答のうち 8 個の回答には Round Up theいる．r には r ∗ r が代入されているため，図 14 の回答はMean*8 の回答に含まれるプログラム文が存在した．Apple
Pie の回答の例を図 12 に示す．この回答は A+((P +A)/2)を返している．この式を変形すると，(A ∗ 3 + P )/2 となり，図 12 の回答にオーバーフィットはない．Round Up
the Mean は，整数 a，b の平均値の小数点以下を切り上げた値を求める問題である．Apple Pie は A 個のリンゴと P

3 ∗ r ∗ r を返していることになり，オーバーフィットがな

個のリンゴの欠片からできるアップルパイの数を求める問

色の部分は回答に影響しないプログラム文である．この回

い回答と判断できる．
オーバーフィットがある回答が生成できた原因として，
テストケースに成功するようにプログラム文を組み合わせたことが考えられる．図 15 は Biscuit Generator の回答の例および各テストケースに対する出力である．図中の灰題であるから Apple Pie と Round Up the Mean は似て

答は 10 と A を 1,000 で割った余りを 10 で割った余りをいない問題といえる．図 13 は再利用元と考えられる回答

比較して小さい数を返している．Biscuit Generator は Tである．水色の部分が再利用したと考えられるプログラム

を A で割った商に B を掛けた値を返せば解ける問題であ文である．このプログラム文中の変数を書き換えた結果，るから，図 15 の回答にはオーバーフィットがある．例え図 12 の回答が得られたと考えられる．

ば，入力が A = 10，B = 1，T = 10 の時正しい出力は 1

Dodecagon の回答には Apple Pie に対する回答と異なり多くの回答に共通するプログラム文が存在しなかった．
*8*9

https://atcoder.jp/contests/abc082/tasks/abc082 a
https://atcoder.jp/contests/abc082/submissions/5875920

c 1959 Information Processing Society of Japan⃝であるが，図 10 の回答の出力は 0 となる．

7. 妥当性の脅威
異なる 10 個の Seed 値を用いて実験を行った．そのた7

情報処理学会研究報告
IPSJ SIG Technical Reportめ，本稿と異なる Seed 値を用いるあるいは Seed 値の数を増やすと実験の結果大きく変わる可能性がある．また，回答のオーバーフィットの有無を自動的に生成したテスト[3]

ケースに全て成功した回答に対して目視で確認したため，オーバーフィットがあるにも関わらずオーバーフィットが[4]

ない回答と判断されたり，オーバーフィットがないにも関わらずオーバーフィットがある回答と判断されている可能
性がある．

[5]

8. おわりに
本稿では，過去に開催されたプログラミングコンテスト[6]の問題に対する回答に含まれるプログラム文の再利用によってプログラミングコンテストの回答を生成する取り組[7]

みについて紹介した．また，分岐や繰り返しがなく解ける
プログラミングコンテストの問題に対し実験を行った．実験の結果，対象にした 4 つ問題に対してテストケースに成[8]功する回答が得られ，3 つの問題に対してオーバーフィッ
トがない回答が得られた．
今後の課題として以下の 3 点が挙げられる．

• kGenProg の拡張[9]• テンプレートの推定の実現• 適応度の計算方法の改良
現時点では回答を生成できない分岐や繰り返しがある問題に対しても回答の生成ができるように kGenProg を拡張[10]する予定である．また，プログラム文の挿入時に挿入対象を平坦化 [1] することも考えている．平坦化とは複数の演算子を含むプログラム文を演算子が高々 1 つだけ含まれるプ[11]

ログラム文に分解する手法である．平坦化により細かい粒度でプログラム文を再利用できると著者は考えている．例
えば，int a = b + c + 1; を挿入する時に int $ 0 = b + c;

[12]と int a = $ 0 + 1; に分解する．この分解によって，分解後のプログラム文の片方だけの再利用が可能になる．
現時点では，与えられた問題文からテンプレートの推定を行っておらず，今後実現する予定である．
現在，適応度はテストの成功率を用いている．適応度の計算方法を改良すればオーバーフィットがある回答が得ら[13]

Spectrum-based Fault Localization , J. Syst. Softw.,
Vol. 82, No. 11, pp. 1780–1792 (2009).
Balog, M., Gaunt, A. L., Brockschmidt, M., Nowozin,
S. and Tarlow, D.: DeepCoder: Learning to Write
Programs, Proceedings International Conference on
Learning Representations 2017 (2017).
Becker, K. and Gottschlich, J.:
AI Programmer:
Autonomously Creating Software Programs Using Genetic Algorithms, CoRR, Vol. abs/1709.05703 (2017).
Britton, T., Jeng, L., Carver, G., Cheak, P. andKatzenellenbogen, T.:
Reversible Debugging Software: Quantify the time and cost saved using reversible debuggers (2013).
Clarke, L. A.: A System to Generate Test Data andSymbolically Execute Programs , IEEE Transactions
on Software Engineering, Vol. SE-2, No. 3, pp. 215–
222 (1976).
Gvero, T. and Kuncak, V.: Synthesizing Java expressions from free-form queries, Acm Sigplan Notices,Vol. 50, No. 10, pp. 416–432 (2015).
Higo, Y., Matsumoto, S., Arima, R., Tanikado,A., Naitou, K., Matsumoto, J., Tomida, Y. andKusumoto, S.:
kGenProg: A High-performance,
High-extensibility and High-portability APR System, the 25th Asia-Paciﬁc Software Engineering Conference, pp. 697–698 (2018).
Jones, J. A. and Harrold, M. J.:
Empirical Evaluation of the Tarantula Automatic Fault-localization
Technique , Proceedings of the 20th ACM/IEEE International Conference on Automated Software Engineering, pp. 273–282 (2005).
Le Goues, C., Dewey-Vogt, M., Forrest, S. andWeimer, W.: A Systematic Study of Automated Program Repair: Fixing 55 out of 105 Bugs for $8 Each
, Proceedings of the 34th International Conference on
Software Engineering, pp. 3–13 (2012).
Man, K. F., Tang, K. S. and Kwong, S.: Genetic
algorithms: concepts and applications [in engineering
design] , IEEE Transactions on Industrial Electronics,
Vol. 43, No. 5, pp. 519–534 (1996).
Pacheco, C., Lahiri, S. K., Ernst, M. D. and Ball,
T.:
Feedback-Directed Random Test Generation ,Proceedings of the 29th International Conference on
Software Engineering, pp. 75–84 (2007).
Zuddas, D., Jin, W., Pastore, F., Mariani, L. andOrso, A.: MIMIC: Locating and understanding bugsby analyzing mimicked executions , Proceedings of the
29th ACM/IEEE International Conference on Automated Software Engineering, pp. 815–825 (2014).

れ難くなると考えている．例えば，入力として与えられた変数を全て使っていない回答は正しい回答とは考えにくい．
そのため，テストの通過率に加えて入力として与えられた変数の使用率も適応度の計算に用いればオーバーフィットがある回答が得られ難くなると考えられる．
参考文献
[1]

[2]

Higo , Y. and Kusumoto , S.: Flattening Code forMetrics Measurement and Analysis, 2017 IEEE International Conference on Software Maintenance andEvolution, pp. 494–498 (2017).
Abreu, R., Zoeteweij, P., Golsteijn, R. and vanGemund, A. J. C.:
A Practical Evaluation ofc 1959 Information Processing Society of Japan⃝

8