A問題 題意を勘違いしていて無駄に時間を使ってしまう。AC。コード。 ここまで4:48。 B問題 やるだけ。コード。 ここまで9:30。 C問題 場合分けがややこしそうだったので、最初に「Bで始まる&&Aで終わる」文字列を特別扱いして考えたらすんなりいってよかっ…

たまにやってます。 abc104 a - 1:00でAC。 b - 4:50でAC。 abc105 a - 0:50でAC。 b - 4:50でAC。 abc106 a - AC。 b - AC。 c - AC。 d - 解説を見ながら40分くらいでAC。想定解法をpythonで実装するとTLEになったので、二次元累積和を使う方法でやったら…

分割数の求め方。 def partitions(n): if n == 0: yield [] return for p in partitions(n-1): yield [1] + p if len(p) == 1 or (len(p) > 1 and p[0] < p[1]): yield [p[0] + 1] + p[1:] print(list(partitions(1))) # => [[1]] print(list(partitions(2))…

蟻本の2-5節を読んで最短経路を求める方法を学んだのでまとめです。 1 ベルマン・フォード法 ある一点から全ての点への最短距離を求める方法の一つ。辺一つ一つについて、辺の向き先の点へのスタート地点からの距離が短く更新できないかを何回も繰り返し見て…

UnionFind木、どういうものでどういう時に使うのかをなんとなく知ってただけで実装したことがなかった。abc097のD問題で実際に使うことになってpythonで実装したのでメモしておく。木の偏りをなくす工夫とかはしてないけど、要素の親だけでなく根からの深さ…

今日は蟻本でDPのところを読んでて、DPの練習がしたくなったので Educational DP Contestを解いてた。途中、完全に想定されてる解法なのにpythonだとTLEになり続けるので、きれて今後はc++を使っていくことにした。今日はc++に慣れるために、C問題までを出来…

abc096 a - 1:20でAC。 b - 1:30でAC。 c - 8:10でAC。 d - 解けずに諦めた。素数を小さい順に見ていって条件に合えば入れていく方針で計算量的に行けそうと思って解き始めると、55555以下の制限に引っかかってうまくいかない。解説見てなるほど…。こういう…

今日は、D問題がわからなくてもすぐ解説を見ずに頑張って考え続ける習慣を取り戻せたのでよかった。その分進みが悪いが...。最近ABCの過去問を埋め続けているが、C問題までは元からほぼ解けるしD問題は相変わらず解ける時は溶けるし解けない時は解けないので…

今日は響けユーフォニアムの映画を見にいったので少しだけ。今までずっとrubyで解いてたけど、今後のことを考えるとpythonの方が良さそうな気がしたので今日からpythonで解いてみる。本当に今後を考えると完全にc++の方が良さそうだが、これは困るまで置いて…

そこそこ時間が取れて、abc081から解いていった。過去に解いたことがある問題は飛ばしている。 abc081 c - 6:50でAC。 d - 解けずに諦めた。問題文を読み違えていて最小手順を求めなければいけないと思って完全に難しすぎると思っていたら、後から見たら手順…

ABC125に出たので反省します。 A問題 掛け算と割り算をして終わり。コード。 ここまで1:56。 B問題 配列を変換して足し上げて終わり。コード。 ここまで4:24。 C問題 とりあえずユークリッドの互除法を再帰的に使って云々すれば良いんだなと思ってやってみる…