masuTomo’s blog

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

ChatGPTではじめてのPyAutoGUI（Google Map データ移行）

やりたいことと前提条件

  • 以前所属していた組織のGoogle アカウントをずっと使っていたが，それが停止されるということで，新しいアカウントにデータ移行したい．
  • 移行するデータはGoogle Mapのお気に入りリスト（スターではなく，ハート）
  • 移行するデータは約1000件（手動では無理）

使った技術

失敗したこと

  • Google MapのAPIを使って，データをエクスポート，インポート

PyAutoGUIについて

Google Map のAPI を使ったデータのインポートエクスポートは，どうやらできないことが判明したので（後述），お気に入りリストに登録されている店舗を新しいアカウントの Google Map上でお気に入りリストにコツコツ登録するしかないという結論に到達した． そのため，そのコツコツ登録する部分をPyAutoGUI で自動化することにしました．

環境構築

  • MacBook Air (M1)
  • Python 3.11.4 (Anaconda) を使用しました．

    PyAutoGUIのインストール（ChatGPT，BingAI頼み）

    せっかくなので流行りのChatGPTとBingAIに聞きながらやってみることにしました．

    pyautoguiのインストール1
    pipが使えませんといったら，手動インストールの手順を教えてくれたので，condaは使えることをお伝えしました．
    condaの使いかた
    condaを使ってインストールして，サンプルプログラムを実行するとエラーが出たので，エラーメッセージをそのままChatGPTに投げました．（本当はもっと長いです．一部だけ掲載しています）
    インストール時のエラー
    すると，親切にエラーの内容と解決法を教えてくれました．
    エラーの解決法
    つづき
    エラーの解決法の続き
    すると，（案の定）エラーは解決しなかったので，次の方法として教えてもらったWebページを見に行きましたが，404NotFoundでした． ChatGPTはここで手詰まりです．

そこで，GPT4が使えると噂のBingAIにも同じエラーメッセージを貼り付けて，解決法を聞いてみることにしました．

BingAIの回答
updateしてもダメなので，新しいconda環境を作成して無事エラーが消えてパッケージのインストールが完了しました．

コーディング

無事パッケージのインストールが終わったので，目的のプログラムを作成していきますが，PyAutoGUIパッケージの使い方がさっぱりわからないので，これも教えてもらうことにしました．

PyAutoGUIの使いかた

import pyautogui

# 画面サイズを取得
screenWidth, screenHeight = pyautogui.size()

# マウスカーソルの現在位置を取得
currentMouseX, currentMouseY = pyautogui.position()

# マウスカーソルをx座標100、y座標150に移動
pyautogui.moveTo(100, 150)

# 現在位置でクリック
pyautogui.click()

# x座標200、y座標220でクリック
pyautogui.click(200, 220)

# マウスカーソルを10ピクセル下に移動
pyautogui.move(None, 10)

# ダブルクリック
pyautogui.doubleClick()

# マウスカーソルをx座標500、y座標500に2秒かけて移動
pyautogui.moveTo(500, 500, duration=2, tween=pyautogui.easeInOutQuad)

# 'Hello world!'と入力（各キーの間隔は0.25秒）
pyautogui.write('Hello world!', interval=0.25)

# Escキーを押す
pyautogui.press('esc')

# Shiftキーを押し続ける
pyautogui.keyDown('shift')

# 左キーを6回押す
pyautogui.write(['left', 'left', 'left', 'left', 'left', 'left'])

# Shiftキーを離す
pyautogui.keyUp('shift')

# Ctrl + c のホットキーを押す
pyautogui.hotkey('ctrl', 'c')

これがわかったら大体やりたいことはできそうなので，次のようなコードを書いて無事完了です．

import pyautogui
import pyperclip
import csv


#お気に入りの店舗の情報が保存されているcsvファイル読み込み
stores = []
with open('favorites_stores.csv', 'r', encoding='utf-8') as f:
    for row in csv.reader(f):
        stores.append(row[2])

#spotlight の座標　1231 12
#spotlightを起動
pyautogui.click(1231, 12)
pyautogui.click()
pyautogui.PAUSE = 1 #1秒待ちを入れる
pyautogui.click()
pyautogui.sleep(0.2)

#spotlightからgoogle chromeを起動
pyautogui.write('google chrome', interval=0.05)
pyautogui.press('return')

#アドレスバーに移動
#画面の真ん中あたりをクリックして，chromeをアクティブにする
pyautogui.moveTo(622,413)
pyautogui.click(622,413)

for s in stores:

    #アドレスバーの内容を削除
    pyautogui.hotkey("command", "l")
    pyautogui.press('backspace')

    #リストのurlをクリップボードに格納
    pyperclip.copy(s)
    pyautogui.hotkey("command","v")
    pyautogui.press('return')
    pyautogui.PAUSE = 1

    #保存アイコンをクリック
    pyautogui.moveTo(217,551)
    pyautogui.click(217,551)
    #お気に入りリストに追加
    pyautogui.moveTo(220,590)
    pyautogui.click(220,590)
    #読み込み待ち
    pyautogui.PAUSE = 3 #秒待つ

最後に注意点をいくつか記載します．

  • 実際の画面遷移を伴うので，画面読み込み等のために適宜PAUSEを入れています．
  • google chrome上のクリックしたい場所は事前にpuautogui.positionで取得しておきます．
  • ウインドウが表示される場所によってクリックしたい座標が変わるので，クリックしたい座標を取得したらアプリケーションを閉じたりせずにプログラムを実行してしまいましょう．
  • 1000件くらいで，おそらく3-4時間程度かかりました（寝るまえに実行して，朝起きたら終わってました）

GASでGoogleスライド内のテキストデータを取得する

たくさんのGoogleスライドからテキストデータだけを抜き出してスプレッドシート上の一覧にするGASを作ったのでここに公開します．

背景

  • 研修講師として，参加者にGoogleスライドの雛形を配布（講師と共有設定されている）
  • その研修において，参加者がGoogleスライドに書き込みを行う
  • 研修実施後に，参加者がGoogleスライドにどのようなことを書き込みしているか確認したい

という状況において，書き込み内容を一覧化するGASコードを書きました．

イメージ

配布したGoogleスライドのイメージ
Googleスライドのテキストを一覧化したスプレッドシートのイメージ

コード

function main(){

    // フォルダの指定
    const folderId= 'Goolgeスライドが格納されているフォルダのID';
  
   //フォルダ内のすべてのファイルを取得
    const folder = DriveApp.getFolderById(folderId);
  
    //ファイルタイプを指定(MINEタイプ)
    const filetype = "application/vnd.google-apps.presentation"; //スライドを指定
    const files = folder.getFilesByType(filetype);
  
  
    //抜き出したテキストデータを転記するためのスプレッドシートを指定
    var sss = SpreadsheetApp.openById('スプレッドシートのID').getSheetByName("シート1");
  
    //何行目のデータか
    //スプレッドシートに書き込む行数
    let rowCnt = 1;
    //各ファイル（スライド）ごとにテキストデータを抜き出す
    while(files.hasNext()){
      
      let file = files.next();
      let fileURL = file.getUrl(); // ファイルURL
  
      var presentation = SlidesApp.openByUrl(fileURL);
      var slides = presentation.getSlides();
      //slidesの1枚目（インデックス０）を指定する
      //getpageElements()でページ要素のリストを取得
      var elements = slides[0].getPageElements();
      //テキストデータが格納されているオブジェクトごとに列をわけてスプレッドシートに書き込む
      var colCnt = 0;
  
      //各スライドのオブジェクトの数だけ繰り返す
      for(let i = 0; i < elements.length; i++){
        //オブジェクトがグループ化されている場合は，直接テキストデータが抜き出せない
        if (elements[i].getPageElementType() == SlidesApp.PageElementType.GROUP){
          //getChildrenでグループ化されているオブジェクトの中身のオブジェクトを取り出す
          var children = elements[i].asGroup().getChildren();
          for (let j = 0; j < children.length; j++){
              var tmpTxt = children[j].asShape().getText().asString();
              var tmpCell = sss.getRange(rowCnt, i+1+colCnt);
              tmpCell.setValue(tmpTxt);
              colCnt++;
          }
        //ページエレメントタイプがSHAPEの場合はテキストデータを直接抜き出せる
        }else if(elements[i].getPageElementType() == SlidesApp.PageElementType.SHAPE){
            var tmpTxt = elements[i].asShape().getText().asString();
            var tmpCell = sss.getRange(rowCnt, i+1+colCnt);
            tmpCell.setValue(tmpTxt);
            colCnt++;
        }
      }
      rowCnt++;
    }
  }

Javascriptがあまりわかっていないので，varとletの使い分けがおかしいかもしれません．

自分がいいねしたツイートの一覧を取得してGoogle Spread Sheetに出力する

動機

ツイッターをやっていて気になったツイートには，備忘録の意味をこめて，いいね！をすることが良くあるのですが，結局見返さないままになってしまっていました．そこで，Twitter APIを利用して，自分が過去にいいね！したツイートの一覧を取得してみました．

使ったもの

作ったもの

基本的な動き

1.自分のUserIDを指定する 2.指定したUserIDが過去にいいね！したツイートの一覧を取得する 3.取得したツイート一覧をGoogle SpreadSheet に表示する

検索部分のコード

  var userId = "user id を指定"; //@からはじまるusernameではなく，ただの数字の羅列
  var url = "https://api.twitter.com/2/users/" + userId + "/liked_tweets"; //URLの末尾にliked_tweetsと指定することで，いいね！したツイートが取得できるようだ
  
  //検索の設定
  var options = {
    "method": "get",
    "headers": {
      "User-Agent": "v2LikedTweetsJS", //これもこのまま書いておけばOK
      "authorization": "Bearer BearerTokenと呼ばれるものをここに書く",
    },
  };

 //取得した結果をJSON形式に変換
 var response = JSON.parse(UrlFetchApp.fetch(url, options));

基本的にはこんな感じである．あまりわかっていないが動いているのでヨシ！とする．BearerTokenについては，Twitter APIの使用申請をすればわかる（もらえる）．

user id について

自分がいいね！したツイートを取得したいので，自分のTwitter アカウントのuser idを指定する．調べ方は，ツイッターを開いてページソースから「id_str」の文字列を検索するとidが出てくる．

url について

上記のコードに記載したのが基本形である．ここにさらにオプションを付け加えたい場合は次のようにする．

var url = "https://api.twitter.com/2/users/" + userId + "/liked_tweets" + "?tweet.fields=author_id" + "&max_results=30";

検索オプションを1つだけつける場合は，末尾に?を付けてから，オプションtweet.fields=author_idなどをつける．2つ以上つける場合は&で連結する．

ちなみに，tweet.fields=author_idは，いいね！したツイートをしたユーザーのIDを取得しており，max_results=30は1回の検索で30件までしか取得しないというオプションである．

詳細はこちら

developer.twitter.com

取得結果をSpreadSheetに出力する

  //検索結果を出力するスプレッドシート
  const folderId = "**************"; //SpreadSheetが格納されているフォルダーのid
  const spreadSheetId = "**************";//結果を出力するSpreadSheetのid
  const sheet = SpreadsheetApp.openById(spreadSheetId);
  const ss = sheet.getSheetByName("シート1") //シートも名前で指定しておく（シートに対してでないと，getRangeが使えない）

  var nRow = 1;
  var col_author = 1;
  var col_text = 2;

   dat = response.data;
    for (let i = 0;  i < dat.length; i++){

      //レスポンスから値を取得
      author_id = dat[i]["author_id"];
      text = dat[i]["text"];

      //スプレッドシートに値をセット
      ss.getRange(nRow,col_author).setValue(author_id);
      ss.getRange(nRow,col_text).setValue(text);
      nRow++;
    }

おまけ

基本的には上述したような感じでOKだが，過去にいいね！したツイートがたくさんある場合は，一度には取得できない（おそらく一度に100件までしかツイートを取得できない）．そのような場合には，responseにnext_tokenと呼ばれるものがついてくる.それが検索結果についてきた場合は，それを使用して，再度リクエストを投げれば良い．その際にURLを次のように変更する.

var url = "https://api.twitter.com/2/users/" + userId + "/liked_tweets" + "?tweet.fields=author_id" + "&max_results=30"+"&pagination_token=" + nexttoken;

末尾のnexttokenにresponseから取得したnext_tokenの値を格納している．また，オプションで指定するときはpagenation_tokenであることにも注意が必要（これに気づかずしばらくはまった）．

おわりに

Webまわりのことは全く詳しくなく，いろいろ調べながら，まぁ動けばいいやというくらいの感じで作業しました．用語等にも誤りがあるかもしれませんし，この機能を使えばもっと簡単に実現できるというようなこともありそうです．例えばTweepyというサービス（ライブラリ？）がよく使われているようでした（何も知らない）．

今後やりたいこと

いいね！したツイートを取得したら，そのツイートをだれがしたのか知りたいですよね（idではなく，名前が知りたい）．ただ，一緒に取ってくる方法がわかりません．ツイートの取得とは別にuseridを指定すれば取得できるのですが，ツイートごとにその作業が必要なので，APIの呼び出し回数制限にひっかかってしまいます．

VSCodeでPythonが実行できなくなった話

なぜだかわからないが，急にVSCode上でPythonが実行できなくなった．

対処法として，備忘録を残しておく．

そもそもの環境

AnacondaでPython環境を作っており，VSCodeからそこの環境を指定して，Pythonを実行していた（はず）

やったこと

VSCodeの表示＞コマンドパレット＞Python:インタープリターを選択＞Conda環境を選択

なぜ？

最初の時もこの作業をやったはずなのだが，なぜか実行できなくなっていた． すぐ解決してよかった．

統計検定2級に合格しました

はじめに

職場で無料チケットがもらえたので統計検定2級を受験しました。結果は合格でした。

せっかくなので，合格までにやったことを整理することにします。（ただし，問題については言及できません）

勉強したこと

概要をつかむ

最初にこの本を読みました。読むだけなので1日でさっとやりました。厳密ではない部分もありますが，全体を俯瞰するのには良かったと思います。

https://www.amazon.co.jp/完全独習-統計学入門-小島-寛之/dp/4478820090www.amazon.co.jp

また，次のYouTube動画を参考にしました。

www.youtube.com

かなり正確で信頼を置いていますが，統計検定2級向けというわけではありません。

真面目に勉強する

次にこの本を一通り学習しました。

https://www.amazon.co.jp/入門統計解析-倉田-博史/dp/4883841405/ref=sr_1_1?__mk_ja_JP=カタカナ&crid=1PA60BEMF7KNQ&keywords=入門統計解析&qid=1644669058&s=books&sprefix=入門統計解析%2Cstripbooks%2C235&sr=1-1www.amazon.co.jp

大学初年度程度の教科書という位置付けのようです。数学の書籍としてはかなり読みやすい部類に入るのではないでしょうか。個人的にはかなりおすすめします。

通読して，各章末の問題もほぼ解きました。この一冊で統計検定2級の範囲はほぼ全て網羅できています。

過去問を解く

公式の過去問集を2〜3周しました。

https://www.amazon.co.jp/日本統計学会公式認定-統計検定-2級-公式問題集-2017〜2019年/dp/4788925524/ref=sr_1_3?__mk_ja_JP=カタカナ&crid=U0OBAVCLW2AV&keywords=統計検定2級&qid=1644669724&s=books&sprefix=統計検定2級%2Cstripbooks%2C282&sr=1-3www.amazon.co.jp

もう一つ新しいものもありますがどちらでも良いでしょう。

復習する

www.youtube.com

toketarou.com たまにこれ間違ってないか？と思う箇所もありましたが，概ね問題ないと思います。

過去問をやってわからなかったところを調べるのに使っていました。（受かることだけを目標にするなら，この動画とWebサイト，過去問で十分かもしれません。）

勉強の方針

合格することが目標ではなかったので，理解することに重きをおいたつもりです。

具体例を挙げます。 標本比率の区間推定と言われたら

\hat{p}-1.96\sqrt{ \hat{p} (1-\hat{p}) / n } \lt p \lt \hat{p}+1.96\sqrt{ \hat{p} (1-\hat{p}) / n }

が思い浮かぶ人もいると思います。（過去問の解説などでは、この式が公式的に書いてあることも多いと思います）

これをnが十分大のとき B(n,p)はN\left( np, np(1-p) \right)で近似できることから，\sum X \sim N(np,np(1-p))となり，\bar{X} \sim N(p,p(1-p)/n)が成り立つ。これを標準化して， ( \bar{X}-p ) / \sqrt{ p(1-p)/n } \sim N(0,1)という導出ができるようにしていました。

勉強以外の注意点

私が受験したのはCBT形式でした。 パソコン教室に行って，パソコンで受験しました。

受験してみて感じたことを挙げます。

  • PC画面では問題が読みにくい

いつも本でやっていたので，目の前にあるディスプレイに問題が表示されていたというのがやりにくかったです。また，本と違って問題文に書き込んだりできないのも普段と違う点でした。

  • 計算用紙について

本番で使用できる計算用紙はA4用紙2枚分のラミネートフィルムみたいなものでした。スペースが不足した場合は交換してもらえます。ただ，交換なので1枚回収されて，1枚もらえるという感じでした。

私は普段から，余白多め，文字大き目のスタイルなので，結局4枚目まで用紙を使用しました。 ペンも会場で渡されるものを使わないといけません。

  • 試験時間

緊張もあったのかもしれませんが，過去問を解いていたときは時間はかなり余裕だったと思うのですが，本番では時間ぎりぎり足りませんでした。 時間をきちんとはかって練習しておくのも大事かもしれません。

おわりに

このような資格試験は10年近く前に受けた情報処理試験以来でした。久しぶりでしたが，ちゃんと受かって良かったです。

これでやっと別のことに取り組めます。

非プログラマーがやる競技プログラミング

はじめに

この記事は次のアドベントカレンダーの12/11の記事として投稿します。 qiita.com

対象読者

競技プログラミングをやっていて次のいずれにも当てはまらない方

  • 上級者（AtCoder水色以上くらい）
  • 競プロ忘年会に参加している人 （今日やってるらしい）
  • IT系企業に勤めている
  • 理系大学（院）生である
  • 競技プログラミングを一緒にやる友達等がいる
  • Twitterに競プロをやっているフォロワー（リプライできるひと）がいる
  • めちゃめちゃ頭がいい（一人で精進してどんどん強くなれる）

要は周りに競プロやってる人いないけどやってみたい（やってるぞ），でも不安だな，という人に向けた記事のつもりです。

私の周囲の環境

  • 非ITの職場（エクセルマクロ使える人はほとんどいない）
  • 競技プログラミングという言葉を知っている人が知人にいない
  • 現実世界で競プロをやっている人と会ったことがない

一人で競プロをやっていて困ること

  • 情報が入ってこない
  • 勉強が続かない
  • 疑問が解決できない

この3つがとても大きいです。これらのことに焦点をあてて記事を書きたいと思います。

情報収集について

そもそも，このブログにたどり着いている方は，この部分を読む必要はない気がしますが，一応書きます。

Twitterをはじめる

これがほぼ唯一解な気がします。私自身，Twitterを始めた時期と競プロを始めた時期が（たまたま）ほぼ一致していますが，競プロの情報の9割以上はTwitterから得ています。

ここで，私がフォローしている競プロerのアカウントをいくつか紹介します。（勝手に紹介してすみません）

@chokudai いわずもがなAtCoderの偉い人。ぷよぷよとかその他の話題も多い。

@drken1215 @drken_procon けんちょん本の著者。アルゴリズムでググるとこの方のQittaの記事によく出会う。

@kenkoooo AtCoder Problemsの方。チョコケーキがお好きらしい。

@kyopro_friends よくAtCoderのコンテストのWriterをされているイメージ。コンテスト後に問題に対して解説ツイートしてくれるのだ。

@kaede20203 この方の周りには色々な競プロerが集まってこられてます。こつこつ続けられていて本当にすごいです。

@e869120 この度，競プロの本を出版されるとのこと（予約しました）

@sak_algo アルゴ式の方（大変お世話になりました）

※ほかにもたくさんの競プロerの方をフォローしていますが，ツイートの頻度や内容，私のアカウントから見つけやすかった，という3つの観点で選びました。 基本的には，ここで紹介した人のうち，数名をフォローしておけば，あとは芋づる式にたくさんの競プロerを発見することができる思います。

注意点

自分と同じくらいの実力の人もフォローしましょう。そして自分も発信しましょう。意外と自分と同じことで悩んでいる人もいるものです。

理由

基本的にフォロワーがたくさんいて発信力がある（Twitter上で有名）な方は強い方（AtCoderでいう青以上）が多い気がします。

コンテスト後のTLが，自分にはちんぷんかんぷんの話題ばかりになってしまい辛いです。

勉強が続かないことについて

正直難しいです。

競プロを一緒にやっている友人知人がいる場合は，コンテストのあとにわいわいすることもできるでしょう。そのために普段から勉強するというのも楽しいでしょうし，なんなら競プロゼミのようなことをやっている人もいるかもしれません。

ですが，ひとりぼっちだとそのどれもありません。せいぜいレート上がったことをツイートして，1つか2ついいねがつくくらいです。

それではなかなか難しいので，ある程度の強制力が必要だと思います。ここで私が色々試したことを列挙します。（合う合わないは個人差が大きいと思うので，私が挫折したものでも，みなさんに合うものもあるかもしれません）

とにかくコンテストに出る

これを私は川内優輝方式と読んでいます。つまり，本番で練習してしまおうということです。 最初の方の自分のレートがどんどんあがっている時期はいいのですが，レートが下がり始めると辛くなります。

自分でノルマを決める

毎日◯◯をやるぞ！と決めて取り組んだこともありました。個人的にはこれが一番合っているのですが，問題点として，わからない問題にぶつかったときに進捗がでない（後述）。仕事が忙しくなるとできなくなり，その後ペースを元に戻しにくい。

なお，このときはAtCoder Problemsのrecommendationの問題をこつこつやっていました。

Paizaに課金する

1ヶ月くらいで挫折しました。3ヶ月やったうちの2ヶ月分くらいの利用料は無駄になりました。

アルゴ式をやる

アルゴ式でテスターをやらせてもらう機会をいただきました。コーチング，ペースメイキングということでサポートいただきましたが，結局この他者からのプレッシャーが一番効果的だった気がします（結局一人ぼっちじゃ無理ということになってしまう）。

ちなみに，テスター期間は終了してしまいましたが，アルゴ式に取り組むこと自体は継続しています（アルゴ式は初学者向けのコンテンツとして，とてもおすすめだと思います）。

疑問の解決について（精進）

書籍について

書籍とWebサービス以外に頼れるものはありません。ここでは私が所有している書籍をご紹介します。

www.amazon.co.jp

www.amazon.co.jp

www.amazon.co.jp

*プログラミングコンテスト攻略のためのアルゴリズムとデータ構造（マイナビ）

www.amazon.co.jp

このうち，役にたったと感じているのは最初の2冊かと思っています。それ以外の本はちょっと初心者には難しいです。ただ，蟻本などは辞書的に使うことがあります。 一緒に読み進めたり，質問できる相手がいれば良いのでしょうが，一人なのでそうもいきません。

そのことを打破するために次の提案します。

アウトプットの機会をつくる

Twitterかブログで発信しましょう。一人で勉強していると知識を得るという意識に偏りがちなので発信することを意識するのが良いと思います。

友人知人がいることの良さは議論できることだと思っています。もう少し限定すると，自分の口で説明する機会が得られることとしても良いかもしれません。ベアプログラミングと似たような考えでしょうか。

発信することで自分の考えを整理するきっかけになりますし，自分がわかっていない部分が明確になります。

初学者は，なかなかそのような行動は取りにくいかもしれませんが，同じような初学者で困っている人も多くいます（AtCoderでも灰・茶の人がほとんどなのですから）。 ぜひやってみてください。

もし，みなさんがそのようなブログやツイートを見かけたら積極的にいいねするようにしてあげてください。

おわりに

とりとめのないことをつらつらと書いてしまい非常に読みづらかったのではないかと思います。

ずっと一人で競プロをやっていて，続ける工夫を試行錯誤する中の一つの取り組みとしてこのアドベントカレンダーを利用させてもらいました。ごめんなさい。

私は地方に住んでおり，競プロのイベントにも気軽に参加できません。最初に書いたように一緒にやる知人もいません。ときには次のようなツイートをしたこともあります。

冗談ですが，心情としてはこんな感じです。 もし，ここまで読んでくださった稀有な方がいらっしゃれば，ぜひ私と一緒に競プロをやりましょう。よろしくお願いします。

最後までお読みくださいありがとうございました。

アルゴ式のテスターに選ばれました（20日目?）グラフ入門で苦労しています

更新が滞っており申し訳ありません．

停滞していた理由としては，全然解けなかったからです．

進捗

以前の記事で次は

algo-method.com

これに挑戦すると言っていました．最初はこのコンテンツの貪欲法に取り組みました．

貪欲法自体はそこそこかけて，Q1-1〜Q1-7まで自力でACできました．その次にグラフ入門のコンテンツに取り組むことにしました． アルゴ式には教科書があるので，それを読みながら進めることでQ3-4まではサクサク解くことができました（3日くらいでここまで到達）．

そこからQ3-5でかなり詰まりました．

algo-method.com

Q3-5について

問題

次の操作を k = 0,・・・N-1について順番に行う．

  1. もし k=0なら頂点0に色を塗る

  2. もし k ≠ 0 ならi-1回目の操作で色が塗られた頂点と繋がっており、まだ色が塗られていない頂点に色を塗る。

操作 k によって色が塗られた頂点を番号が小さい順に全て求めよ。（ただしk=iのときの操作を操作iという）

考察

最初の提出

操作自体はシンプル．とにかく頂点0からはじめて隣にある頂点に順番に色を塗っていけばよいので，BFSかな？とすぐ察しがつきました．

で，最初の（ちゃんと）提出したコードがこちら

from collections import deque
#入力を受け取って，頂点と辺の情報をリストGに格納
N, M = map(int, input().split())
G = [ [] for _ in range(N)]
for _ in range(M):
    A, B = map(int,input().split())
    G[A].append(B)
    G[B].append(A)

#彩色済みかどうか
DONE = [ False for _ in range(N)] 

#最初は頂点0から始める
print(0)
DONE[0] = True

#NEXTには，次の操作で色を塗る頂点を格納する．
#最初は頂点0と繋がっている頂点を格納しておく
NEXT = deque(G[0])
l = len(NEXT)

while l > 0:
    for _ in range(l):
　
　　 #NEXTから取り出して，表示，DONE[v]=True（頂点vに色を塗った）とする
        v = NEXT.popleft()
        print( v, end = ' ' if not DONE[v] else '')
        DONE[v] = True

        #頂点vに色を塗ったので，vと繋がっている頂点をNEXTに格納する
        for x in G[v]:
            #すでに色が塗られている頂点と，すでにNEXTに格納されている頂点は除く
            if not DONE[x] and x not in set(NEXT):
                NEXT.append(x)
　
    l = len(NEXT)
    print()

5AC，3WA，2TLEでした．

まぁいろいろよくなかったです．すぐにわかることとして，出力条件の

作 k によって色が塗られた頂点を番号が小さい順に全て求めよ。

番号が小さい順という点を全く考慮していませんでした（読み飛ばしてしまっていました）．実際，WAしたテストケースを見てみると

  • 入力
7 13
4 3
1 4
1 6
0 3
5 0
6 0
5 6
2 6
6 4
5 1
2 4
4 5
5 3
  • 上記コードの出力
0
3 5 6 
4 1 2
  • 正しい出力
0
3 5 6
1 2 4

となっており，出力の3行目の数字の順番が異なっています．

なので，NEXTに頂点を格納するときにソートしてやれば良いということになります．

次の提出

ということで実装したものがこちら

from collections import deque
N, M = map(int, input().split())
G = [ [] for _ in range(N)]
for _ in range(M):
    A, B = map(int,input().split())
    G[A].append(B)
    G[B].append(A)

#彩色済みかどうか
DONE = [ False for _ in range(N)] 

print(0)
DONE[0] = True
G[0].sort()
NEXT = deque(G[0])
l = len(NEXT)
while NEXT:
    tmp = []
    for _ in range(l):
        v = NEXT.popleft()
        print( v, end = ' ' if not DONE[v] else '')
        DONE[v] = True
        #vの隣接頂点のうちでまだ彩色されていない点をtmpに格納
        #NEXTはキューなのでソートできない
        for x in G[v]:
            if not DONE[x] and x not in NEXT and x not in tmp:
                tmp.append(x)
    tmp.sort()
    for t in tmp:
        NEXT.append(t)
    l = len(NEXT)
    print()

としました．これで1ケースのみTLEであとはACしました．

注意 NEXTにキューを使う必要はありません．なぜかキューを使わないといけないと思い込んでいました．

最後の提出

このTLEがなかなかとれず，アルゴ式さんに

「できません〜」と泣きついたところ

f:id:masuTomo:20211031095842p:plain

さらに

f:id:masuTomo:20211031100025p:plain

ということで修正しました

from collections import deque
N, M = map(int, input().split())
G = [ [] for _ in range(N)]
for _ in range(M):
    A, B = map(int,input().split())
    G[A].append(B)
    G[B].append(A)

#彩色済みかどうか
DONE = [ False for _ in range(N)] 

print(0)
DONE[0] = True
G[0].sort()
NEXT = deque(G[0])
l = len(NEXT)
while NEXT:

    #tmpをセットに変更
    tmp = set()

    for _ in range(l):
        v = NEXT.popleft()
        print( v, end = ' ' if not DONE[v] else '')
        DONE[v] = True
        #vの隣接頂点のうちでまだ彩色されていない点をNEXTに格納
        for x in G[v]:
            if not DONE[x] and x not in set(NEXT) and x not in tmp:
                tmp.add(x)
    tmp = sorted(tmp)
    for t in tmp:
        NEXT.append(t)
    l = len(NEXT)
    print()

まだTLEでしたが，たしかに実行時間で比べるとかなり早くなっていました．

また，このあと

f:id:masuTomo:20211031100444p:plain

f:id:masuTomo:20211031100525p:plain

とアドバイスをいただきました．

後半の

tmp に x を挿入する瞬間に DONE[x] = True にしてしまうことが考えられます！

の部分はおそらく自力では思いつけなかったのではないかと思います．だって，色を塗ったかどうかの判定をリストDONEに格納しています．色を塗ったあとでは遅いのです．NEXTに格納した瞬間に，色を塗ることは確定するのだからそのタイミングでTrueにせよ，と．難しいです．

DONEじゃなくてTODOの気持ちだそうです．

何はともあれ，実装しました．

from collections import deque
N, M = map(int, input().split())
G = [ [] for _ in range(N)]
for _ in range(M):
    A, B = map(int,input().split())
    G[A].append(B)
    G[B].append(A)

#彩色済みかどうか
DONE = [ False for _ in range(N)] 

print(0)
DONE[0] = True
G[0].sort()
NEXT = deque(G[0])

#ここも追記
for g in G[0]:
    DONE[g] = True

l = len(NEXT)

while NEXT:
    tmp = set()
    for _ in range(l):
        v = NEXT.popleft()
        print( v, end = ' ')

        #DONE[v] = True

        #vの隣接頂点のうちでまだ彩色されていない点をNEXTに格納
        for x in G[v]:
            if not DONE[x]:
                tmp.add(x)
                DONE[x] = True

    tmp = sorted(tmp)
    for t in tmp:
        NEXT.append(t)
    l = len(NEXT)
    print()

無事ACです．

おわりに

アルゴ式さんのアドバイスによりなんとかACできました．ちなみに解説のコードはもっとすっきりしていました．（当然キューもつかっていない）．