masuTomo’s blog

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

Googleスプレッドシートから取り込んでGoogleフォームを作成する

GAS Google Apps Script

最近G Suite for Educationの利用が広がっているようですね。 私の職場でも最近活用が始まってきました。

特にGoogle Formsを利用してアンケート等を行うことが多いです。ただ，Formsの使い方がよくわからない人や，アンケートの原案を作るときにExcelを利用する人が一定数います。

  1. Excelで原案を作る

  2. Excel原案をFormsが使える人（私）に渡して，アンケート作成をお願いする

  3. 私がExcelからアンケートを作る

という流れがありました。少ない項目のアンケートなら問題ないのですが，項目数が多かったり，少ないにしても頻度が多くなるとさすがにめんどウになってきたので，GoogleスプレッドシートからFomsに読み込んで自動でアンケートを作成するScriptを書きました。

※Excelをスプレッドシートに変換するのは簡単で，スプレッドシートの方がFormsと連携しやすいのでこの形にしました

function myFunction() {
  var form = FormApp.getActiveForm();
  
  //質問をすべて削除
  while(form.getItems().length > 0){
    form.deleteItem(0);  
  }
  //読み込み先のspreadシートを指定
  var ss = SpreadsheetApp.openById('ここに読み込み先のSpreadシートのidを入力');
  //spreadシートの指定したシートのすべてのセルを読み込み
  const values = ss.getSheetByName('読み込みたいシート名を入力').getDataRange().getValues();
  
  
  //質問の個数
  var itemCnt = 100
  //選択肢の最大個数
  var optCnt = 200
  
  for(let i = 1; i < itemCnt; i++){
    //質問が空白だったらフォームの生成を終了する
    if(i == values.length) break;
    var questionTitle = values[i][0];  
    
    //解答方法
    var kind = values[i][1];
    switch (kind){
      case '記述式':
          form.addTextItem().setTitle(questionTitle)
          break;
          
      case '段落':
          form.addParagraphTextItem().setTitle(questionTitle)
          break;
          
      case 'ラジオボタン':
        var arr = new Array();
        //選択肢の末尾が「その他（自由記述）」を追加するか
        var otherOptionFlg = false;
        for(let j = 2; j < optCnt; j++){
          if(values[i][j] == null || values[i][j] == ''){
            break;
          }
          //選択肢がその他の場合は、末尾にその他（自由記述）を追加する
          if(values[i][j] == 'その他'){
            otherOptionFlg = true;
          }else{
              arr.push(values[i][j]);
            }
        }
        form.addMultipleChoiceItem().setTitle(questionTitle).setChoiceValues(arr).showOtherOption(otherOptionFlg);
        break;
          
      case 'チェックボックス':
        var arr = new Array();
        //選択肢の末尾が「その他（自由記述）」を追加するか
        var otherOptionFlg = false;
        for(let j = 2; j < optCnt; j++){
          if(values[i][j] == null || values[i][j] == ''){
            break;
          }
        //選択肢がその他の場合は、末尾にその他（自由記述）を追加する
        if(values[i][j] == 'その他'){
            otherOptionFlg = true;
          }else{
              arr.push(values[i][j]);
            }
        }
        form.addCheckboxItem().setTitle(questionTitle).setChoiceValues(arr).showOtherOption(otherOptionFlg);
        break;   
     }
  }
}

スプレッドシートの構成は，先頭行はヘッダということで，2行目からデータを入力する形とした。

A列に質問の具体的な文言，B列に回答方法として「ラジオボタン」「チェックボックス」「記述式」「段落」のいずれかを入力。C列以降には，ラジオボタンやチェックボックスの場合の選択肢を1セルにつき1項目ずつ入力する。空白が来たら，その直前が最後の選択肢であるという処理にしている。

また，その他，と入力しておくと選択肢の最後に，記述可能な「その他」の選択肢を付け加えるようにした。

AtCoderで緑になりました。

AtCoder 競技プログラミング

昨日の日立製作所 社会システム事業部 プログラミングコンテスト2020で緑色になったので色変記事を書こうと思います。ラッキーで緑化した気もしますが，緑は緑です。胸をはります。

簡単な自己紹介

社会人です。大学での専攻は数学でしたが，競プロで役立ちそうな代数（整数論）ではなくトポロジーが専門でした。AtCoderを始めたときはifやforはわかるけどアルゴリズムについて勉強したことはなかったです。 社会人になって競プロはじめたぞ，学生みたいに毎日精進する時間もないぞ，という人の助けになればうれしいです。

AtCoder歴

初参加は2018年9月ですが，そこからまったくやっておらず本格的な参入は2019年8月です。
そこからおよそ半年で緑色になりました（もう少し早くなれると思っていましたが，甘くなかったです）。

緑になるまでに心がけていたこと（順不同）

  1. ABCにとにかく参加する（レートが下がるのを気にしない）

  2. ABCでできなかった問題のうち1問だけ復習する（無理しない）

  3. 毎日精進できなくても気にしない（無理しない）

  4. AtCoderProblemsを活用してrecommendationsのmoderateを解く（簡単なやつから）

  5. Twitterで競プロerの方々をフォローする（競プロのキーワードを自分の中に取り込む）

  6. ABC参加前の1時間くらいは過去問と解く時間に充てる（コンテスト勘を取り戻す）

もう少し具体的に

上記の４でも触れましたが，AtCoderProblemsというサイトを活用してABCの過去問を解くということを繰り返しました。 緑化した時点でのＡＣはこれくらいです。 f:id:masuTomo:20200309192519p:plain 精進するときもABCの１セットをAから順に解いていき，わからなかった問題はがんばって考えるという感じでした。
Ｄだけやるとかは疲れちゃうので必ずＡやＢもやって箸休めしていました。
こんな感じなのでD問題はあまりやっていません。
私のレートが上がるパターンは基本的にＣまではほぼ考察無しで解く（茶色の中では早いほう）＋Ｄ問題が簡単なときにたまに解けるというときでした。正直今でも，茶色の中の高難度の問題はできないものを多いと思います。

あんまりやらなかったこと

  • 螺旋本

  • 蟻本

買いましたがあまりやりませんでした。パラパラ見たり，ABCで出てきたアルゴリズムを調べるのには使いました。これからは勉強した方がいいだろうなぁと思っています。

キーエンスプログラミングコンテスト2020 B - Robot Arms

AtCoder python3 蟻本 区間スケジューリング 貪欲法

昨日のキーエンスプログラミングコンテストでは撃沈した。Ｂ問題が解けなかった。 解説を見ると，どうも区間スケジューリングと呼ばれる典型問題らしい。また，Twitterによると蟻本にも書いてあるとのこと。
蟻本は多少読んだけど，まだ自分が読んでいない部分だったのかなと思って調べたら，がっつり以前読んでいた部分であった（かなしい）。
ということで少し復習してみた。

区間スケジューリング問題とは（蟻本）

  • ｎ個の仕事がある

  • 各仕事の開始時刻と，終了時刻が与えられる

  • 各仕事について，参加するかどうか選択する

  • 参加する場合は，開始時刻から終了時刻までその仕事しかできない

  • 同一時刻に複数の仕事することはできない（ある仕事の終了時刻と，別の仕事の開始時刻が重なってもいけない）

このとき，最大で何個の仕事に参加可能か。 　　　　

解法　選べる仕事の中で，終了時刻が一番早いものを選び続ければよい（貪欲法）　　　　

それっぽい説明

f:id:masuTomo:20200119143155p:plain

上の図のような状態だとする（線分1本1本が仕事を表す）。また，これより左側（早い時刻）では最適な仕事が選ばれているとする。このときに選ぶべき仕事を考える。

この図よりも右側において，より多くの仕事を選ぶことができる仕事が最適である。それは一番上の線分で表される仕事である。なぜなら右側の区間を一番長く残せるからである。

この図の左側では最適に選んでいるので，残りの時間（右側）をいかに長くできるかを考えれば良いという点がポイントだと思っている。

今回の問題

B - Robot Arms

注意点 ロボットのアームは X _i - L _iより大きく X _i + L _i未満である。と書いてあるので区間の端は重なっても良いということになる。また，ロボットのアームが一番左に行くのは X = 0, L = 10 ^9のときに -10 ^9となる場合である。
このことを考慮して，蟻本を参考に実装したコードが以下である。

N = int(input())
XL = []
for _ in range(N):
    x,l = map(int,input().split())
    #腕の右端が左にあるものから調べる
    XL.append([x+l,x-l])
XL.sort()

ans, t = 0, -1e9
for i in range(N):
    if t <= XL[i][1]:
        ans += 1
        t = XL[i][0]
print(ans)

蟻本をPythonで（LakeCounting）

本記事はnoteで書いていた記事の転載です。（noteからはてなブログに移行したため）　　　

AtCoderのコンテストに参加したり，蟻本を読んだりし始めました。

使用言語はPythonの予定。そこで，コンテストの参加記録や蟻本で勉強したことを書いていければいいなと思っています。

今回は第二章の全探索（深さ優先探索）。POJ2386のLakeCountingです。

C++とPythonで違うところはほとんどないので，そのまま真似して書けばＯＫ．

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

field = [""]*M
for i in range(N):
   field[i] = list(input())

def dfs(x, y):
   field[x][y] = "."

   for dx in range(-1,2):
       for dy in range(-1,2):
           nx = x+dx
           ny = y+dy
           if  0 <= nx and nx < N  and 0 <= ny and ny < M and field[nx][ny] == "W":
               dfs(nx,ny)

res = 0
for i in range(N):
   for j in range(M):
       if field[i][j] == "W":
           dfs(i,j)
           res += 1
print(res)

個人的に蟻本のコードで気になっていた部分は，DFSの処理の中の，ifの条件式でした。

別に水たまりかどうかの判定に庭の端かどうかは関係なくね？と思っていました。ので，if文の部分を以下のように変更してみました。

これを

if  0 <= nx and nx < N  and 0 <= ny and ny < M and field[nx][ny] == "W":

これに

if  field[nx][ny] == "W":

すると，こうなりました。

    if  field[nx][ny] == "W":
IndexError: string index out of range

ということで，水たまりかどうかの判定ではなく，field[ ][ ]というlistにアクセスする際に，indexの外側の値でアクセスしないようにするために必要だったということでした。4方向にfor文を回しているので確かにその判定が必要ですね。

でも，ということはifの中身の条件式の順番を入れ替えて

if  field[nx][ny] == "W" and 0 <= nx and nx < N  and 0 <= ny and ny < M:

としても

  if  field[nx][ny] == "W" and 0 <= nx and nx < N  and 0 <= ny and ny < M:
IndexError: string index out of range

同じエラーがでますね。ifでは条件式がFalseになった時点で後続の条件文を判定しないので，このようになるのかなと思います。

Pythonとturtleでシェルピンスキーのガスケット

python3 図形

シェルピンスキーのギャスケットの画像が必要になった。せっかくなので勉強中のPythonで書いてみることにしたました。
そもそもPythonで図形描画をしたことがなかったので「Python 図形描画」でググるところからスタート。少し調べると２つ候補が見つかりました。

  • turtle

  • matplotlib

matplotlibは以前，統計処理の勉強で少しだけ使ったことがあるが，グラフを書くことや点をプロットすることは得意そうという印象。ただ，今回は直線を引いたりするのを気軽にやりたくて，そういうのはturtleの方が得意そうに見えたので，今回はturtleを使ってみることにしました。
以下のwebサイトを参考にさせてもらいました。

亀に訊け：Pythonの亀グラフィックス

Pythonとタートルグラフィックスによる（再帰）プログラミング教育処方案 - Read -> Blog

turtle --- タートルグラフィックス — Python 3.8.1 ドキュメント

使用する機能は基本的には２つ。

  • 指定した角度だけ回転する
  • 今向いている方向に，指定した長さの線分を引く

あとはこれをうまいこと組み合わせればよい。 解説はまた今度（眠いので）。今日はコードと描画結果だけ掲載します。

from turtle import *
from collections import deque
len = 600
stX = -250
stY = -250

#スタート地点に戻る
def setHome():
    setheading(0)
    penup()
    setposition(stX,stY)
    pendown()
#指定した場所に移動して方向を水平に変更
def setXY(x,y):
    setheading(0)
    penup()
    setposition(x,y)
    pendown()

#最初に一度だけ描く大きい三角形
def drawBigTri(l):
    setHome()
    fillcolor('blue')
    begin_fill()
    for _ in range(3):
        fd(l)
        rt(240)
    end_fill()

#再帰で小さい三角形を描画
def drawTri(l):
    l /= 2
    qq = []
    for q in Q:
        qq.append(q)
    for q in qq:
        setXY(q[0],q[1])
        fd(l)
        rt(300)
        Q.append(list(position()))
        fillcolor('white')
        begin_fill()
        for i in range(3):
            if i == 2: Q.append(list(position()))
            fd(l)
            rt(240)
        end_fill()
    drawTri(l)

speed(0)
drawBigTri(len)
Q = deque()
Q.append([stX,stY])
drawTri(len)
done()

描画結果はこちら f:id:masuTomo:20200117003325p:plain

yukicoder No.118 門松列(2)

python3 yukicoder 競技プログラミング

★★に早く慣れたい。

問題

No.118 門松列(2) - yukicoder

長さが違う3本の竹を選べば適当に並べ替えることで門松列にすることができるので，異なる長さの竹を3本選ぶ選び方の総数（同じ長さの竹も区別する）を求めればよい。
同じ長さの竹が何本あるかがわかればあとは計算できる。
例えば1,2,3という長さの3本の竹を選んだとして，それぞれの竹が a,b,c本ずつあるとする。このときの門松列の数はa\times b \times cである。
あとは，長さが異なる3本の竹を選ぶ方法はitertoolsのcombinationsを利用すれば簡単である。

itertools --- 効率的なループ実行のためのイテレータ生成関数 — Python 3.8.1 ドキュメント

実装
import itertools
mod = 10**9 + 7
N = int(input())
A = list(map(int,input().split()))
A.sort()
listA = [0 for _ in range(max(A)+1)]
setA = set(A)
for  a in setA:
    listA[a] = A.count(a)
ans = 0
for c in itertools.combinations(setA, 3):
    ans += listA[c[0]]*listA[c[1]]*listA[c[2]]%mod
print(ans%mod)

yukicoder No.959 tree and fire

python3 yukicoder 競技プログラミング

★２は少し難しく感じます。

問題

No.959 tree and fire - yukicoder

期待値は最近の高校生は学習していない可能性が高いです。
よくわからない人はざっくり平均のことだと思っておきましょう。
ちなみに数学Ｂの教科書に載っています。

各マス目について木が存在する確率を求めればよい。

  • 角について
    調べたいマス＋周り2マスが木であればよく，その確率は p ^ 3
    また，このようなマスは4マスある（角は４つ）。

  • 端（角以外）について
    調べたいマス＋周囲３マスが木であればよく，その確率は p ^ 4
    また，このようなマスは 2(N-2) + 2(M-2)マスある。

  • 内部（角，端以外）について
    調べたいマス＋周囲４マスが木であればよく，その確率は p ^ 5
    また，このようなマスは (N-2) \times (M-2) マスある。

従って，求める期待値は以下のようになる。
4p ^ 3 + (2(N-2)+2(N-4)) p ^ 4 + (M-2)(N-2)p ^ 5
N,M,Pの値から直接計算できるのでループ等を用いる必要もない。

注意

N=1のときなどのコーナーケースは場合分けが必要。

  • N=1かつM=1のとき
    pがそのまま期待値となる

  • N=1かつM \neq 1のとき（N,Mが逆のときも同じ）
    調べたいマス＋周囲２マスが木であればよく，そのようなマスは M-2マスあるので
    2p ^ 2 + (M-2)p ^ 3

ソースコードは以下

N,M = map(int,input().split())
p = float(input())
ans = 0
#1マスのとき
if N == 1 and M == 1:
    print(p)
    exit()
#細長いとき
if (N == 1 and M != 1) or (N != 1 and M == 1):
    E = max(N,M)
    print(2* p**2 + (E-2)* p**3)
    exit()
#それ以外
print(4* p**3 + 2*(M+N-4)* p**4 + (M-2)*(N-2)* p**5 )
余談

最初，上記の考察をしてから各マス目に対して上記の処理をループで実行したらTLEになりました。注意しましょう。