htkb-proconの日記

初心者がPythonで問題解いた記録

過去問

yukicoder No.751 Frac #2

No.751 Frac #2 - yukicoder 最初、問題の意図がつかめなかったが、括線の長さを見ると分子側は一番上から分母側は一番下から処理していくようだ。 分子側は 1 --- 2 ----- 3 ------- 4 の場合、(1/2)/3 = 1/6 → (1/6)/4 = 1/24のようにやり、分母側は 1 ---…

CODE THANKS FESTIVAL 2018 E - Union

E - Union 解説見てもDPの回し方にしばらく悩んだのでメモ。 dp[i][j] := 整数i-1まで余りなく処理したとき、iにj個持ち越した場合の数 って感じの流れは思いつけたんだけど、なーーーーんでか各iを1個残した場合と全部使い切って次に回す場合の場合分けって…

ARC014 C - 魂の還る場所

C - 魂の還る場所 Submission #3626930 - AtCoder Regular Contest 014 解法が思い浮かばなくて試しにビームサーチ解投げてみたら通ってしまって笑ったのでメモ。ただゲームのルール上筒の中に玉がたくさん詰まった状態で終盤から挽回するのは無理なので、不…

ABC054-D DP

D - Mixing Experiment DPやるだけの400点問題なんだけど今更こんなのでハマってしまったので忘れないように記す。 2種類の物質がa:bで混じっているc円の薬がN個あるので、これを好きなように混ぜてなるべく安く指定の比率を実現したいという問題で、制約も…

ABC041-D bitDP

D: 徒競走 - AtCoder Beginner Contest 041 | AtCoder この問題、解説見てもACコード見てもプロい人のブログとか見ても、お願いだから日本語書いて?って感じで困っていたのだけど、このブログの 感覚的には空集合の場合の数から全集合の場合の数へ、集合の…

Typical Contest 001-B, ARC032-B, ARC037-B UnionFind

B: Union Find - AtCoder Typical Contest 001 | AtCoder Submission #1294904 - AtCoder Typical Contest 001 | AtCoder UnionFindの実装が面倒そうで避けてたので練習として。データ構造としては配列一本持つだけでどのように操作するか/比較するかだった…

ABC012-D 最短経路問題

D - バスと避けられない運命 最短経路問題の練習をいくつかこなしていたら、ダイクストラを真っ当に実装したはずなのにめっちゃTLEが出るこの問題に遭遇。おかしいと思って解説を読むと、 •注意点 – 遅い言語では通りません! • Perl, Ruby, Pythonなど • 計…