masuTomo’s blog

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

python3

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を受け取…

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

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

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

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

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

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

yukicoder No.118 門松列(2)

★★に早く慣れたい。 問題 No.118 門松列(2) - yukicoder 長さが違う3本の竹を選べば適当に並べ替えることで門松列にすることができるので,異なる長さの竹を3本選ぶ選び方の総数(同じ長さの竹も区別する)を求めればよい。 同じ長さの竹が何本あるかがわか…

yukicoder No.959 tree and fire

★2は少し難しく感じます。 問題 No.959 tree and fire - yukicoder 期待値は最近の高校生は学習していない可能性が高いです。 よくわからない人はざっくり平均のことだと思っておきましょう。 ちなみに数学Bの教科書に載っています。 各マス目について木が…

yukicoder No.893 お客様を誘導せよ

この問題は別に書かなくてもいいかなと思ったけど,みんなそう思ったのか解説記事が少なそうなので一応書くことにした。 問題 No.893 お客様を誘導せよ - yukicoder やり方はすぐわかると思われる。 上図のようにレジ(塗りつぶしがレジ,白の四角が人)に人…

yukicoder No.897 compαctree

一問ずつ記事をかくのはどうなのか?という思いもある。 問題 No.897 compαctree - yukicoder 少し図を書いて考察すればすぐに規則がわかる。 N = 41, K = 3として考えてみる。 深さを最小にしたいので,各頂点に対する子の数はK個とするのが最良である。 …

yukicoder No.927 Second Permutation

時間ができたらyukicoderの★1.5~★2あたりを解いて勉強することにしている。今日はこれ。 No.927 Second Permutation No.927 Second Permutation - yukicoder 問題を読んだら,やることはわかる。 というか短い桁数のものなら人間の手でやった方が楽ちん。 …

ABC149 A~Dについて

遅ればせながら年末にあったAtCoderのABC149のA ~D問題をやった。 AtCoder Beginner Contest 149 - AtCoder A - Strings A - Strings 入力された文字列を結合して出力すれば良い(順番に注意)。 各々が使用している言語の文字列結合の方法について学習すれ…

マスター・オブ・整数で競技プログラミング その3 つづき

問題 解説 と書き直すとは互いに素。また,。これらをに代入して整理すると ここでの素因数分解を考える。 が素数のとき のときのみ条件を満たすが,は自然数より条件を満たすようなは存在しない。 のとき すべてののとき ,つまり,は互いに素となり,なの…

マスター・オブ・整数で競技プログラミング その3

3 最小公倍数と最大公倍数 最小公倍数と最大公約数の利用 たてA cm, 横B cm, 高さC cmの直方体がたくさんある。この箱を隙間なく並べて立方体を作る。作ることができる最小の立方体の1辺の長さを求めよ。 A,B,Cの最小公倍数を求めればよい。最小公倍…

マスター・オブ・整数で競技プログラミング その2

2 素因数分解の利用 素因数の個数 2で割り切れる回数 自然数Nに対して,1~Nまでの自然数の積をPとする。 (1)Pが2で何回割り切れるか。 愚直な実装をすれば,素直に2で割り続ければよい。 def func(n): if n == 1: return 1 return n*func(n-1) N = int(in…

ABC 079 C - Train Ticketを再帰関数で解く

再帰関数と全探索の勉強 問題 atcoder.jp 参考にしたサイト qiita.com qiita.com いずれもこの方のページ。他にもたくさん競プロ向け記事を書いていらっしゃいます。 qiita.com 考察(とりあえず再帰を使ってみる) 全探索と再帰の勉強のための解きなおしな…