masuTomo’s blog

競技プログラミングの勉強メモです．主にPythonを使用します．数学の記事も書くかもしれません．

アルゴ式のテスターに選ばれました（2日目）

別に毎日更新しようと思っているわけではありませんが，たまたま気が向いたので今日も書きます．

進捗

今日は動的計画法のQ2-1～Q2-4までをやりました．２次元の動的計画法の前半部分です．昨日取り組んだ内容と比べるとやや時間がかかりましたが何とかＡＣできました．

感想

Q2-1，Q2-2は良いとして，Q2-3で少し悩みました．以前もやったことがあるような問題だし，DPっぽいなと思うのですがなかなか手が付きません．今回の問題を通して，配列dpの取り方（置き方？）がよく理解できていなかったということを自覚しました． Q2-3では，

dp[i]がi日目の報酬の最大値

のようにすればよいのかな？と漠然と考えていました．ただ，もしi日目に仕事0を行っていたとするとi+1日目には仕事0は行うことができません．でもi+1日目に仕事0を行った方が報酬の最大値が大きくなる可能性があるということくらいは僕でもわかります．今まではここまで考えて，うーん，うーんとうなって終わりだったような気がします．

今日はこのあともう少し考えてdp[i][j]は，i日目に仕事jをやったときの報酬の最大値とすれば良さそうであると気づくことができました．なぜ気づくことができたのかと言われれば２次元動的計画法の問題だよと教えてもらっていたからな気がします．

あと，Q2-4の解説を読んで，初めて「配るDP」と「貰うDP」の意味が分かりました．今までピンと来てませんでした．けんちょん本もよんだりQiitaの記事も読んだりしましたが，なんで今までピンと来ていなかったのでしょうか．

おわりに

毎日こんなにたくさんの文章を書くのは無理なので続けられるペースでやります（継続できる範囲で）．明日はきっと更新しません．

アルゴ式のテスターに選ばれました（１日目）

アルゴ式のテスターに応募したらなんと選ばれちゃいました．

note.com

現状

アルゴ式の取組状況はこんな感じ． f:id:masuTomo:20211011194709p:plain

ちなみにAtCoderの色は茶色（2021/10/11）highestは847（緑）

f:id:masuTomo:20211011195304p:plain

なお，大学院まで数学専攻ですがもう10年以上経っていますし，なんなら位相幾何学専攻でしたので競プロに役立つとされる整数分野は高校では未履修です（たぶん）．でも高校数学は割とできます．

今後

TwitterのDMによるやり取りで，興味ある分野をDPと申告したので，とりあえずDPのコンテンツに取り組んでみて，進捗報告をしていくことになりました． AtCoderのEDPCも途中で挫折してしまっています．

１日目

とりあえず動的計画法を進めます．

今日はQ1-1～Q1-6までやりました． f:id:masuTomo:20211011205756p:plain

この６問で１時間くらいかかりました． ちゃんと図を書いたりしながらやりました． 途中のタイルの問題も解くことができましたが，DPの問題だとわかっていない場合に，DPで解けると気づけるかどうかは微妙だなと感じました．

今日の感想

とりあえず初日なので無理せずにあまり悩まずにできるところまでをやりました． コツコツ続けていきたいです．

【誰得】Google Forms からGoogle Documentを生成

GAS Google Apps Script

はじめに

暇つぶしにGoogleAppsScriptでいろいろ調べて遊んでいます．そこで作ってみたスクリプトを公開したいと思います．

作ったもの

  • Google Formsで作成したアンケート等をGoogle Document形式に変換します．

    機能詳細

  • GoogleFormsのタイトル，質問，選択肢，セクションを取得して，それらしいGoogleDocumentを生成する．

使いどころ

  • GoogleFormsでアンケートを作成したが，社内が未だに書面による決済のため，作成したGoogleFormsを印刷したい．（Formsでも印刷できるが，編集ができない）
  • GoogleFormsでアンケートを実施したいが，スマホ等を所持していない可能性も考慮して，紙面でのアンケートも準備したい．
  • GoogleFormsで印刷したら選択肢のプルダウンが多すぎて見るに堪えないので，プルダウンの選択肢は削除して印刷したい（どれだけニッチな場面なのか）

注意点

作成したFormsに編集権限がないと使えません．

使い方

  • 自分のGoogleDriveのフォルダ内でGoogle Apps Scriptを新規作成して，以下のスクリプトをコピペ（Google Apps Scriptの配布の仕方がわかりませんでした）．

  • スクリプト内の保存先フォルダーのIDを書き換える

生成したDocumentを保存したいフォルダをマイドライブ内のどこかに作成し，そこのフォルダに移動する．アドレスバーの以下の画像のようにアドレスの末尾がフォルダーＩＤなので，それをコピーして貼り付けてください．f:id:masuTomo:20210226232144p:plain

  • 読み込むフォームのIDを書き換える

読み込みたいフォームを開いて，フォルダーＩＤと同じような文字列がアドレスのところに表示されているので，それをコピーして貼り付け．

  • 関数がmainになっていることを確認して実行 f:id:masuTomo:20210226230618p:plain

スクリプト

//保存先フォルダーのID
const saveFolderId = 'ここに保存先フォルダーのＩＤ';
//読み込むフォームのID
const formId = 'ここに読み込みたいフォームのＩＤ';

//各質問の先頭に付与するためのNumber
var qNo = 1;

//ファイルの保存
function saveDoc(doc,titleText){
  var file = DriveApp.getFileById(doc.getId());
  // 出力フォルダ
  var OutputFolder = DriveApp.getFolderById(saveFolderId);  
  file.moveTo(OutputFolder);
}

//Docの最上部に表示する文字列を設定
//見出し，センタリング
function setDocTitle(body, str){
  var par = body.appendParagraph(str);
  par.setHeading(DocumentApp.ParagraphHeading.HEADING1);
  par.setAlignment(DocumentApp.HorizontalAlignment.CENTER);
  return body;
}

//追加されたセクションの処理
function setSectionTitle(body,str){
    var par = body.appendParagraph(str);
  par.setHeading(DocumentApp.ParagraphHeading.HEADING2);
  par.setAlignment(DocumentApp.HorizontalAlignment.CENTER);
  return body;
}

function setContents(body, item){
  const indent = '    ';
  var type = item.getType();
  switch(type){

    //チェックボックスの処理
    case FormApp.ItemType.CHECKBOX:
      var res = String(qNo) + '.' + item.getTitle() +'\n\n';
      qNo++;
      console.log('CHCECKBOX開始-' + item.getTitle());
      var choices = item.asCheckboxItem().getChoices();
      for( var i = 0; i < choices.length; i++)  {
        res += indent + '□'+choices[i].getValue() + '\n';
      }
      res += '\n';
      body.appendParagraph(res);
      console.log('CHCECKBOX終了');
    break;

    //複数選択方式のグリッドの処理
    case FormApp.ItemType.CHECKBOX_GRID:
      console.log('CHCECKBOX_GRID開始-'+item.getTitle());
      var res = String(qNo) + '.' + item.getTitle() +'\n\n';
      qNo++;
      body.appendParagraph(res)
      var cols = item.asCheckboxGridItem().getColumns();
      var rows = item.asCheckboxGridItem().getRows();
      var cells = Array(rows.length+1);
      cols = [''].concat(cols);
      cells[0] = cols;
      for( var i = 1; i < rows.length+1; i++){
        cells[i] = Array(rows[i-1]).concat(Array(cols.length-1).fill('□'));
      }
      body.appendTable(cells);
      console.log('CHCECKBOX_GRID終了');
    break;

    //日付型の処理
    case FormApp.ItemType.DATE:
      var res = String(qNo) + '.' + item.getTitle() + '\n';
      qNo++;
      console.log('DATE開始-' + item.getTitle());
      console.log('DATE終了');
    break;

    case FormApp.ItemType.DATETIME:
      var res = String(qNo) + '.' + item.getTitle() + '\n';
      qNo++;
      console.log('DATETIME開始-' + item.getTitle());
      console.log('DATETIME終了');
    break;

    case FormApp.ItemType.DURATION:
      console.log('DURATION開始-' + item.getTitle());
      console.log('DURATION終了');
    break;

    //単一選択形式のグリッドの処理
    case FormApp.ItemType.GRID:
      console.log('GRID開始-'+item.getTitle());
      var res = String(qNo) + '.' + item.getTitle() +'\n\n';
      qNo++;
      body.appendParagraph(res)
      var cols = item.asGridItem().getColumns();
      var rows = item.asGridItem().getRows();
      var cells = Array(rows.length+1);
      cols = [''].concat(cols);
      cells[0] = cols;
      for( var i = 1; i < rows.length+1; i++){
        cells[i] = Array(rows[i-1]).concat(Array(cols.length-1).fill('〇'));
      }
      body.appendTable(cells);
      console.log('GRID終了');

    break;
    case FormApp.ItemType.IMAGE:
      console.log('IMAGE開始-' + item.getTitle());
      console.log('IMAGE終了');
    break;

    //プルダウンの処理
    case FormApp.ItemType.LIST:
      var res = String(qNo) + '.' + item.getTitle() + '\n\n';
      qNo++;
      console.log('LIST開始-' + res);
      var choices = item.asListItem().getChoices();
      for( var i = 0; i < choices.length; i++)  {
        res += indent + '・'+choices[i].getValue() + '\n';
      }
      res += '\n';
      body.appendParagraph(res);
      console.log('LIST終了');

    break;

    //ラジオボタンの処理
    case FormApp.ItemType.MULTIPLE_CHOICE:
      var res = String(qNo) + '.' + item.getTitle() + '\n\n';
      qNo++;
      console.log('MULTIPLE_CHOICE開始-' + res);
      var choices = item.asMultipleChoiceItem().getChoices();
      for( var i = 0; i < choices.length; i++)  {
        res += indent + '・'+choices[i].getValue() + '\n';
      }
      res += '\n';
      body.appendParagraph(res);
      console.log('MULTIPLE_CHOICE終了');
    break;

    //段落型の処理
    case FormApp.ItemType.PARAGRAPH_TEXT:
      var res = String(qNo) + '.' + item.getTitle() + '\n\n';
      qNo++;
      console.log('PARAGRAPH_TEXT開始-' + item.getTitle());
      res += '（自由記述）';
      res += '\n';
      body.appendParagraph(res);
      console.log('PARAGRAPH_TEXT終了');
    break;

    //均等目盛型の処理
    case FormApp.ItemType.SCALE:
      var res = String(qNo) + '.' + item.getTitle() + '\n\n';
      qNo++;
      console.log('SCALE開始-' + res);
      var llabel = item.asScaleItem().getLeftLabel();
      var rlabel = item.asScaleItem().getRightLabel();
      var lbound = item.asScaleItem().getLowerBound();
      var rbound = item.asScaleItem().getUpperBound();
      var line = '';
      for(var i = 0; i < rbound-lbound; i++){
        line += '----' + String(lbound + i + 1);
      }
      res += indent + llabel + ' | ' + String(lbound) + line + ' | ' + rlabel + '\n';
      body.appendParagraph(res);
      console.log('SCALE終了');
    break;

    case FormApp.ItemType.SECTION_HEADER:
      console.log('SECTION_HEADER開始-' + item.getTitle());
      console.log('SECTION_HEADER終了');
    break;

    //記述式の処理
    case FormApp.ItemType.TEXT:
      var res = String(qNo) + '.' + item.getTitle() + '\n\n';
      qNo++;
      console.log('TEXT開始-' + item.getTitle());
      res += '（自由記述）';
      res += '\n';
      body.appendParagraph(res);
      console.log('TEXT終了');
    break;

    //時刻の処理
    case FormApp.ItemType.TIME:
      console.log('TIME開始-' + item.getTitle());
      console.log('TIME終了');    
    break;

    case FormApp.ItemType.VIDEO:
      console.log('VIDEO開始-' + item.getTitle());
      console.log('VIDEO終了');
    break;

    //追加されたセクションの処理
    case FormApp.ItemType.PAGE_BREAK:
      body = setSectionTitle(body,item.getTitle() + '\n');
      console.log('PAGE_BREAK開始-' + item.getTitle());
      console.log('PAGE_BREAK終了');
    break;

  }
}

function main() {
  //読み込み先のFormsを指定
  var f = FormApp.openById(formId);
  //フォームの上部にある説明文
  var des = f.getDescription();
  var formTitle = f.getTitle();
  //フォームと同じタイトルでGoogle Docsを作成する
  var date = new Date();
  const doc = DocumentApp.create(formTitle + '_'+Utilities.formatDate(new Date(), 'JST', 'yyyyMMdd'));
  var body = doc.getBody();
  body = setDocTitle(body,formTitle + '\n');
  body.appendParagraph(des + '\n\n\n');

  //質問項目を取得
  var itemList = f.getItems();
  for(let i = 0; i < itemList.length; i++) {
    setContents(body,itemList[i]);    
  }
  saveDoc(doc,formTitle);
}

注意点

  • フォーム内の画像は取り込めません
  • 回答によるセクション移動には対応していません
  • テスト機能は反映しません
  • 必須回答は反映しません（これはそのうち対応するかも）
  • 入力チェックも反映しません
  • バグがあると思います．お気づきのことがあればお知らせいただけるとありがたいです．
  • その他，私が思い至らず考慮漏れしれいる事項があると思います．

参考

ここに全部書いてある． developers.google.com

ABC162 解説（D）

AtCoder python3 競技プログラミング

ABC162 D - RGB Triplets

(ABC162 D - RGB Triplets) https://atcoder.jp/contests/abc162/tasks/abc162_d

TLEした解法

とりあえず何も気にせずに3重ループを書いて提出した．

N = int(input())
S = input()

ans = 0
for i in range(N):
    for j in range(i,N):
        for k in range(j,N):
            if j -i == k-j : continue
            if S[i] != S[j] and S[j] != S[k] and S[k] != S[i]: ans += 1
print(ans)

結果：7TLE

制約はN<=4000なので，まぁそれはそうかと思っていましたが一応提出しました．

やり直し

3重ループをなんとかして2重ループにすれば通るだろうなと考えたので，その方法を考察します．

なんとなく頭の片隅にあったのは蟻本のp.8「あみだくじ」やp.25「ハードルがあがった『くじびき』」でした．これは最初4重ループで記載していたコードを3重ループに減らすというものです．

おおよそのところを説明すると，整数Kが与えられたときに a+b+c+d = Kとなるa,b,c,dの組み合わせを求めよという問に対し，最初の4重ループはa,b,c,dをそれぞれforでまわして解を得るものでした．

でも，最後のdについてはKが決まっているのだから，a,b,cが決まった段階でdをループさせる必要はなくなるので3重ループに落とせるという考え方です．

これを真似します． 今の問題では左から順に調べていき，R，Gが使わていれば最後に探す文字はBになります．そこでGを使用した場所よりも右にあるBの個数がわかればそれで(i,j,k)の個数が確定します．

そのために，左からi番目までにR，G，Bの出現した個数を累積和としてあらかじめ計算しておくことにしました． あとはR，Gについて，2重ループをして，最後のBについては累積和から個数を求めました． コードが冗長になりましたが，ACしたものはこちら（PyPyで提出）

N = int(input())
S = input()
#i番目までに何個のR，Ｇ，Ｂが出てくるか
countR = [0 for _ in range(N)]
countG = [0 for _ in range(N)]
countB = [0 for _ in range(N)]

for i in range(N):
    if S[i] == 'R':
        countR[i] = 1
    if S[i] == 'G':
        countG[i] = 1
    if S[i] == 'B':
        countB[i] = 1
for i in range(N-1):
    countR[i+1] += countR[i]
    countG[i+1] += countG[i]
    countB[i+1] += countB[i]

ans = 0
#フラグ
R = False
G = False
B = False
for i in range(N):
    if S[i] == 'R':
        R = True
    if S[i] == 'G':
        G = True
    if S[i] == 'B':
        B = True
    for j in range(i,N):
        if S[i] == S[j]: continue

        if S[j] == 'R':
            if G:
                ans += countB[N-1] - countB[j]
                if 2*j-i < N and S[2*j-i] == 'B':ans -=1
            if B:
                ans += countG[N-1] - countG[j]
                if 2*j-i < N and S[2*j-i] == 'G':ans -=1

        if S[j] == 'G':
            if R:
                ans += countB[N-1] - countB[j]
                if 2*j-i < N and S[2*j-i] == 'B':ans -=1
            if B:
                ans += countR[N-1] - countR[j]
                if 2*j-i < N and S[2*j-i] == 'R':ans -=1

        if S[j] == 'B':
            if R:
                ans += countG[N-1] - countG[j]
                if 2*j-i < N and S[2*j-i] == 'G':ans -=1    
            if G:
                ans += countR[N-1] - countR[j]
                if 2*j-i < N and S[2*j-i] == 'R':ans -=1
    R = False
    G = False
    B = False
print(ans)

ARC013 B - 引越しできるかな？ 解説

AtCoder python3 競技プログラミング

はじめに

書くつもりはなかったが，公式解説がないようなのでメモ程度に書いてみることにした．

問題

ARC013 B - 引越しできるかな？

解法

各荷物の3辺において必ず

１番長い辺 ２番目に長い辺 3番目に長い辺

が存在する（同じ長さがあれば，それらの順位付けは勝手に決めてよい）．

荷物 iについて

l_{i} ： １番長い辺

m_{i} ：２番目に長い辺

n_{i} ：３番目に長い辺

として， [ tex: l_ {i} , m_ {i} , n_ {i} ]の最大値をそれぞれ求めて，それらを3辺の長さとする箱が必要である． （数式表示がうまくいきません，ごめんなさい）

実装

C = int(input())
l_max = 0
m_max = 0
n_max = 0
for _ in range(C):
    size = list(map(int,input().split()))
    size.sort()
    l_max = max(size[0],l_max)
    m_max = max(size[1],m_max)
    n_max = max(size[2],n_max)

print(l_max*m_max*n_max)

ABC129 C - Typical Stairs 解説

AtCoder python3 競技プログラミング 高校数学

はじめに

Pythonで実装しました．そんなところで差が出るなんて，，，という学びがあったので記事にします．

問題

ABC123 C - Typical Stairs

考え方

いわゆるDPの基本的な問題なのだとおもいます．フィボナッチ数列と同じです．

1歩または2歩進めるとうことは，Ｎ段目に到達する方法はN-1段目から来る，またはN-2段目から来るの2通りです．したがってdp[N]をN段目に到達する方法とすれば，

dp[N] = dp[N-1] + dp[N-2]

と表すことができ，これはフィボナッチ数列の一般項と同じです．ここに壊れている床は使えないという条件を加えてやればACとなります．

TLEした実装

mod = 1e+9+7
 
# 入力の受け取り
N, M = map(int,input().split())
#壊れて使えない床をリストAに格納
A = [int(input()) for _ in range(M)]
 
dp = [0 for _ in range(N+1)]
dp[0] = 1
dp[1] = 1 if 1 not in A else 0
#DP遷移を計算
for i in range(2,N+1):
　#i段目が使えない床の場合はdp[i]=0とする
    if i in A:
        dp[i] = 0
    else:
        dp[i] = (dp[i-1] + dp[i-2])%mod
    
print(int(dp[N]))

ACした実装

mod = 1e+9+7

N, M = map(int,input().split())

#壊れた床の格納方法を変更
#床iが使えるときはA[i]=True
#床iが使えないときはA[i]=False
A = [ True for _ in range(N+1)]
for i in range(M):
    A[int(input())] = False

dp = [0 for _ in range(N+1)]
dp[0] = 1
dp[1] = 1 if A[1] == True else 0
for i in range(2,N+1):
    #dpを計算するときのifの条件式もAに合わせて変更
    if A[i]: dp[i] = (dp[i-1] + dp[i-2])%mod
   
print(int(dp[N]))

これでTLEが解消されてACとなりました．

大学入試

1歩で1段または2段のいずれかで階段を昇るとき，1歩で2段昇ることは連続しないものとする．15段の階段を昇る昇り方は何通りあるか．（07 京都大　文 ）

競プロが大学入試にも役立つ好例ですね！！中高生も胸をはって競プロにいそしみましょう！

ABC186 解説（A～C）

AtCoder python3 競技プログラミング 高校数学

A - Brick

A - Brick

N=12，w = 5のときは，2個の荷物を載せることができる（3個目を載せると15キログラムとなりオーバーする）． これを素直に式に表すと 12÷5 = 2\cdots 3となる（\cdotsは余りを表す）．

従って，この計算の商の部分が答えになる．pythonでは切り捨て処理は//で記述できる．

N, W = map(int,input().split())
print(N//W)

B - Blocks on Grid

B - Blocks on Grid

ブロックを取り除くことしかできないので，すべてのマスの中でブロック数が一番少ないマスのブロック数に他のマスのブロック数を合わせるしかない．

おおむね次のような処理とした．

  • 入力の1行ごとに，その行の最小値を保存するようにして，すべての入力が終わったあとで，それらの中から全体の最小値を取得
  • H\times W個の要素を走査し，その中で先の最小値との差を合計していく
H, W = map(int,input().split())
A = []
mins = []
for i in range(H):
  a = list(map(int,input().split()))
  A.append(a)
  mins.append(min(a))
ans = 0
m = min(mins)
for i in range(H):
  for j in range(W):
    ans += A[i][j] - m

print(ans)

C - Unlucky 7

少し難しかった．

  • 各桁に7が出てくるかどうかのチェックが必要であり，それは整数型のままではできないので，文字列に変換して文字列の7を含むかどうかを判定する．

  • 10進数については，ただ文字列に変換して上記の処理を行えばよい

  • 8進数については，10進数を8進数に変換する処理が必要になる．

8進数への変換

実は，pythonには関数が用意されている(https://docs.python.org/ja/3/library/functions.html#oct)． ただ，ここでは向学のため8進数への変換も実装することとする．

進数について

カンジをつかむ

そもそも10進数とはどのような数の表し方かを確認する．例えば2345（二千三百四十五）は 2345 = 2000 + 300 + 40 + 5 = 2 \times 10^{3} + 3 \times 10^{2} + 4 \times 10^{1} + 5 \times 10^{0} と書き直すことができる． この各位の数2,3,4,5以外の部分に注目して10^{x}という形になっている．この部分が10なので10進法と呼んでいる．

では，8進数で3456_8と表されているという数は（10進数では）どのような数になるかというと，それは 345_8 = 3\times 8^{3} + 4\times 8^{2} + 5\times 8^{1} + 6 \times 8^{0}となる．ちなみにこれを計算すると1880である（もちろんこれは10進数）．※3456_8の右下の小さい8は，8進数で表していることを明示するためにつけている）

8進数を10進数に変換する

これで，８進数，10進数のカンジはつかめたのではないかと思うので，次は10進数で表された数を8進数に変換することを考える． 先の2345 _{10}を8進数に変換することを考える．8進数での表記は8^{x}というかたまりを作れば良い．下の桁から順番に調べよう．一番下の桁はk\times 8^{0}となっており，kは1～7のいずれかである（もしk=8なら，繰り上がって，8^{1}の桁の方に出てくることになる）．

したがって一番下の桁は，元の数字を8で割った余りを取ればよい． 2345÷8 = 293\cdots 1となり，最下位桁は1とわかる．

次に下から2番目の桁を求める．今，最下位桁は「●●▲◆」の◆の部分を８で割った余りとして求めたので，次の桁は一番下の◆を切り落とした「●●▲」に対して8 で割った余りを求めればよい．この一番下の◆を切り落とす方法を考える．

実は簡単である．10進法で考えると，1234を123にするには，10で割って小数点以下を切り落とせばよい．ここで10で割ることで一番下の桁が落ちるのは10進数だからである．

したがって今は8進法で考えているので8で割って小数点以下を切り捨てれば目的のものが得られ，それを8で割った余りを求めればよい．

2345÷8=293.125なので293とし，さらに293÷8=36\cdots 5となり下から2番目の桁は5だとわかる．

あとはこれを繰り返せばよい．計算式のみ記す．

293÷8 = 36.625となり36÷8 = 4\cdots4

36÷8 = 4.5となり4÷8 = 0\cdots4

4÷8 = 0となり0÷8 = 0\cdots0となりここで終わり．

したがって，2345_{10} = 4451_8であることがわかった．これを実装すると次のようになる．

def to_oct(n):
  s = ''
  while(n):
    s = str(n%8) + s
    n //= 8
  return s

ans = 0
N = int(input())
for i in range(1,N+1):
  if '7' not in str(i)  and '7' not in to_oct(i):
    ans += 1
print(ans)