AtCoder
下記で書いたptvsdよりも簡単な方法があった。ソースコード側への修正は不要になる。 VSCode+Pythonのリモートデバッグ - 自分用メモ 使うもの github.com 使い方 使い方はptvsdと似ている。 python実行するとデバッガが接続しにくるまで待つので、VScodeの…
追記:もっと良い方法があった。こっちだとソース修正が不要になる。→ VSCode+Pythonのリモートデバッグ:その2 - 自分用メモ HTTF2022のようなマラソンマッチでは、作成したpythonスクリプトを別プログラムからキックすることになることが多い。 普段のよ…
最近の競プロのブームによって平均レベルが上っているような感じがするのと、競技プログラミングを1年以上サボっていて実力が落ちた感もあって、 このままでは水色維持なんてとてもじゃないけど無理だ・・・と思ったので、競プロ典型90問によってトレーニン…
問題 atcoder.jp 挑戦結果 挑戦日:2021/11/03 結果:解けた 時間:30分 考えたこと 約数を列挙して、permutationで組み合わせを全パターン列挙。やってみたけどTLEだった。 ライブラリ化していた約数列挙のアルゴリズムのような感じで、a,bを決めてしまい、…
問題 atcoder.jp 挑戦結果 挑戦日:2021/11/03 結果:解けた 時間:20分ぐらい 考えたこと ????ox????となっていたら、 lはoか左の?部分から何を選んでもいいし、rはxか右の?部分から何を選んでもいい lを各字に固定して、lの右で一番近い別文字を見つければ…
問題 atcoder.jp 挑戦結果 挑戦日:2021/11/03 結果:解けた 時間:2時間ぐらい 考えたこと i桁の整数単位で計算すれば良さそう 解法は5分ぐらいで思いついたけど、実装やデバッグがうまく行かなかった・・・。 公式解説 https://twitter.com/e869120/status…
問題 atcoder.jp 挑戦結果 挑戦日:2021/11/01 結果:解けた 時間:10分 考えたこと 一番右下1箇所だけ更新してよいのか?を迷った。 そうだとすると、どんな場合もBに一致できそうだし、例とその答えとも一致しなくなるので、あくまで4箇所更新が必須という…
問題 atcoder.jp 挑戦結果 挑戦日:2021/11/01 結果:解けた 時間:10分 考えたこと グラフをマトリックスで持つと、1頂点について確認するのにグラフをナメないと行けないのでTLEするのかなと思った。 グラフを集合もってもナメないとダメなので、優先度付…
問題 atcoder.jp 挑戦結果 挑戦日:2021/10/31 結果:解けた 時間:15分 考えたこと 1周して戻るときは、modをとって計算 しゃくとり法の感じで、現在が求めたい面積より多いときは縮める、少ないときは伸ばすをしていき、見つかるかどうかを行えば良い 公式…
問題 atcoder.jp 挑戦結果 挑戦日:2021/10/31 結果:解けた 時間:5分 考えたこと まずは素因数分解する。いちばん効率が良いのは、 の を一番効率よく分割するのは、との素因数の数が同じになるようにすること。 素因数分解はいぜんにライブラリ化してある…
問題 atcoder.jp 挑戦結果 挑戦日:2021/10/30 結果:解けた 時間:45分ぐらい 考えたこと 効率的な解法は特に思いつかないし、制約が小さいので全探索か? 再帰で全ルートを求める 公式解説 https://twitter.com/e869120/status/1407109731546636289/photo/…
問題 https://atcoder.jp/contests/typical90/tasks/typical90_br 挑戦結果 挑戦日:2021/10/29 結果:解けた 時間:10分 考えたこと X方向とY方向は独立して考えてOK。 発電所の左右にある工場数が同じあれば効率が良い。 工場の座標をソートして、中央にあ…
問題 atcoder.jp 挑戦結果 挑戦日:2021/10/29 結果:解けた 時間:15分 考えたこと 1ブロック目:Kパターン、 2ブロック目:K-1パターン、 3ブロック目以降:K-2パターン なので、これをかければ良い。modを取れば大きな数字ならないので、速度面も問題ない…
問題 atcoder.jp 挑戦結果 挑戦日:2021/10/28 結果:解けた 時間:20分 考えたこと 再現するだけ。 いったん10進法に戻して計算する。 コーナーケース(0のとき)で、WAを出した 実装はちょっと汚い気がした。 公式解説 https://twitter.com/e869120/status/1…
問題 atcoder.jp 挑戦結果 挑戦日:2021/10/27 結果:解けた 時間:1時間ぐらい 考えたこと 各区画の標高を持つのはTLE。 各クエリ時点での不便さを更新していくようなアルゴリズムでないと、計算量的に間に合わなそう 左隣の標高との差を保持するのが良いか…
問題 atcoder.jp 挑戦結果 挑戦日:2021/10/26 結果:解けた 時間: 1時間ぐらい 考えたこと DPとかを使うのかと思ったけど、 愚直にやればできそうな気がした。 8行分のどれを使うかは全パターン列挙しても256通り。 選択した行について、列が同じ数字にな…
問題 atcoder.jp 挑戦結果 挑戦日:2021/10/25 結果:解けた (でも、2,3問WAが出てデバッグに苦労した) 時間:1時間ぐらい 考えたこと ボタンAを押していく中で、過去に登場した数値が出てきたらあとは同じ。周期性を使って計算すれば良さそう。 公式解説 ht…
問題 atcoder.jp 挑戦結果 挑戦日:2021/10/21 結果:解けなかった(TLE) 時間:30分 考えたこと コンビネーションで全列挙は簡単にかけるけど、 ぐらいになって、TLEしそう。 でも高速な解法は思いつかないので、全列挙してみよう。TLEした。 解けなかった。…
問題 atcoder.jp 挑戦結果 挑戦日:2021/10/21 結果:解けた 時間:15分 考えたこと サイコロ2個の事例で計算してみていると、各サイコロの和をとって、それを掛けていけばOKと気がついた 公式解説 https://twitter.com/e869120/status/1398409831044632576…
問題 atcoder.jp 挑戦結果 挑戦日:2021/10/17 結果:解けた 時間:10分 考えたこと いかにもDP DP[n]をn段目にたどり着く方法とおいて、DP[n] から DP[n+1]とDP[n+L]に配ればOK。 最初、1段~L段上にすすめると勘違いしていたけど、そうではなくて1段orL段…
問題 atcoder.jp 挑戦結果 挑戦日:2021/10/17 結果:解けた 時間:20分ぐらい 考えたこと 各秒で貪欲に点数が一番多い問題(部分点 or 満点狙い)に取り組むのが良い。それを上手に実装すればよさそう。 部分点は最初にソートしておいて、上から順に取り出し…
問題 atcoder.jp 挑戦結果 挑戦日:2021/10/17 結果:解けた 時間:10分 考えたこと T1とT3はやるだけ。 T2は右シフトを愚直に実装するとTLEしそう。 なので、シフトに、クエリ数がだとでまずそう。 シフトの代わりに基準にする場所を持っておいて、T2のとき…
問題 atcoder.jp 挑戦結果 挑戦日:2021/10/17 結果:解けなかった 時間:1時間ぐらい 考えたこと 方向を変えた数なので、単純な最短経路ではなさそう。 といっても、QueueをもってBFSをやって、方向転換した数が少ないものから展開していけば良さそう なに…
問題 atcoder.jp 挑戦結果 挑戦日:2021/10/15 結果:解けなかった 時間:30分 考えたこと DPっぽい 一文字足して行く感じ 公式解説 https://twitter.com/e869120/status/1394423616805097477 解説を読んだふりかえり メモ化再帰で書いてみた 個人的にDPより…
問題 atcoder.jp 挑戦結果 挑戦日:2021/10/14 結果:解けた 時間:3分 考えたこと pythonに最大公約数のライブラリは入っていて、そこから最小公倍数も求められる。 最小公倍数のスニペットも以前作ったことあった気がするから、発掘。 公式解説 https://tw…
問題 https://atcoder.jp/contests/typical90/tasks/typical90_ah 挑戦結果 挑戦日:2021/10/08 結果:解けた 時間:30分ぐらい 考えたこと しゃくとり法のように構成すれば良さそう 現在見ている左部分(l)と右部分(r)の座標を保持する。 登場した数字の個数…
問題 https://atcoder.jp/contests/typical90/tasks/typical90_ag 挑戦結果 挑戦日:2021/10/08 結果:解けなかった 時間:20分 考えたこと 左上原点としたら、各2x2のマスの左上を点灯させるだけ 1行分を考えると$(W+1)//2$、1列分を考えると、$(H+1)//2$ …
問題 https://atcoder.jp/contests/typical90/tasks/typical90_af 挑戦結果 挑戦日:2021/10/07 結果:解けた 時間:20分ぐらい 考えたこと 全探索できそう。$10! = 3.6 * 106$ 順番の全列挙はpythonのライブラリにあったはず 公式解説 https://twitter.com/…
問題 https://atcoder.jp/contests/typical90/tasks/typical90_ab 挑戦結果 挑戦日:2021/10/07 結果:解けた 時間:30分ぐらい 考えたこと いもす法というやつで解けるのでは? はっきりとおぼえていなかったけど、縦と横で累積和を取るはず 公式解説 https…
問題 https://atcoder.jp/contests/typical90/tasks/typical90_aa 挑戦結果 挑戦日:2021/10/07 結果:解けた 時間:3分 考えたこと setに入れて、チェックするだけ 公式解説 https://twitter.com/e869120/status/1387901052683386880 解説を読んだふりかえ…