tookunn’s diary

主に競技プログラミング関係

yukicoder

yukicoder long contest 1 stick xor

問題 No.5002 stick xor - yukicoder 考察 愚直にやって終わった感じでした。 愚直にやる以外は全然思いつかなかった。1ターン毎に現在の盤面から最も多く漆黒→純白に反転できる操作を盤面に適用していく。 操作対象となるセル(x,y)のx,yはランダムに決定し…

yukicoder No514 宝探し3

問題 http://yukicoder.me/problems/no/514 考察 座標と座標のマンハッタン距離はである。(とする) そこで、座標と座標のマンハッタン距離を考える。(y座標を求めるためにx座標を0に固定する) すると、となり、と出来る。これでは求まった。 あとはとな…

yukicoder No443 GCD of Permutation

問題 No.443 GCD of Permutation - yukicoder 考察 まず愚直に整数の各桁を並べ替えて出来る整数の集合を列挙することは制約から無理ということが分かる。ここから公式解説の解法について考える(自分に向けての補足)yukicoder Sに含まれる整数"xxxxab"と"xxx…

yukicoder No420 mod2漸化式

問題 No.420 mod2漸化式 - yukicoder 考察 ・まずは素直にを書き連ねてみる。 ・が奇数の時にになっていることに着目する。・つまり,を2進数で表現した時1が立っているビットの数がになる。・はまでなので、はまでしかないことが分かる。・を普通にからまで…

yukicoder No390 最長の数列

問題 No.390 最長の数列 - yukicoder やったこと まず最初に考えたのは「よい数列」というのはa[i] 再帰をしましたが、 計算量はO(N^2)であるので、TLEでした。 N = int(input()) x = sorted([int(i) for i in input().split()]) dp = [[-1 for j in range(N…

yukicoder No375 立方体のN等分 (1)

問題 No.375 立方体のN等分 (1) - yukicoder 考え 同じ方向からN - 1枚の平面で切断するのが最大なので、TMaxはN - 1下図のA方向からの平面の切断数をa、B方向はb、C方向はc、とすると TMinはa + b + cの最小の値となる。 なので、aの値を全探索をして、残…