典型90問

Atcoder 典型90問 076★3[二分探索][累積和]

■要約  問題の流れは理解していたが,実装が難しかったことと,二分探索で条件を満たすRを見つけるという考え方が浮かばなかった.確かに二分探索ならO(logN)で見つけることができるので,こういう使い方もできるかのと勉強になった.  簡単に問題を解く流れを書くと以下のよう. ①連続するピースを表せるように,ケーキ2周分に配列を拡張する.▶ N番目から数える連続するケーキの組み合わせを表現できる ②累積和Bを求める. ③Br - Bl = Bn/10 となるrを探す旅に

Atcoder典型90問 069★3[繰り返し2乗法]

■要約 N=1以外の時は,総数がK*(K-1)*(K-2)^(N-2)になることはすぐに分かったが,累乗の計算量はO(N)なのでどうしようかと考えていた.調べたら,繰り返し2乗法というものがあり,計算量をO(logN)に減らせる. 説明は他の方々がとてもわかり易いものを記載しているので割愛する. pythonだとわざわざ実装しなくても pow(x,y,n)でx^yをnで割ったあまりをO(logN)で計算してくれるらしい.鬼便利 N, K = map(int, inp

Atcoder 典型90問032 - AtCoder Ekiden(★3)[順列全探索][配列で隣接を評価]

■要約  正直★3の中では今まで解いてきた問題で一番複雑だった.解き方はすぐに思いついた.Nがとても小さいので,①各区間の走り方の全パターンを考えて,②それぞれに対して噂話を評価して,区間にかかる時間を更新していけばよいと考えた.①については,pythonでは num = list(range(N))ptn = list(itertools.permutations(num)) のようにすれば,順列の各パターンを配列として作ってくれるので簡単である.(bit全探索のと

Atcoder典型90問027(★2)[in][listとset]

■要約  解き方はすぐに思いついた.でてきた単語をリストに入れていって毎回の入力で得た単語がそのリストの中に入っているか確かめていけば良いと考えた.しかし,pythonではlist型におけるinの平均計算量はO(N)のため,毎回のループでこれを行うとO(N^2)の計算量が必要になりTLEとなってしまう.これを防ぐ方法は案外簡単で,set型を用いればよい.setは同じ値の重複を許さないような型なので,inの平均計算量がO(1)で済む.素晴らしい. N = int(input

スキ
1

ABC 典型90問 010(★2)[累積和]

■要約  生徒は2クラスあって,各クラスのある区間のテストの点数の和を求める問題.まず,①各生徒のテストの点数の保持の仕方に工夫がいる.最初は辞書とかがいいのかと思ったがいつか解いた問題で使った,N個の長さの配列を2つ用意してi番目に得点を代入すればよいことが思いついた.次にQ個のクエリについて,毎回指定範囲の和を求めると計算量がO(NQ)でTLEしてしまうことに気がついた.今回はある区間の総和を求めればよいので②累積和を使うことに気がついた.コードは少し冗長になったが以下

スキ
1

Atcoder典型90問 007(★3)[二分探索]

■要約  問題文通り考えるとQ人の生徒について,N個のクラスを考えないといけないのでO(NQ) = 10^10でだめなことが分かる.そこで今自分が使えるアルゴリズムを考えると,bit全探索/二分探索/累積和ぐらいであり,これらが使えないか考えた.すると,今回の問題は,全部の差を考えるんじゃなくて,生徒Bのレーティングが,クラスのレーティング配列Aのどの値に近ければわかればいいので,配列Aをソートして,何番目にbのレーティングが含まれればいいか分かれば,その左右の絶対知を計算

Atcoder 典型90問004-★2[前処理][配列処理]

■誤解答 方針自体はすぐに思いついた.求めたい場所に対して縦と横の総和からその場所の値を引けば良いと考え実装.この際,行列の縦と横の総和の取り方が分からず迷う.縦の総和はlistで行けるが,横の総和はnpにしないとsum関数を使って上手くできない. import numpy as npH, W = map(int, input().split())ans = 0a = [list(map(int, input().split())) for l in range(H)]a

典型90問002[bit全探索][カッコ列]

 大変お久しぶりです.死ぬほど忙しかった修士1年の前期が終わり余裕が出来たので久々に競プロを再開して行きたいと思います.M1前期は就活や授業,研究,学会とてんこもりでしたのでまた機会があったら振り替えっていきたいと思います.  友人(tukasくん)に過去問もいいけど典型90問も良いよと進められたのでしばらくは★3以下を解いて入茶を目指していきます. ■方針 "("と")"の2パターンの並び替えなのでbit全探索を用いることには気づけましたが,カッコ列の正誤判定がわから