masuTomo’s blog

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

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

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

蟻本をPythonで(LakeCounting)

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

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…

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

マスター・オブ・整数とは マスター・オブ・整数とは,雑誌「大学への数学」の分野別充填シリーズ。主に難関大学を目指す高校生向けの書籍である。 競技プログラミングに高校数学の整数分野の知識,テクニックが役に立つとよく聞くので冬休みを利用して解き…

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

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

ABC147 C HonestOrUnkind2

問題 atcoder.jp N人の正直者(必ず本当のことを言う)か不誠実な人(本当のことを言うかわからない)がいる。N人の人が〇〇さんは正直者(または不誠実な人)だよと証言する。証言が矛盾しない範囲で,最大で何人の正直者がいるかを求めよ。 試行錯誤(全探…

yukicoder No.36 素数が嫌い!

今日もyukicoder 問題 yukicoder.me 入力で与えられた数が「素数,1,使う数自身」以外で割り切れるかどうかを判定する。 考え方 1はダメ。素数もダメ,入力で与えられた数Nもダメ。それ以外の数字で割り切れればOKということなので,合成数の約数を持つかど…

yukicoder No.16 累乗の加算

※noteに記事を投稿していましたが,数式を書きたくなることがたまにあるのでHatena Blogも試してみることにしました。 note.com 下記問題に挑戦した。問題詳細は以下。 yukicoder.me 愚直に実装したらTLEでした(そりゃそうだ)。 x, N = map(int,input().sp…