2020-01-01から1年間の記事一覧
ABまでできた。Bが案外難しかった。Cは勘違いしてた。Cは単純に累積和を別リストにもって頭から順番に足していけばいいだけだったのに過去問にひきづられて困惑。DはUnion-Find(実装したことなく、無理だった)。本番弱いなぁ。 内容 結果 どう考えたか + α…
かなりシンプルな問題。砕いて残ったものが1, 2, 3...という風に並んでる状態を目指す。左から順番に砕くか判定していく。 目次 目次 概要 制約 解くときに考えた内容 コード 書籍 最近ポチった書籍 アルゴリズムの参考書籍 概要 問題 1. 個のレンガが並んで…
目次 目次 概要 制約 解くときに考えた内容 コード 書籍 最近ポチった書籍 アルゴリズムの参考書籍 概要 問題 1. 人人でも均等にお菓子を分けられるような最小のお菓子の数は? 制約 は整数 解くときに考えた内容 単純にの最小公倍数を求める。 最小公倍数を…
startとgoalを自分で決める迷路で最長の手数のstartとgoalはなにかっていう問題。久しぶりに迷路問題解いた。普通はスタートとゴールを設定するんだけど、ゴールまで設定するとTLEになるので、スタートだけ設定して、BFSでやって最大手数の場所を結果的にゴ…
上下左右の移動だけでなく、制限があるワープができる条件で、最低限のワープ数で迷路にゴールできるかを問う問題。結論から言うと、計算量的にきつかった。自分にはこれ以上は思いつかなかったが、ともかく、普通の移動→そこをスタート地点してワープ→そこ…
その時点でのmax値を保持してその値より、小さかったら、差分を足すということを続けるだけ。 概要 解くときに考えた内容 TLE AC コード TLE AC 書籍 最近ポチった書籍 アルゴリズムの参考書籍 概要 問題 1. 人が並んでいる。 1. 順番に身長がである。 1. 左…
ABCまで、Dももうちょっとだった。Cで線形探索すればいいだけだったのに無駄なことで時間を使いすぎた。Dは久しぶりの迷路実装で忘れてた。今日ので復習が大事であることを再確認した。 内容 結果 どう考えたか + α A - Takoyaki B - Multiple of 9 C - Step…
先日手に入った「実用的でないPythonプログラミング」を読んだので、感想。実際にコードにも触れて感触を確かめた。Colabである程度はいじれるようにしたほうが都合がよかったので、かなりボリュームがあったので全てではないが、一部Colabでも動かせるよう…
当たり前だが、制約が大きいので、一つ一つ移動させてスコアの和の最大値を求めようとするとTLEになる。そこを工夫する必要があり、の和で考えて対応した。最初に選んだマスがある意味運命を左右することになるので(止まるという選択肢はあるものの)そこを…
移動している様子を書きながら、考えればできそう。 は正として考えればいいし、が小さめな時は0へどんどん向かっていけばいいし、動ける回数が余ったら、余った回数の偶奇で場合分けする。 概要 解くときに考えた内容 コード 概要 問題 1. 座標上のにいる。…
また、ABまで。しかもBで相当時間かけてしまってCの時間が足りなかった。まだまだ問題をこなす量が足りないのを実感。まぁでもCはちょっとだった。Dはとりあえず通る実装かけたけどこれをコンテスト中に書くのは辛い印象。 内容 結果 どう考えたか + α A - R…
馬場さんの「RとStanではじめる ベイズ統計モデリングによるデータ分析入門」を読んだので、感想。 今回の書籍はベイズ統計モデリングの初学者向けにぴったりで、内容がわかりやすくてガンガン読み進められた素晴らしい書籍。細かい話は概要に書く。 買おう…
問題を把握するには、連続したシグマが何を意味しているのか、XORの特性を理解することがポイント。それさえできれば結構単純。自分は桁ごとに考えた。制約としてギリなのでローカル化しないとTLE。もっと工夫できるのかもしれないけど。 目次 目次 概要 制…
問題文をみて瞬間に、ムムッとなる。データの読み込みに慣れていればさほどでもないが、いきなり嫌な感じがした。 結局、全探索っていう感じだが結構その探索も結構面倒。なるだけ詳細を書きながらまとめる。 目次 目次 概要 解くときに考えた内容 コード 書…
5年くらい前から英語再学習を始めた。きっかけは、たった2日間のインターナショナル・ミーティングに参加し、全然聞き取れなくて、話せなくて悔しい思いをした。その時にビジネスレベル(業務で使ったり、丁寧さや細かいニュアンスも重要とするようなレベル…
個存在する状態をを目指すようにして、それぞれの状態における最小の手数を数えて、全状態の中で最小値をみつければいい。状態をどう考えるか、その時の最小の手数はどう考えればいいかというのがポイント。 概要 解くときに考えた内容 反省点 コード 概要 …
問題は7, 77, 777 ... を純粋に並べようとするとTLEになってしまう。累乗の計算量というのはかなり大きいので、制約が大きい時はつかえないというのがポイント(知らなかったOrz)。あとは、あまりの話なので大きい数の余りを計算するのではなく余りを定数倍…
久しぶりのAtCoder Beginner Contetだったが、全然だめ。TLEとうまく頭の中で条件分岐できず、C, Dを解けず終了。 内容 結果 どう考えたか + α A - Air Conditioner B - Distance C - Repsept D - Alter Altar おわりに 内容 Python3でやっている。 参加ログ…
木グラフにおける辺彩色の問題。色分けに必要な最小な色数とその例をだす必要があるので、色分けの仕方をきちんと書き上げる必要がある。 DFSとBFSの違いを理解した状態で取り組んだので形式的だが、どちらもdequeを使ってやってみた。 目次 目次 概要 解く…
以前にTweetしたが、多読ってなんか飽きちゃってだめだなーと思っていたが、やっぱり話が面白ければ続きそうだと思った。多読は単語を調べないでっていうんだけど、まぁドメイン吸収程度は調べつつ、まとめつつ。だいたいわかればいいのでスプレッドシートで…
ナイトのコマがある動きをするときに、目的の場所にたどり着けるかどうかという問題。連立方程式も使うし、高速にを計算する必要もある。結構内容としては盛りだくさんで難しい。久しぶりにモジュラ逆数について考えたので軽くまとめた。 概要 解くときに考…
単純に計算すると計算量多すぎるので、桁の条件を詰めつつ最大値を求める方法と二分探索がある。 目次 目次 概要 解くときに考えた内容 コード 条件を満たす最大の桁におけるを計算 二分探索 概要 問題 の整数を買いたい。 買うには、円必要。(はの桁数) …
中井さんのITエンジニアのための強化学習理論入門を読んだので、感想。中井さんの書籍は数式や文章のストーリー展開がわかりやすくて、その期待も込みで購入。教育用の書籍になると思うので。 中井さんの新刊気付いてなくて連休中にポチった。強化学習の導入…
当たり前だが、安い時に買って、高い時に売ればいいっていうのを実装する。条件的にはその時点で所持する金と株の範囲内で1日に何回でも売り買いができるので、翌日上がる時に買えるだけ買って、翌日上がらないなら全部売るを常に繰り返せばいい。 こんな能…
結構単純。回テストがあって、頭から個ぶんたまったら、累積積(総乗)をずらしながら考える。 この時のポイントは、出と入の大小関係できまるので実際に総乗を計算する必要はないということ。(出と入については後述する。)解説は出と入の割合を計算してい…
M-SOLUTIONSが主催する個人戦のプログラミングコンテストに参加した。前回に引き続き、企業主催のコンテストに参戦。 何回かペナルティーがあったがABCDまで解けた 内容 結果 どう考えたか + α A - Kyu in AtCoder B - Magic 2 C - Marks D - Road to Millio…
街が個あるので全部パターン数えていると計算量が大きくなってしまう。最終的に平均の距離を出すのでそこも合わせて工夫する 概要 解くときに考えた内容 コード 愚直に、全経路パターンの和を出す方法 各街同士の距離の和を出して、重複回数をかける方法 概…
このコンテストのA, Bは九九の問題であった。この問題はそれを制約の範囲でかなり大きい表をイメージする。 がと大きいので工夫して探索 概要 解くときに考えた内容 コード 概要 問題 九九のようにのマスがある。 そのマスの値はである。 2以上の1つ整数を与…
同じ文字をグループとして捉えてその切れ目を数える 概要 解くときに考えた内容 コード 概要 問題 文字列が与えられる。 例えばaabbbbaacaであれば、[aa][bbb][aa][c][a]のように隣接する文字が同じ場合は一つのグループとする。(問題的にはスライム) 最終…
シェル関連のまとめ。特に新しいPCでなんかやらんといけなくなった時などに。 更新:2020-07-18 見出しを付け直し、一部修正。 プロンプト 2行プロンプト screen screenの使いかた .screenrc screen時のssh-agent etc ちょいちょい使うもの プロンプト 2行プ…