問題ページ atcoder.jp 愚直に考えると、0~N-1の範囲で、部分文字列の左端と右端を選んで、その部分文字列が P で割り切れるか、全ての(左端、右端)の組で判定する。計算量はO(N^2)で、N <= 2*10^5 より間に合わない。 計算量をO(N)程度に落としたい。S=1234…

難しかった。 [ポイント] ・123456789みたいな数字について、12345 = (123456789 - 6789) / 10**4 の発想 - これめっちゃ頭いいと思った - 累積和ではないけど累積和風味の発想がおもしろい ・余りの問題は、計算過程から余りをとっておくと高速化できてよい…

Dまでの4完だったが、Dを解くのに時間をかけすぎた。 反省するべき点はあるけれど、実装力と論理的思考力はそこそこの水準になってきていると思っているので、うっかりミスとかを減らしていくことでどこかで飛躍的にパフォをあげられる気もする。また、Dは時…

以前解いたときは、i番目までのカードの中からｊ枚カードを選択するとして、i番目をj枚目として選ぶときに合計がj*AになるものをDPで数え上げた。が、このやり方だと３次元配列になってややこしいので２次元で何とかしたかった。 prd_xxxさんの解答が行数少…

問題は人のグラフを言語のグラフ（辺？）を使って全員をつなげるか、みたいな感じでUnionFindですべて同じUnionにできるかどうかなどで判断できると考えた。 今回は愚直に人を言語の辺でつないでいった。最初はdequeを使っていたが、dequeを使っても何度も何…

その時最大の値を //2 すればいいよね→とすると計算量がO(NM)で解けなくね？ っとなって死んだ。 毎回最大や最小の値が必要な場合、優先度付きキュー（pythonだとheapq）があるのでこれを使えばいいことが分かっていれば瞬殺できる問題だった。 heapqは子が…

最近300~500点問題でDificultyが1000~ぐらいの問題を一日2問解くみたいなチャレンジをやっていて、毎日学びがある。python高速化周りの記事を書こうかなとも思ったのだけど、タイトルの問題で結構感動したのでこの問題について記録しておく。 最初の提出はこ…

お菓子の個数の累積和をとっておいて、lとrを動かして、累積和の差分のmod Mが０になるなら、均等にお菓子を分けられるのは気が付いたので愚直に2重forループでやってTLE。データ数的にTLEになるのは分かっていたけど atcoder.jp で、そこからうまいこと計算…

本番では解けなかったので解説見て解いた。優先度付きキューはほとんど触ったことないので発想になかった。別解の方はなるほどわからんなのでそのうち理解したい。 覚えて置きたい所 ・制限の厳しいものから選んでいくと見通しが立ちやすい（今回は残り支払…

Cまでの3完。Cは最初深さ優先で解いてTLEでたのでDPに変えた。ただ、N＝１，２のを考慮に入れておらず、それに気づかなかったため、何度もREを出した。 発想力と実装力は以前よりよくなってきたと思うが、細部に気を払えるように頑張りたい。特に今回は１，…

問題的には→と↓の並べ方をnCrで求める問題なのだが、制限的にオーバーフローを起こすので回避する方法を調べた。 こちらのページのJavaのコードをpython化して回答した。 手法としては、分子と分母の積算の数値をリストの中に入れておいて、割れる部分を先に…

今日はあまり問題解けてないけど眠いから感想書いて寝る 考えたこと N=５０だから組み合わせは2^50なので全探索は絶対終わらない。部分点もらえるので深さ優先でとりあえずやってみる。 部分点はもらえた。一方で全探索しない方法を全く思いつかない。合計が…

ここ一か月でABC35~120のC問題に挑戦して４５からは自力で解けたか解説を見たかが残してあるので自力で解けてないものについて再挑戦する。 考えたこと 文字列は長さが１０までなので、数字の間に＋を入れるか入れないかで2^9通りなので、全パターン試して十…

再帰的な処理は多少かけるが、深さ優先探索を実装することがうまくできないことが多いので、すこしまとめてみた。 どんな時に使えるのか 「ある物/配列要素に対し操作1,2,3...のいずれかを行う（選ぶ/選ばないなど）」のパターン全列挙 いくつかの文字の中か…

自分で書いたときは、与えられたhをリストに格納し、左から０でない部分を探し設問のlに、次いでlから右に向かって一番初めに見つかった0の手前を設問のrとして、[l:r+1]の範囲で最小の値を見つけ、h[l:r+1]からその値を減算すると同時にansに最小値を加算す…

自力では解けなかったのでカンニングした。 考えたこと 375とか537とかの753数の頭に3,7,5のどれかを付け足すと簡単にできそう。 いや、3557も753数。ベースとなる数字が753数とは限らない。 とりあえず3,5,7を適当に並べた数字を作るか。でもその方法が分か…

完敗。 C問題 連立方程式を解く感じかと思い込んだため、解けなかった。中心座標がそれぞれ１以上１００以下なので、全組み合わせについて試せるのは盲点だった。 D問題 探索範囲がM**0.5までで問題ないのを思いつかなかったため、TLEを抜け出せなかった。 …

考えたこと 偶数部分と奇数部分に分けて最頻値を取り出すとこまではすぐに思いついた。書き換えた後に両方とも同じ値になる場合をおもいつかず少し手間取った。 そのあと、同じ値になってしまった場合に偶数部分と奇数部分のどちらの書き換え先を変えるべき…

組み合わせの公式は覚えていたが、重複組み合わせの公式は完全に忘れてた。解き方はすぐに思いついたが重複組み合わせのせいでもたついた。 組み合わせ nCk = n!/((n-k)! k!) 重複組み合わせ 今回の問題の文脈でいうと、x個の数字oをn個のリストのマス目の中…

二時間近くかかった。 考えたことと試みたこと ある文字からある文字への変換表を辞書形式で保持しておいて一対一の対応になるか調べたらいけるやんと思う。 はじめは文字列Sのi番目とTのi番目が一致しないときだけ辞書に入れて、文字列S全体について変換表…

考えたこと ・初期地点も都市として扱い、都市のリストに追加。それらを位置でソートする。 ・両端の都市の距離を用いて二分探索で隣り合う都市間の距離を割った余りが０になるように設定するとよいのでは？二分探索（O(logN)）と各都市間距離を見ていく（O(…

リストのコピーはコストが少なくともコピーする要素分かかる。 リストのコピーを作るのは、リストをいじる必要がある場合かつ、コピー＆いじる操作を含めて時間内に処理が終わる程度のデータ数に対してのみ。それ以外はいのす法みたいに最後にまとめて処理す…

AB2だけAC、CはTLE、Dはそもそも見てない。 ◆Cについて ・「一つを好きな値に変える＝取り除く」までは分かったので、残りに対して二分探索で最大公約数を求めようとしたがTLEから抜けられなかった。選んだ要素の左右の配列について最大公約数を求め、両者の…

四月頭から参加＆過去問解き始めて３５～１００番までABC-C問題に挑戦したけど、なんか少ない。 とおもったらARCのAに反映されてた。

ABC１２３からAtCoderを始めた。Cまで解けたがコンテスト参加回数が少ないとランクが著しく低く出るということで、現在は灰色（最低）ランクだ。 過去問もちょこちょこ解いてみたりしている。 A,Bは基本的に解けるが、Cは解けないもののほうが多い。Dはわか…