masuTomo’s blog

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

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

はじめに この記事は次のアドベントカレンダーの12/11の記事として投稿します。 qiita.com 対象読者 競技プログラミングをやっていて次のいずれにも当てはまらない方 上級者(AtCoder水色以上くらい) 競プロ忘年会に参加している人 (今日やってるらしい) …

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

更新が滞っており申し訳ありません. 停滞していた理由としては,全然解けなかったからです. 進捗 以前の記事で次は algo-method.com これに挑戦すると言っていました.最初はこのコンテンツの貪欲法に取り組みました. 貪欲法自体はそこそこかけて,Q1-1〜…

アルゴ式のテスターに選ばれました(10日目)

今後の方針 昨日,何とか動的計画法のコンテンツを終えたので,次にやるところをどこにしようか悩んでいましたが,アルゴ式さんから 「毎日アルゴ式」の過去問を埋めながら、日々の問題を並走していくのがよいと思います。 とアドバイスをいただいたので,素…

アルゴ式のテスターに選ばれました(9日目)

進捗 数日詰まっていたQ3-6に何とかACし,勢いそのままにQ3-7もACしました!やった!! Q3-6について 最初の実装 dp[i][j]はi番目までを使用しjを作れた場合は,j%Aの値.jを作れなかったときは-1. N, A, B = map(int,input().split()) X = list(map(lambda…

アルゴ式のテスターに選ばれました(8日目)

昨日からやっている問題に改めて挑戦した. 挑戦した問題はこちら 結論から言うとできていません.とりあえず愚直に実装したらTLEでした. N, A, B = map(int,input().split()) X = list(map(lambda x: int(x)%A ,input().split())) sumX = sum(X) dp = [ [-…

アルゴ式のテスターに選ばれました(5〜7日目)

進捗 土日はあまり進捗がありませんでした. Q3-4,Q3-5の二問を解きました. Q3-6もやりましたが,解けませんでした....むむむ algo-method.com 考えていること Q3-4,3-5は置いておいて,Q3-6で考えていることを書き留めておこうと思います. 問題設定は…

アルゴ式のテスターに選ばれました(4日目)

今日はやるだけにして書かないつもりでしたがやっぱり書きます. 進捗 動的計画法のQ3-1,Q3-2をやりました. Q3-1はスムーズに解けましたが,Q3-2は2時間くらい悩んだと思います. 感想 Q3-2の問題はタイトルの通り,本当によく見るDPの問題でした.もちろ…

アルゴ式のテスターに選ばれました(3日目)

更新しないって言ったじゃないか 進捗 今日も少し進めてQ2-5~Q2-7をやりました.まだ何とか自力ACです. 感想 Q2-7で少しつまりました.DPの部分ではなくて,loopの回し方がうまくいっていなかったり,二次元リストの初期化をミスしていたりしました. 勉強…

アルゴ式のテスターに選ばれました(3日目)

更新しないって言ったじゃないか 進捗 今日も少し進めてQ2-5~Q2-7をやりました.まだ何とか自力ACです. 感想 Q2-7で少しつまりました.DPの部分ではなくて,loopの回し方がうまくいっていなかったり,二次元リストの初期化をミスしていたりしました. 勉強…

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

別に毎日更新しようと思っているわけではありませんが,たまたま気が向いたので今日も書きます. 進捗 今日は動的計画法のQ2-1~Q2-4までをやりました.2次元の動的計画法の前半部分です.昨日取り組んだ内容と比べるとやや時間がかかりましたが何とかAC…

アルゴ式のテスターに選ばれました(1日目)

アルゴ式のテスターに応募したらなんと選ばれちゃいました. note.com 現状 アルゴ式の取組状況はこんな感じ. ちなみにAtCoderの色は茶色(2021/10/11)highestは847(緑) なお,大学院まで数学専攻ですがもう10年以上経っていますし,なんなら位相幾何学…

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

はじめに 暇つぶしにGoogleAppsScriptでいろいろ調べて遊んでいます.そこで作ってみたスクリプトを公開したいと思います. 作ったもの Google Formsで作成したアンケート等をGoogle Document形式に変換します. 機能詳細 GoogleFormsのタイトル,質問,選択…

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)…

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

はじめに 書くつもりはなかったが,公式解説がないようなのでメモ程度に書いてみることにした. 問題 ARC013 B - 引越しできるかな? 解法 各荷物の3辺において必ず 1番長い辺 2番目に長い辺 3番目に長い辺 が存在する(同じ長さがあれば,それらの順位付…

ABC129 C - Typical Stairs 解説

はじめに Pythonで実装しました.そんなところで差が出るなんて,,,という学びがあったので記事にします. 問題 ABC123 C - Typical Stairs 考え方 いわゆるDPの基本的な問題なのだとおもいます.フィボナッチ数列と同じです. 1歩または2歩進めるとうこと…

ABC186 解説(A~C)

A - Brick A - Brick ,のときは,個の荷物を載せることができる(個目を載せるとキログラムとなりオーバーする). これを素直に式に表すととなる(は余りを表す). 従って,この計算の商の部分が答えになる.pythonでは切り捨て処理は//で記述できる. N,…

ABC187 解説(D - Choose Me)

D - Choose Me D - Choose Me 貪欲法を用いる 何もしなければ,青木君はすべての票を,高橋君は0票となる.もし,町で高橋君が演説をすれば,青木君の票が票減り,高橋君の票が票増える.注意点は「 青木君の総得票数」<「高橋君の総得票数」となるときの演…

ABC187 解説(A~C)

はじめに Twitterを見ていると,意外と競技プログラミングに出てくる高校数学に慣れ親しんでいない人が多いという話だったので,簡単な問題でも解説記事は需要があるかもしれないと思ったので,解説記事を書くことにしました.また,最近ABCにはあまり参加で…

アルゴリズムとデータ構造(けんちょん本)4.1,4.2

トリボナッチ数列を計算するプログラム メモ化なし import time def tori(n): if n == 1: return 0 if n == 2: return 0 if n == 3: return 1 return tori(n-1) + tori(n-2) + tori(n-3) k = int(input()) memo = [-1 for _ in range(k+1)] start = time.tim…

アルゴリズムとデータ構造(けんちょん本)4.1,4.2

トリボナッチ数列を計算するプログラム メモ化なし import time def tori(n): if n == 1: return 0 if n == 2: return 0 if n == 3: return 1 return tori(n-1) + tori(n-2) + tori(n-3) k = int(input()) memo = [-1 for _ in range(k+1)] start = time.tim…

アルゴリズムとデータ構造(けんちょん本)3.4

アルゴリズムとデータ構造(けんちょん本) この本の気になった章末問題等をPythonでやったりして更新してみることにする。いつまで続くかはわからない。おかしな点があれば教えてください。 章末問題3.4 #入力の受け取り #入力でa_1, a_2, ,,,,a_Nを受け取…

アルゴリズムとデータ構造(けんちょん本)2.6

章末問題2.6 のグラフとその下側に作った長方形の面積を考える。 赤い長方形の面積は左から順に, となっている(縦横の比率がおかしいのは目をつぶる)。 である。 ここで, であるから,赤い長方形の面積の和<を得る。 以上のことから,であることがわ…

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

paizaの有料講座の無料分だけやってみました Python×AI・機械学習入門編1: 機械学習の概要を知ろうのチャプター一覧 | プログラミング学習サービス【paizaラーニング】 機械学習は少しだけ勉強したことがあったのですが、ここから先、どうやって勉強を進めて…

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

paizaの有料講座の無料分だけやってみました Python×AI・機械学習入門編1: 機械学習の概要を知ろうのチャプター一覧 | プログラミング学習サービス【paizaラーニング】 機械学習は少しだけ勉強したことがあったのですが、ここから先、どうやって勉強を進めて…

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

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

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

最近G Suite for Educationの利用が広がっているようですね。 私の職場でも最近活用が始まってきました。 特にGoogle Formsを利用してアンケート等を行うことが多いです。ただ,Formsの使い方がよくわからない人や,アンケートの原案を作るときにExcelを利用…

AtCoderで緑になりました。

昨日の日立製作所 社会システム事業部 プログラミングコンテスト2020で緑色になったので色変記事を書こうと思います。ラッキーで緑化した気もしますが,緑は緑です。胸をはります。 簡単な自己紹介 社会人です。大学での専攻は数学でしたが,競プロで役立ち…

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

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

蟻本をPythonで(LakeCounting)

本記事はnoteで書いていた記事の転載です。(noteからはてなブログに移行したため) AtCoderのコンテストに参加したり,蟻本を読んだりし始めました。 使用言語はPythonの予定。そこで,コンテストの参加記録や蟻本で勉強したことを書いていければいいなと思…

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

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