アルゴ式のテスターに選ばれました（3日目）
更新しないって言ったじゃないか
進捗
今日も少し進めてQ2-5～Q2-7をやりました．まだ何とか自力ACです．
感想
Q2-7で少しつまりました．DPの部分ではなくて，loopの回し方がうまくいっていなかったり，二次元リストの初期化をミスしていたりしました． 勉強したい考え方以外の部分でミスしたりわかっていないかったりする部分があるのも，学習の妨げになるのだと感じました．
ちなみにQ2-7は解説にもあるように最初に入力で与えられるマス目に書かれている数字を逆順に保存すれば2-6と同じだなと思いましたが，それだと練習にならないなと思って，問題の意図通り実装しました．
別解はこんな感じですかね．
N = int(input()) A = [ list(reversed(list(map(int,input().split())))) for _ in range(N)] dp = [[100000] * N for _ in range(N)] dp[0][0] = A[0][0] for i in range(N): for j in range(N): if i-1 >= 0: dp[i][j] = min(dp[i-1][j]+A[i][j], dp[i][j]) if j-1 >=0: dp[i][j] = min(dp[i][j-1]+A[i][j], dp[i][j]) print(dp[N-1][N-1]) ''' #おわりに MacbookAirをポチってしまいました．M1の整備品でメモリ16GBのものが出ていたのでつい．．．ストレージが256なのが不安．．．
アルゴ式のテスターに選ばれました（3日目）
更新しないって言ったじゃないか
進捗
今日も少し進めてQ2-5～Q2-7をやりました．まだ何とか自力ACです．
感想
Q2-7で少しつまりました．DPの部分ではなくて，loopの回し方がうまくいっていなかったり，二次元リストの初期化をミスしていたりしました． 勉強したい考え方以外の部分でミスしたりわかっていないかったりする部分があるのも，学習の妨げになるのだと感じました．
ちなみにQ2-7は解説にもあるように最初に入力で与えられるマス目に書かれている数字を逆順に保存すれば2-6と同じだなと思いましたが，それだと練習にならないなと思って，問題の意図通り実装しました．
別解はこんな感じですかね．
N = int(input()) A = [ list(reversed(list(map(int,input().split())))) for _ in range(N)] dp = [[100000] * N for _ in range(N)] dp[0][0] = A[0][0] for i in range(N): for j in range(N): if i-1 >= 0: dp[i][j] = min(dp[i-1][j]+A[i][j], dp[i][j]) if j-1 >=0: dp[i][j] = min(dp[i][j-1]+A[i][j], dp[i][j]) print(dp[N-1][N-1])
おわりに
MacbookAirをポチってしまいました．M1の整備品でメモリ16GBのものが出ていたのでつい．．．ストレージが256なのが不安．．．
アルゴ式のテスターに選ばれました（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の記事も読んだりしましたが，なんで今までピンと来ていなかったのでしょうか．
おわりに
毎日こんなにたくさんの文章を書くのは無理なので続けられるペースでやります（継続できる範囲で）．明日はきっと更新しません．
アルゴ式のテスターに選ばれました（１日目）
アルゴ式のテスターに応募したらなんと選ばれちゃいました．
現状
アルゴ式の取組状況はこんな感じ．
ちなみにAtCoderの色は茶色（2021/10/11）highestは847（緑）
なお，大学院まで数学専攻ですがもう10年以上経っていますし，なんなら位相幾何学専攻でしたので競プロに役立つとされる整数分野は高校では未履修です（たぶん）．でも高校数学は割とできます．
今後
TwitterのDMによるやり取りで，興味ある分野をDPと申告したので，とりあえずDPのコンテンツに取り組んでみて，進捗報告をしていくことになりました． AtCoderのEDPCも途中で挫折してしまっています．
１日目
とりあえず動的計画法を進めます．
今日はQ1-1～Q1-6までやりました．
この６問で１時間くらいかかりました． ちゃんと図を書いたりしながらやりました． 途中のタイルの問題も解くことができましたが，DPの問題だとわかっていない場合に，DPで解けると気づけるかどうかは微妙だなと感じました．
今日の感想
とりあえず初日なので無理せずにあまり悩まずにできるところまでをやりました． コツコツ続けていきたいです．
【誰得】Google Forms からGoogle Documentを生成
はじめに
暇つぶしにGoogleAppsScriptでいろいろ調べて遊んでいます．そこで作ってみたスクリプトを公開したいと思います．
作ったもの
- Google Formsで作成したアンケート等をGoogle Document形式に変換します．
機能詳細
- GoogleFormsのタイトル，質問，選択肢，セクションを取得して，それらしいGoogleDocumentを生成する．
使いどころ
- GoogleFormsでアンケートを作成したが，社内が未だに書面による決済のため，作成したGoogleFormsを印刷したい．（Formsでも印刷できるが，編集ができない）
- GoogleFormsでアンケートを実施したいが，スマホ等を所持していない可能性も考慮して，紙面でのアンケートも準備したい．
- GoogleFormsで印刷したら選択肢のプルダウンが多すぎて見るに堪えないので，プルダウンの選択肢は削除して印刷したい（どれだけニッチな場面なのか）
注意点
作成したFormsに編集権限がないと使えません．
使い方
自分のGoogleDriveのフォルダ内でGoogle Apps Scriptを新規作成して，以下のスクリプトをコピペ（Google Apps Scriptの配布の仕方がわかりませんでした）．
スクリプト内の保存先フォルダーのIDを書き換える
生成したDocumentを保存したいフォルダをマイドライブ内のどこかに作成し，そこのフォルダに移動する．アドレスバーの以下の画像のようにアドレスの末尾がフォルダーＩＤなので，それをコピーして貼り付けてください．
- 読み込むフォームのIDを書き換える
読み込みたいフォームを開いて，フォルダーＩＤと同じような文字列がアドレスのところに表示されているので，それをコピーして貼り付け．
- 関数がmainになっていることを確認して実行
スクリプト
//保存先フォルダーの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）
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重ループに減らすというものです．
おおよそのところを説明すると，整数が与えられたときに
となる
の組み合わせを求めよという問に対し，最初の4重ループは
をそれぞれforでまわして解を得るものでした．
でも，最後のについては
が決まっているのだから，
が決まった段階で
をループさせる必要はなくなるので3重ループに落とせるという考え方です．
これを真似します．
今の問題では左から順に調べていき，R，Gが使わていれば最後に探す文字はBになります．そこでGを使用した場所よりも右にあるBの個数がわかればそれでの個数が確定します．
そのために，左から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 - 引越しできるかな？ 解説
はじめに
書くつもりはなかったが，公式解説がないようなのでメモ程度に書いてみることにした．
問題
解法
各荷物の3辺において必ず
１番長い辺 ２番目に長い辺 3番目に長い辺
が存在する（同じ長さがあれば，それらの順位付けは勝手に決めてよい）．
荷物について
： １番長い辺
：２番目に長い辺
：３番目に長い辺
として， [ 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)
