D - Leaping Tak 1からNまでの移動する通りの数を求める． ただし，移動する際はK個の区間によって形成されたマスの数しか移動できない． [1,2] [5,6,7] [9,10]など． N は2*10**5以下． MOD ＝998244353 解） 愚直に全部足すとO(N**2)の計算量． Kの区間ご…

D - Friends ・友達の友達は友達 ・友達同士がいないように分ける場合，最低何グループ必要か 解） 最大の友達集合の大きさを求めればよい． Union Find 木構造が役に立つ． 実装： parent[] は大きさN，-1を初期値とし，parent[i]には i の根を格納． iが根…

D - Wizard in Maze 魔術師が迷路にいる． 上下左右に移動する，あるいはコスト1で自分を中心とした5×5のマスのどれかにワープすることができる． なるべく少ないワープ回数で移動したい． 解） ワープ回数0のエリア，1のエリア，…と分けていき，ゴールまで…

C - Repsept 解） 以下の漸化式を立てる． 鳩ノ巣原理より、高々 KK 項目までを計算すれば十分である． それはそう．

E - M's Solution N個の集落が効率よく通勤できるように鉄道を敷く． 解法： 愚直に全パターン計算しようとすると，(4**N) * (N**2) ． 事前にコストを計算しておくこと，縦と横を別々に分けることで (3**N) * N になる． 事前にX方向のみ路線を引いた場合，…

LinuxコマンドとWindowsコマンドの対応を忘れそうになるので復習．

D - Anything Goes to Zero popcount(n)をnを2進数表記した時の'1'の個数とする． n %= popcount(n)としたとき，nが0になる回数をf(n)とする． あるNについて，Nを二進数表記した後，一つの桁のビットを反転させたものについてf(n)を求めよ． 解法： 単純に…

C - Tsundoku 注意：numpyの dtype = int は 10 ** 9 以上だとオーバーフロー 通常のintは10**18まで大丈夫なのでこれで計算してappendする方がいい D - Sum of Divisors Nまでの約数の個数×数字の和を求めよ． for i =1, ....N: for j = 1, ....N: if i % j…

B - Judge Status Summary 正）AC x 10 誤）AC × 10 良い子のみんなはちゃんと文字を確認しような！ そもそもデフォルトの掛け算記号は＊なのだから気づくべき C - H and V H×Wの行列がある．列あるいは行を選んで塗りつぶすことで，#の数をK個にする． 方針…

D - .. (Double Dots) N本の部屋，M本の通路を持つ洞窟 洞窟内の各部屋から外に出るための最短ルートを進む際，次に向かうべき部屋を出力 達成できない部屋がある場合は"No"を出力 graph = [ for _ in range(N+1)] for a,b in zip(*[iter(AB)] * 2): graph[a…

大して成長していないのに周囲に指摘されなくなっていくのがつらい。 子供のころは周囲がああしろ，こうしろとうるさかった。失敗したらこってり絞られた。今思えば期待の裏返しであったと思う。 今はというと，失敗してもどうにも甘い。「まあしょうがない…

C - Skill Up N冊の本でM個のスキルをX以上にするための最小コストを求めたい 実装：深さ優先探索 def func(cost,a,i): if min(a) >= X: return cost elif i == N: return MAX total_A = [x+y for (x,y) in zip(a,A[i])] return min(func(cost + C[i],total_…

F - Strivore 「好きな英小文字 11 文字を好きな位置に挿入する」という操作を文字列 SS にちょうど KK 回繰り返してできる文字列は何通りあるでしょう？ 答えは非常に大きくなる可能性があるので、(109+7)(109+7) で割ったあまりを出力してください。 KK は…

D - Not Divisible 数列の中で，他の数に割られない数の個数を求める 全探索だとTLE ・解法 サイズ Amax の 配列 dpを作成，0で初期化 dp[Ai] = 0 の時，dp[Ai] += 1 Aiより大きいAiの倍数yについて，dp[y] = 2 にする これによりdp[Ai] == 1である数は一回…

E - This Message Will Self-Destruct in 5s 単純に全探索するとTLE j - i = Ai + Aj i + Ai = j - Ai Li = i + Ai, Ri = i - Ai とおくと，Li = Rj が求める条件 Li, Ri がそれぞれが取り得る値すべてを計算し，連想配列を使って一致するものを見つける 具…

C - Many Requirements A = {1,3,4} のとき A3 - A1 = 4- 1 = 3 = c1 O 100点入る A2 - A1 = 3- 1 = 2 = c1 O 10点入る A3 - A2 = 4- 3 = 1 ≠ c1 × 10点入る 計110点 解き方：条件を満たす数列を全探索 Ai = i 番目の仕切りより左側に存在するボールの数 + 1…

前半の浮動小数点の計算が合わない問題 C問題はdecimalを使うことで解けたけどBが合わない →なぜかすべての数が2より大きいと思ってN<59などという条件を付けくわえていた…雑なミス B - Multiplication 2 N個の数が与えられ，その積を求める問題。10^18を超…

Abstraction and Reasoning Challenge | Kaggle Jigsaw Multilingual Toxic Comment Classification | Kaggle Tweet Sentiment Extraction | Kaggle Prostate cANcer graDe Assessment (PANDA) Challenge | Kaggle ALASKA2 Image Steganalysis | Kaggle TReN…

C - gacha ガチャをN回引き，重複しなかったものの数を数える。 set()で重複を抜き，lenで数えた。 上位の回答を見ると，open(0)関数を使ってすべての入力を読み込み，冒頭のNの分の1回を引いている。 参考 qiita.com D - Multiple of 2019 20,0000文字以下…