masuTomo’s blog

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

アルゴリズムとデータ構造（けんちょん本）２．６

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

章末問題２．６

y = \dfrac{1}{x}のグラフとその下側に作った長方形の面積を考える。
赤い長方形の面積は左から順に， 1, \dfrac{1}{2}, \dfrac{1}{3}, \cdots ,\dfrac{1}{10} となっている（縦横の比率がおかしいのは目をつぶる）。
（赤い長方形の面積の和） \lt \int_1 ^N \dfrac{1}{x} dx + 1である。
ここで，
\int _1 ^N \dfrac{1}{x} dx = \log Nであるから，赤い長方形の面積の和< \log Nを得る。 f:id:masuTomo:20201006221522p:plain

以上のことから， 1+\dfrac{1}{2}+ \dfrac{1}{3} + \cdots + \dfrac{1}{N} = O(\log N)であることがわかった。

おまけ

上記の図では， y = \dfrac{1}{x}の下側の長方形の面積の和（不足和，Lower Sum）と積分値を比較したが，逆にグラフの上側にはみでるように長方形を作って，その長方形の和（過剰和, Upper Sum）を考えることで，上から抑えることもできる。下からも上からも評価できるので，結果として 1+\dfrac{1}{2}+ \dfrac{1}{3} + \cdots + \dfrac{1}{N} = \Theta(\log N)がわかる。

Paiza 「Python×AI・機械学習入門編1: 機械学習の概要を知ろう」無料分だけやってみた

paizaの有料講座の無料分だけやってみました

Python×AI・機械学習入門編1: 機械学習の概要を知ろうのチャプター一覧 | プログラミング学習サービス【paizaラーニング】

機械学習は少しだけ勉強したことがあったのですが、ここから先、どうやって勉強を進めていくか悩ましかったので、とりあえず無料分だけやってみました。

想定する受講者はPythonの基礎ができている人、とのこと。 とりあえずやってみたが、無料分だけだと何ともいえない。 チャプター1は機械学習のほんとに最初の部分について。具体的には

  • 分類問題、回帰分析

  • 教師あり、教師なし

あたりの説明

チャプター２は、paizaラーニングのこの講座で使う環境と少しだけライブラリ（matplotlib）の話

  • jupyternotebookが使えるので環境構築不要

  • matplotlibを使って簡単なグラフを描画

という感じでした。

有料部分の講座

こちらは受講していないので詳細は分かりませんが

  • 問題と入出力データを考えよう

  • 画像から特徴量を抽出しよう

  • scikit learnで学習と予測を行おう

  • 特徴量に明度のヒストグラムを利用しよう

という内容でした。

お金を払ってやってみるべきかどうか

正直、この講座だけのためであれば無料のものを利用してこれ以上の内容が学習できると思います。 例えば、 大学生のためのデータサイエンス（Ⅱ） | gacco などのmoocといわれるサービス（？）を利用しても良いかもしれません。

ただ、Paizaは1講座いくら、という料金体系ではなく、月額制でPaizaが提供する講座のすべてを受講できる（たぶん）という仕組みのようです。
料金は * 1078円/月

  • 4488円/半年 = 748円/月

  • 7200円/年　= 600円/月 となっています。 この講座だけでなく、

  • C入門

  • linux入門

  • DB/SQL入門 など幅広い講座があります。いちいち書籍等を購入することを考えると有料会員になっても良いような気もします。 書籍を購入したら1冊3000円とかざらですからね。

また、自分のコードを採点してもらえるのも書籍等にはない強みだと思います。継続的に勉強できる人（月額料金を無駄にしない自信がある人）にはおすすめできるかもしれません。

最後に

この記事は、ステッカー等が欲しくて頑張って書きました。普段はPaizaのスキルチェックしかほぼ利用していませんが、スキルチェック問題の解説を公開するのは違反のようでしたので、無料講座を受講してその紹介記事を書きました。

思ったよりも月額料金が安かったので、やってみてもいいかなという気持ちになりました。

Paiza 「Python×AI・機械学習入門編1: 機械学習の概要を知ろう」無料分だけやってみた

paizaの有料講座の無料分だけやってみました

Python×AI・機械学習入門編1: 機械学習の概要を知ろうのチャプター一覧 | プログラミング学習サービス【paizaラーニング】

機械学習は少しだけ勉強したことがあったのですが、ここから先、どうやって勉強を進めていくか悩ましかったので、とりあえず無料分だけやってみました。

想定する受講者はPythonの基礎ができている人、とのこと。 とりあえずやってみたが、無料分だけだと何ともいえない。 チャプター1は機械学習のほんとに最初の部分について。具体的には

  • 分類問題、回帰分析

  • 教師あり、教師なし

あたりの説明 チャプター２は、paizaラーニングのこの講座で使う環境と少しだけライブラリ（matplotlib）の話

  • jupyternotebookが使えるので環境構築不要

  • matplotlibを使って簡単なグラフを描画

という感じでした。

有料部分の講座

こちらは受講していないので詳細は分かりませんが

  • 問題と入出力データを考えよう

*画像から特徴量を抽出しよう

  • scikit learnで学習と予測を行おう

  • 特徴量に明度のヒストグラムを利用しよう

という内容でした。

お金を払ってやってみるべきかどうか

正直、この講座だけのためであれば無料のものを利用してこれ以上の内容が学習できると思います。 例えば、 大学生のためのデータサイエンス（Ⅱ） | gacco などのmoocといわれるサービス（？）を利用しても良いかもしれません。

ただ、Paizaは1講座いくら、という料金体系ではなく、月額制でPaizaが提供する講座のすべてを受講できる（たぶん）という仕組みのようです。
料金は * 1078円/月 * 4488円/半年 = 748円/月 * 7200円/年　= 600円/月 となっています。 この講座だけでなく、

  • C入門

  • linux入門

  • DB/SQL入門 など幅広い講座があります。いちいち書籍等を購入することを考えると有料会員になっても良いような気もします。 書籍を購入したら1冊3000円とかざらですからね。

また、自分のコードを採点してもらえるのも書籍等にはない強みだと思います。継続的に勉強できる人（月額料金を無駄にしない自身がある人）にはおすすめできるかもしれません。

最後に

この記事は、ステッカー等が欲しくて頑張って書きました。普段はPaizaのスキルチェックしかほぼ利用していませんが、スキルチェック問題の解説を公開するのは違反のようでしたので、無料講座を受講してその紹介記事を書きました。

思ったよりも月額料金が安かったので、やってみてもいいかなという気持ちになりました。

Pythonでwebスクレイピング（ログインとデータ取得）

python3 webスクレイピング

動機

バイクの免許を取ろうと，自動車学校に通うことにした。講習はwebからの予約制であり，今は新型コロナウイルスで大学が休みだったりするらしく，例年より生徒が多いらしい。そこで，予約に空きがでたらすぐに確認・予約ができるようにpythonでwebスクレイピングしてみることにした。

条件

  1. 自動車学校のホームページの予約ページから，idとパスワードを入力してログインする

  2. ログイン先の画面から予約可能枠を取得

  3. 予約可能枠を自分のラインに送信する

  4. 上記の操作を定期的に実行する

自動で予約するところまで作ろうかとも思ったが，変な予約してしまうことのリスクを避けるため，予約状況を送信するにとどめました（大変そうだったからというのもある）。

実装

やり方を調べる

とりあえず，「python　webスクレイピング　ログイン」などとしてググってみると，いろいろ記事がある。seleniumというのを利用すると簡単らしいということがわかったので，それを利用した。

shimi-dai.com

また，ブラウザ（Google Chrome）にアクセスするためにはchromedriverと呼ばれるものが必要らしく，それをダウンロードしてきて，適当な場所に格納する（そこにパスを通すのを忘れずに）

Downloads - ChromeDriver - WebDriver for Chrome

最新版でいいだろ，と思って適当にやったらエラーがでました。サポートしているchromeのバージョンを確認しておきましょう。（Chromeのヘルプでバージョンを確認したら83，最新です。となっていたのにchromedriverの最新版はchromeのver84をサポートしているようでした。どういうこと？）

ログインする

from selenium import webdriver
from selenium.webdriver.chrome.options import Options

url = "ログインしたいwebページのURL"

# ヘッドレスモードの設定。
# True => ブラウザを描写しない。
# False => ブラウザを描写する。
options = Options()
options.add_argument('--headless')

# Chromeを起動
driver = webdriver.Chrome(executable_path="chromedriverのexeのパスを指定", chrome_options=options)

# ログインページを開く
driver.get(url)

idとパスワードを入力する

まずは，idとパスワードの入力欄を取得してくる必要がある。chromeブラウザでログインページを開いてF12（その他のツールからデベロッパツール）を押すと，ページソースが見れる。 f:id:masuTomo:20200621111220p:plain さらにソースが見えているエリアの左上の矢印ボタンを押しておく。
その状態で，画面左側にマウスカーソルを持っていくと，画面上のアイテムに該当するソースがハイライトされる。 f:id:masuTomo:20200621111246p:plain この方法で入力欄のidなどを調べる。idを指定して，アイテムを取得し，そこに値を引き渡す。

from selenium.webdriver.common.keys import Keys

#入力欄にidを入力する処理
driver.find_element_by_id('idを入力するアイテムのid').send_keys('あなたのid')
driver.find_element_by_id('パスワードを入力するアイテムのid').send_keys('あなたのパスワード')
#ログインボタンをクリックする処理
driver.find_element_by_id('ログインボタンのid').send_keys(Keys.ENTER)

アイテムによってはidが指定されていなかったりという状況もあるので，取得したいアイテムに合わせるメソッドを利用する。classやname属性を指定することもできる。

qiita.com

これで，ログイン後の画面に遷移しているはずである。ただし，ページ読み込みなどに時間がかかる場合があるので念のためこんな感じの処理を入れておく。

from time import sleep
#ページ読み込み待機
sleep(5)

ログイン後画面から予約情報を読み取る

なんだかよくわからないがbeautifulsoupなるものを利用することが多いらしく，真似してみた。

from bs4 import BeautifulSoup

# # soupオブジェクトを作成（ここはよくわかっていないのでおまじないのつもり）
soup = BeautifulSoup(driver.page_source, "lxml")

で，このsoupオブジェクトからページ要素を取得する方法がわからなかったのだが，find，fild_allなどというメソッドが用意されているようで，それを利用すれば，ページ要素からタグを指定して値を取得することができるようだった。 私が調べたいサイトは予約枠がテーブルで書かれており，idが割り振られていなかったため，tdタグとclassを指定して取得した。
ページソースを眺めていると，classがstatus1だと予約可能，status3は自分の予約，という風になっていたので，statsu1を指定して要素を取得することとした。当然，複数の予約可能枠があるので，それをリストに格納することにした。

#予約ページからstatus1（予約可能）の情報を取得
tmp_list = list(str(soup.find_all('td', class_ = 'status1')).split())

そこのタグ内に日付や時間情報も持っていたので，文字列操作でそこを取り出しておいた。

取得した予約可能枠をLINEに送信する

LINEのアクセストークンというものを発行しなければならないらしいが，とても簡単だった。

qiita.com

import requests

#line送信の準備    
lineurl = "https://notify-api.line.me/api/notify"
access_token = '自分のアクセストークン'
headers = {'Authorization': 'Bearer ' + access_token}

message = ’送信したい文字列’
payload = {'message': message}
r = requests.post(lineurl, headers=headers, params=payload,)

定期的に実行する

pythonプログラムを実行するbatファイルを作成して，それをタスクスケジューラから定期的に実行する形にした。
batファイルはこんな感じ

cd C:\Users\username\workspace\pythonファイルのパス
py 実行したいファイル.py

タスクスケジューラの場所は[スタートメニュー]→[Windows管理ツール]→[タスクスケジューラ]

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)