B - いちご (Strawberry) 考えたこと とりあえず右端まで行くのが良さそうなので、右端から開始すると考えます。右端から地点0に向って進んでいきます。途中で、青いイチゴがあれば赤くなるまでその場で待機します。 n = int(input()) at = [list(map(int, i…

C - 桁和 (Digit Sum) 考えたこと N以下の全ての自然数を試そうとすると、きつそうなので別の方法を考えます。 考え方を逆にして、Nから1までの整数を調べてみることにします。を操作してNにできるなら、操作してiにできるような整数もNになります。(j→i→N) …

A - 碁石ならべ 考えたこと 石の状態をlistで管理します。配列に(石の色,連続する個数)のtupleを保存して操作します。問題文と同じく白は0、黒は1で保存します。 例:([(0, 2), (1, 2), (0, 3)])これは、0011000を表します まずは、iが偶数のときを考えます。…

F - 船旅 考えたこと 最短経路を求める問題なので、クエリに従って辺を追加して、dijkstraする。無向グラフなので、両方向に辺を追加する。 from heapq import heappush, heappop n, k = map(int,input().split()) info = [list(map(int,input().split())) f…

D - 星座探し 考えたこと 全探索するだけ。実行時間も10secもあるので雑な全探索でも耐えます。 disという配列に探したい星座の星間の距離を入れて、見えている全ての星に対してそれぞれ調べます。 m = int(input()) targets = [list(map(int,input().split(…

fiber - 光ファイバー (Fiber) 考えたこと グラフを連結して最終的に連結してるグループの数を考える問題。グラフについて色々調べてみると、UnionFindというのがあるらしいので使う。 PythonでのUnionFindから、いらない部分を削いで書きました。 class Uni…

building - ビルの飾り付け (Building) 考えたこと 前から貪欲に取っていけば大丈夫だと思っていたけど、それだとダメだったのでDPします。 ので初期化したdpテーブルを考えます。 [1:]]を

mall - ショッピングモール (Mall) 考えたこと ひとつずつコストの和を取っていると間に合わないので、うまく計算量を減らす必要があります。そこで、累積和を使います。私も初めて使いましたが、二次元累積和というものらしい。 m, n = map(int,input().spl…

factorial - 階乗 (Factorial) 考えたこと 素因数分解して、それぞれの素因数が丁度入るような数を探していって、条件を満たす数の最大値を取ります。 素因数が丁度入るような数は、前から見ていくと大きい素数が出てくると厳しいので、†二分探索†を使います…

C - 最古の遺跡 hatenaのtexが面倒なので画像を貼ります。 n = int(input()) xy = [tuple(map(int,input().split())) for _ in range(n)] set_xy = set(xy) ans = 0 for i in range(n): x1, y1 = xy[i][0], xy[i][1] for j in range(i+1,n): x2, y2 = xy[j][…

B - 最長の階段 考えたこと 白紙のカードが無い場合は連続した部分の最大を考える問題。 白紙のカードが入っている場合は入っていない場合を少し拡張して、[連続部分の長さ、連続部分列の最初の要素、連続部分列の最後の要素]を記録するlistを作って考える。…

考えたこと 一つでも不良品が含まれていると動作しないので、分からないものを調べるには3個中2個は正常なものでないといけない。なので、長さa+b+ca+b+cの配列を用意してそれぞれの商品を対応されて調べればよい。1回のループでは上から順に実験結果(入力の…

前回 一泊目 ベルリンから ルート 移動中はYouTube見たり、車窓を眺めていました。車窓 ベルリンから少し出ると田舎の風景になりました。 ワルシャワに到着 電車で6時間弱くらいかけて、Warszawa Centralna駅に到着! 駅の近くのビルがおしゃれ 上の建物はシ…