競技プログラミング Edit

競プロの勉強方法と便利サイトと自作学習表

AtCoderで競技プログラミングをはじめたばかりの頃ってどうやって勉強したら良いのか全然わからないかと思います。

競技プログラミングの勉強方法と役立つ便利サイトを紹介したいと思います。

勉強の質と量

勉強する際に一番気になるのが勉強の質と量どっちが重要なのかですがこれはどちらも必要です。

短期間で上位(橙・赤コーダー)になっている人もいるのは事実です。

そもそも前提知識や自頭の良さに差があることは当然だとは思いますが、そういう人達は当然のように努力しています。

2019年にpythonで橙コーダーになったことで有名なmaspyさんのAtCoder Problemsを見てみましょう。

鬼のように問題を解いています。

私の会社でもAtCoderをやっている人は何人かいますが「多くて1日2、3問程度」だったりします。

趣味や暇つぶしに競技プログラミングをするなら全然問題ないのですが水色コーダー以上になるためには全然足りません。

もちろん量だけこなせばいいというわけではありませんが必要最低限以上の量が必要で、それは(一般人からすれば)思った以上に多いというのも事実です。

量の確保

量の確保の目的は次の通りです。

量の確保の目的

  • コーディングを速くする
  • 類似問題をノータイムで解けるようにする

コーディング速度は問題によりますが、pythonで解くならABCのA~C問題を10分以内で問題によっては5分以内で解けるくらいを目標にするといいと思います。

最初はABCのA~Cを15分で解くことを目標にするぐらいがいいと思います。

実際にpythonで競技プログラミングしている人で水色以上の人はそれくらいのタイムで解いています。

ABCのA~Fを全完することを考えると単純計算1問15分ですが、問題が難しくなるほど時間がかかるので最低でもA~Cを10分ほどで解く実力がないと厳しいです。

 

具体的に勉強量を増やす方法ですが競技プログラミングを毎日する習慣をつけることが一番です。

私の場合は自作の学習表を作ってひたすら予定を消化する方法をとりました。

一か月ほどでA~C問題を15分くらいで解けるようになりました。

質の確保

質の確保の目的

  • 解けなかった問題を解けるようにする
  • 解けるか微妙な問題を本番で確実に解く

成績を良くする方法として(競技プログラミングに限らず)解けない問題を解けるようにすること、解けるか微妙な問題を本番で確実に解くのが効率が良いです。

特に「解けるか微妙な問題を本番で確実に解く」ことは重要です。

解けるか微妙な問題とは正答率が30~70%くらいの問題だと思ってください。

 

私はこちらも自作の学習表で客観的な数値として把握して正答率が低い問題ほど繰り返し解くようにしました。

便利サイトと自作学習表

学習を管理する上で重要なのは客観的な数値です。

自分の主観と客観的な数値は意外と違うことが多いので、客観的な数値として管理するのが重要です。(私も自分が得意だと思ってた問題の正答率が意外と低いことがあって驚くことがあります)

ここでは私が実際に学習をどうやって管理している方法を紹介します。

まずは私が使っている便利サイトを紹介します。

AtCoder Problems

一番使っているサイトで、正直これだけあれば学習管理は十分です。

紹介する自作学習表もAtCoder ProblemsのAPIで取得したデータを自分が必要な形式で表示しています。

こんな便利なサイトを無料で公開している管理者の方に本当に感謝ですね。

自作学習表

こちらはGoogleスプレッドシートとGASで作りました。

スプレッドシート&GASの理由

  • Googleアカウントだけで共有が簡単
  • 一定間隔で自動実行したかった
  • 無料
  • サーバーレス

無料で簡単に分かりやすく使いたかったので選択しました。

具体的にどうやっているのかGASのコードも含めて公開します。

GASのコードが分かる人は適宜変更してください。

step
1
シートの作成

次の名称のシートを作成してください。

シート名

  • Target(学習データを表示)
  • MyData(提出データを保存)
  • Contest_list(コンテスト一覧を保存)
  • Probrem_list(問題一覧を保存)

step
2
スクリプトエディタにコードをコピペ

次のコードをコピペして次の部分を自分のAtCoderIDに書き換えてください。

ここにAtCoderIDを入力(私の場合は「XXXHOLiC」)→自分のAtCoderIDに変更

コードの機能

  • Get_All(全データを最新値に更新)
  • Get_My_Data(提出データを最新値に更新)
  • Get_Contest_List(コンテストデータを最新値に更新)
  • Get_Problem_List(問題データを最新値に更新)
  • Sort_Ac_Rate(学習表を正解率順でソート)
  • Sort_Next_execution(学習表を次回解答予定日順でソート)
  • Sort_Problem(学習表を問題順でソート)

function onOpen() {
var sheet = SpreadsheetApp.getActiveSpreadsheet();
var entries = [
{
name : "Get_All",
functionName : "Get_All"
}
,
{
name : "Get_My_Data",
functionName : "Get_My_Data"
}
, {
name : "Get_Contest_List",
functionName : "Get_Contest_List"
}
, {
name : "Get_Problem_List",
functionName : "Get_Problem_List"
}
, {
name : "Sort_Problem",
functionName : "Sort_Problem"
}
, {
name : "Sort_Next_execution",
functionName : "Sort_Next_execution"
}
, {
name : "Sort_Ac_Rate",
functionName : "Sort_Ac_Rate"
}
, {
name : "Create_Contest_List",
functionName : "Create_Contest_List"
}
];
sheet.addMenu("AtCorder", entries);
};
function Get_All(){
Get_My_Data()
Get_Contest_List()
Get_Problem_List()
Sort_Next_execution()
}
function Sort_Ac_Rate(){
var book = SpreadsheetApp.getActiveSpreadsheet()
var sheet = book.getSheetByName("Target");
var filter_criteria = []
if(sheet.getFilter() != null){
for(i = 1; i <= sheet.getLastColumn(); i++){
if(sheet.getFilter().getColumnFilterCriteria(i) != null){
filter_criteria.push(sheet.getFilter().getColumnFilterCriteria(i))
sheet.getFilter().removeColumnFilterCriteria(i)
}
else{
filter_criteria.push(null)
}
}
}
sheet.getRange(2, 11, sheet.getLastRow()-1, 1).copyValuesToRange(sheet, 11, 11, 2, sheet.getLastRow())
sheet.getRange(2, 2).setValue('')
sheet.getRange(2, 3).setValue('')
sheet.getRange(2, 4).setValue('')
sheet.getRange(2, 5).setValue('')
sheet.getRange(2, 6).setValue('')
sheet.getRange(2, 7).setValue('')
sheet.getRange(2, 8).setValue('')
sheet.getRange(2, 9).setValue('')
sheet.getRange(2, 10).setValue('')
sheet.getRange(2, 12).setValue('')
sheet.getRange(2, 13).setValue('')
sheet.getRange(2, 14).setValue('')
sheet.getRange(2, 15).setValue('')
sheet.getRange(2, 1, sheet.getLastRow()-1, 14).sort({column: 11, ascending: true});
sheet.getRange(2, 11, sheet.getLastRow()-1, 1).clearContent()
sheet.getRange(2, 2).setValue('=ArrayFormula(if(isna(vlookup(A2:A,MyData!A:J,2,false)),"", vlookup(A2:A,MyData!A:J,2,false)))')
sheet.getRange(2, 3).setValue('=ARRAYFORMULA(countifs(MyData!L:L,">"&E2:E,MyData!K:K,A2:A&"AC"))')
sheet.getRange(2, 4).setValue('=ARRAYFORMULA(if(isna(vlookup(A2:A&"AC",MyData!K:L,2,false)),"1999/01/01 00:00:00",vlookup(A2:A&"AC",MyData!K:L,2,false)))')
sheet.getRange(2, 5).setValue('=ARRAYFORMULA(if(isna(vlookup(A2:A&"NG",MyData!K:L,2,false)),"1999/01/01 00:00:00",vlookup(A2:A&"NG",MyData!K:L,2,false)))')
sheet.getRange(2, 6).setValue('=ArrayFormula(countif(MyData!K:K,A2:A &"AC"))')
sheet.getRange(2, 7).setValue('=ArrayFormula(countif(MyData!K:K,A2:A &"NG"))')
sheet.getRange(2, 8).setValue('=ARRAYFORMULA(if(F2:F+G2:G =0,"", F2:F/(F2:F+G2:G)))')
sheet.getRange(2, 9).setValue('=ArrayFormula(countifs(MyData!K:K,A2:A &"AC",MyData!L:L,">" & NOW()-360))')
sheet.getRange(2, 10).setValue('=ArrayFormula(countifs(MyData!K:K,A2:A &"NG",MyData!L:L,">" & NOW()-360))')
sheet.getRange(2, 11).setValue('=ARRAYFORMULA(if(I2:I+J2:J =0,"", I2:I/(I2:I+J2:J)))')
sheet.getRange(2, 12).setValue('=ArrayFormula(IF(K2:K>=0.8,IF(C2:C>=3,D2:D+360,IF(C2:C =2,D2:D+45,IF(C2:C=1,D2:D+7,D2:D+1))),IF(C2:C=1,D2:D+3,IF(C2:C=2,D2:D+15,IF(C2:C>=3,D2:D+(30 * (C2:C-2)),D2:D+3)))))')
sheet.getRange(2, 13).setValue('=ArrayFormula(IF(L2:L<=NOW(),HYPERLINK( "https://atcoder.jp/contests/"& VLOOKUP(A2:A,Probrem_list!A:C,2,false) &"/tasks/"& A2:A, "〇" ),"×"))')
sheet.getRange(2, 14).setValue('=ARRAYFORMULA(IF(left(A2:A,3) = "abc","abc", IF(left(A2:A,3)="arc","arc", IF(left(A2:A,3)="agc","agc","xxx"))) & "_" & left(VLOOKUP(A2:A,Probrem_list!A:C,3,false),1))')
sheet.getRange(2, 15).setValue('=ARRAYFORMULA(VLOOKUP(A2:A,Probrem_list!A:C,3,false))')
/*filter条件は実行前のものを使用*/
for(i = 1; i <= sheet.getLastColumn(); i++){
if(filter_criteria[i-1] != null){
sheet.getFilter().setColumnFilterCriteria(i, filter_criteria[i-1])
}
}
}
function Sort_Next_execution(){
var book = SpreadsheetApp.getActiveSpreadsheet()
var sheet = book.getSheetByName("Target");
var filter_criteria = []
if(sheet.getFilter() != null){
for(i = 1; i <= sheet.getLastColumn(); i++){
if(sheet.getFilter().getColumnFilterCriteria(i) != null){
filter_criteria.push(sheet.getFilter().getColumnFilterCriteria(i))
sheet.getFilter().removeColumnFilterCriteria(i)
}
else{
filter_criteria.push(null)
}
}
}
sheet.getRange(2, 12, sheet.getLastRow()-1, 1).copyValuesToRange(sheet, 12, 12, 2, sheet.getLastRow())
sheet.getRange(2, 2).setValue('')
sheet.getRange(2, 3).setValue('')
sheet.getRange(2, 4).setValue('')
sheet.getRange(2, 5).setValue('')
sheet.getRange(2, 6).setValue('')
sheet.getRange(2, 7).setValue('')
sheet.getRange(2, 8).setValue('')
sheet.getRange(2, 9).setValue('')
sheet.getRange(2, 10).setValue('')
sheet.getRange(2, 11).setValue('')
sheet.getRange(2, 13).setValue('')
sheet.getRange(2, 14).setValue('')
sheet.getRange(2, 15).setValue('')
sheet.getRange(2, 1, sheet.getLastRow()-1, 14).sort({column: 12, ascending: true});
sheet.getRange(2, 12, sheet.getLastRow()-1, 1).clearContent()
sheet.getRange(2, 2).setValue('=ArrayFormula(if(isna(vlookup(A2:A,MyData!A:J,2,false)),"", vlookup(A2:A,MyData!A:J,2,false)))')
sheet.getRange(2, 3).setValue('=ARRAYFORMULA(countifs(MyData!L:L,">"&E2:E,MyData!K:K,A2:A&"AC"))')
sheet.getRange(2, 4).setValue('=ARRAYFORMULA(if(isna(vlookup(A2:A&"AC",MyData!K:L,2,false)),"1999/01/01 00:00:00",vlookup(A2:A&"AC",MyData!K:L,2,false)))')
sheet.getRange(2, 5).setValue('=ARRAYFORMULA(if(isna(vlookup(A2:A&"NG",MyData!K:L,2,false)),"1999/01/01 00:00:00",vlookup(A2:A&"NG",MyData!K:L,2,false)))')
sheet.getRange(2, 6).setValue('=ArrayFormula(countif(MyData!K:K,A2:A &"AC"))')
sheet.getRange(2, 7).setValue('=ArrayFormula(countif(MyData!K:K,A2:A &"NG"))')
sheet.getRange(2, 8).setValue('=ARRAYFORMULA(if(F2:F+G2:G =0,"", F2:F/(F2:F+G2:G)))')
sheet.getRange(2, 9).setValue('=ArrayFormula(countifs(MyData!K:K,A2:A &"AC",MyData!L:L,">" & NOW()-360))')
sheet.getRange(2, 10).setValue('=ArrayFormula(countifs(MyData!K:K,A2:A &"NG",MyData!L:L,">" & NOW()-360))')
sheet.getRange(2, 11).setValue('=ARRAYFORMULA(if(I2:I+J2:J =0,"", I2:I/(I2:I+J2:J)))')
sheet.getRange(2, 12).setValue('=ArrayFormula(IF(K2:K>=0.8,IF(C2:C>=3,D2:D+360,IF(C2:C =2,D2:D+45,IF(C2:C=1,D2:D+7,D2:D+1))),IF(C2:C=1,D2:D+3,IF(C2:C=2,D2:D+15,IF(C2:C>=3,D2:D+(30 * (C2:C-2)),D2:D+3)))))')
sheet.getRange(2, 13).setValue('=ArrayFormula(IF(L2:L<=NOW(),HYPERLINK( "https://atcoder.jp/contests/"& VLOOKUP(A2:A,Probrem_list!A:C,2,false) &"/tasks/"& A2:A, "〇" ),"×"))')
sheet.getRange(2, 14).setValue('=ARRAYFORMULA(IF(left(A2:A,3) = "abc","abc", IF(left(A2:A,3)="arc","arc", IF(left(A2:A,3)="agc","agc","xxx"))) & "_" & left(VLOOKUP(A2:A,Probrem_list!A:C,3,false),1))')
sheet.getRange(2, 15).setValue('=ARRAYFORMULA(VLOOKUP(A2:A,Probrem_list!A:C,3,false))')
/*filter条件は実行前のものを使用*/
for(i = 1; i <= sheet.getLastColumn(); i++){
if(filter_criteria[i-1] != null){
sheet.getFilter().setColumnFilterCriteria(i, filter_criteria[i-1])
}
}
}
function Sort_Problem(){
var book = SpreadsheetApp.getActiveSpreadsheet()
var sheet = book.getSheetByName("Target");
var filter_criteria = []
if(sheet.getFilter() != null){
for(i = 1; i <= sheet.getLastColumn(); i++){
if(sheet.getFilter().getColumnFilterCriteria(i) != null){
filter_criteria.push(sheet.getFilter().getColumnFilterCriteria(i))
sheet.getFilter().removeColumnFilterCriteria(i)
}
else{
filter_criteria.push(null)
}
}
}
sheet.getRange(2, 2).setValue('')
sheet.getRange(2, 3).setValue('')
sheet.getRange(2, 4).setValue('')
sheet.getRange(2, 5).setValue('')
sheet.getRange(2, 6).setValue('')
sheet.getRange(2, 7).setValue('')
sheet.getRange(2, 8).setValue('')
sheet.getRange(2, 9).setValue('')
sheet.getRange(2, 10).setValue('')
sheet.getRange(2, 11).setValue('')
sheet.getRange(2, 12).setValue('')
sheet.getRange(2, 13).setValue('')
sheet.getRange(2, 14).setValue('')
sheet.getRange(2, 15).setValue('')
sheet.getRange(2, 1, sheet.getLastRow()-1, 14).sort({column: 1, ascending: true});
sheet.getRange(2, 2).setValue('=ArrayFormula(if(isna(vlookup(A2:A,MyData!A:J,2,false)),"", vlookup(A2:A,MyData!A:J,2,false)))')
sheet.getRange(2, 3).setValue('=ARRAYFORMULA(countifs(MyData!L:L,">"&E2:E,MyData!K:K,A2:A&"AC"))')
sheet.getRange(2, 4).setValue('=ARRAYFORMULA(if(isna(vlookup(A2:A&"AC",MyData!K:L,2,false)),"1999/01/01 00:00:00",vlookup(A2:A&"AC",MyData!K:L,2,false)))')
sheet.getRange(2, 5).setValue('=ARRAYFORMULA(if(isna(vlookup(A2:A&"NG",MyData!K:L,2,false)),"1999/01/01 00:00:00",vlookup(A2:A&"NG",MyData!K:L,2,false)))')
sheet.getRange(2, 6).setValue('=ArrayFormula(countif(MyData!K:K,A2:A &"AC"))')
sheet.getRange(2, 7).setValue('=ArrayFormula(countif(MyData!K:K,A2:A &"NG"))')
sheet.getRange(2, 8).setValue('=ARRAYFORMULA(if(F2:F+G2:G =0,"", F2:F/(F2:F+G2:G)))')
sheet.getRange(2, 9).setValue('=ArrayFormula(countifs(MyData!K:K,A2:A &"AC",MyData!L:L,">" & NOW()-360))')
sheet.getRange(2, 10).setValue('=ArrayFormula(countifs(MyData!K:K,A2:A &"NG",MyData!L:L,">" & NOW()-360))')
sheet.getRange(2, 11).setValue('=ARRAYFORMULA(if(I2:I+J2:J =0,"", I2:I/(I2:I+J2:J)))')
sheet.getRange(2, 12).setValue('=ArrayFormula(IF(K2:K>=0.8,IF(C2:C>=3,D2:D+360,IF(C2:C =2,D2:D+45,IF(C2:C=1,D2:D+7,D2:D+1))),IF(C2:C=1,D2:D+3,IF(C2:C=2,D2:D+15,IF(C2:C>=3,D2:D+(30 * (C2:C-2)),D2:D+3)))))')
sheet.getRange(2, 13).setValue('=ArrayFormula(IF(L2:L<=NOW(),HYPERLINK( "https://atcoder.jp/contests/"& VLOOKUP(A2:A,Probrem_list!A:C,2,false) &"/tasks/"& A2:A, "〇" ),"×"))')
sheet.getRange(2, 14).setValue('=ARRAYFORMULA(IF(left(A2:A,3) = "abc","abc", IF(left(A2:A,3)="arc","arc", IF(left(A2:A,3)="agc","agc","xxx"))) & "_" & left(VLOOKUP(A2:A,Probrem_list!A:C,3,false),1))')
sheet.getRange(2, 15).setValue('=ARRAYFORMULA(VLOOKUP(A2:A,Probrem_list!A:C,3,false))')
/*filter条件は実行前のものを使用*/
for(i = 1; i <= sheet.getLastColumn(); i++){
if(filter_criteria[i-1] != null){
sheet.getFilter().setColumnFilterCriteria(i, filter_criteria[i-1])
}
}
}
function Get_My_Data () {
var book = SpreadsheetApp.getActiveSpreadsheet()
var sheet = book.getSheetByName("MyData");
var url = 'https://kenkoooo.com/atcoder/atcoder-api/results?user=ここにAtCoderIDを入力(私の場合は「XXXHOLiC」)';
var response = UrlFetchApp.fetch(url, {"headers" : {"Accept-Encoding" : "gzip"}});
var jsons = JSON.parse(response.getContentText())
var ls = []
var tls = []
tls.push('Problem_id')
tls.push('Result')
tls.push('User_id')
tls.push('Contest_id')
tls.push('Language')
tls.push('Date')
tls.push('Length')
tls.push('Id')
tls.push('Point')
tls.push('Execution_time')
tls.push('Key_01')
tls.push('Date')
ls.push(tls)
var i = 2
jsons.forEach(function(myData, j){
fls = []
fls.push(myData.problem_id)
fls.push(myData.result)
fls.push(myData.user_id)
fls.push(myData.contest_id)
fls.push(myData.language)
fls.push(new Date(myData.epoch_second * 1000))
fls.push(myData.length)
fls.push(myData.id)
fls.push(myData.point)
fls.push(myData.execution_time)
if(myData.result === "AC"){
fls.push(myData.problem_id + "AC")
}
else{
fls.push(myData.problem_id + "NG")
}
fls.push(new Date(myData.epoch_second * 1000))
ls.push(fls)
i++;
});
sheet.getRange(1, 1, i - 1, 12).setValues(ls)
sheet.getRange(1, 1, i - 1, 12).setBorder(true, true, true, true, true, true)
sheet.getRange(1, 1, i - 1, 12).sort({column: 6, ascending: false});
sheet.getRange(1, 1, 1, 10).setBackgroundRGB(200, 255, 200)
}
function Get_Contest_List () {
var book = SpreadsheetApp.getActiveSpreadsheet()
var sheet = book.getSheetByName("Contest_list");
var url = 'https://kenkoooo.com/atcoder/resources/contests.json';
var response = UrlFetchApp.fetch(url, {"headers" : {"Accept-Encoding" : "gzip"}});
var jsons = JSON.parse(response.getContentText())
var ls = []
var tls = []
tls.push('Title')
tls.push('Id')
tls.push('Start_Date')
tls.push('Limit_Time')
ls.push(tls)
var i = 2
jsons.forEach(function(myData, j){
fls = []
fls.push(myData.title)
fls.push(myData.id)
fls.push(new Date(myData.start_epoch_second * 1000))
fls.push(myData.duration_second)
ls.push(fls)
i++;
});
sheet.getRange(1, 1, i - 1, 4).setValues(ls)
sheet.getRange(1, 1, i - 1, 4).setBorder(true, true, true, true, true, true)
sheet.getRange(1, 1, 1, 4).setBackgroundRGB(200, 255, 200)
}
function Get_Problem_List () {
var book = SpreadsheetApp.getActiveSpreadsheet()
var sheet = book.getSheetByName("Probrem_list");
var url = 'https://kenkoooo.com/atcoder/resources/problems.json';
var response = UrlFetchApp.fetch(url, {"headers" : {"Accept-Encoding" : "gzip"}});
var jsons = JSON.parse(response.getContentText())
var ls = []
var tls = []
tls.push('Id')
tls.push('Contest_id')
tls.push('Title')
tls.push('Registed')
tls.push('Submitted')
ls.push(tls)
var i = 2
jsons.forEach(function(myData, j){
fls = []
fls.push(myData.id)
fls.push(myData.contest_id)
fls.push(myData.title)
fls.push('=ARRAYFORMULA(countif(Target!A:A,A2:A))')
fls.push('=ARRAYFORMULA(countif(MyData!A:A,A2:A))')
ls.push(fls)
i++;
});
sheet.getRange(1, 1, i - 1, 5).setValues(ls)
sheet.getRange(1, 1, i - 1, 5).setBorder(true, true, true, true, true, true)
sheet.getRange(1, 1, 1, 5).setBackgroundRGB(200, 255, 200)
}

step
3
必要に応じてトリガー設定

必要に応じて、タイマー設定を行ってください。

学習予定表の使い方

「Get_All」を週1(新しいコンテストが開催された時)

「Get_My_Data」を10分くらい毎(新しく提出した時)

「Sort_Ac_Rate」、「Sort_Next_execution」、「Sort_Problem」を並び替えしたいタイミングで使います。(私は基本「Sort_Next_execution」で並び替えて使っています。たまに「Sort_Ac_Rate」で成果率の高い問題を解いたりしています。)

「Target」シートの「Check」列の「〇」をクリックするとAtCoderの問題ページが開くようになっています。

また、計算式や学習予定の初期設定は次のようになっています。

次回学習予定日の初期設定

  • 1問連続正解&正解率80%以上→7日後
  • 1問連続正解&正解率80%未満→1日後
  • 2問連続正解&正解率80%以上→45日後
  • 2問連続正解&正解率80%未満→3日後
  • 3問連続正解&正解率80%以上→360日後
  • 3問連続以上正解&正解率80%未満→正解率によって

sheet.getRange(2, 12).setValue('=ArrayFormula(IF(K2:K>=0.8,IF(C2:C>=3,D2:D+360,IF(C2:C =2,D2:D+45,IF(C2:C=1,D2:D+7,D2:D+1))),IF(C2:C=1,D2:D+3,IF(C2:C=2,D2:D+15,IF(C2:C>=3,D2:D+(30 * (C2:C-2)),D2:D+3)))))')

かなり客観的に自分の正答率などが見えるので是非試してみてください。

プログラミング

-競技プログラミング, Edit