NOMURA プログラミングコンテスト 2020 A,B,C の3完 ABC170 A,B,C,D の4完でした。 土曜日の方はまずまず。C は直ぐセグ木じゃん楽勝と思った割に、実装をバグらせまくり時間をロスしすぎました。いもす法は知らなかったので、セグ木で毎回リスト A をみて 1…

AGC に備えてAGCの緑 diff を８問くらい解いた。 印象としては気づくかどうか系が半分くらいで正答率も半分くらいだった。 数え上げ問題が多く、やたら Counter 使っている気がする。 一番大事なのは問題の題意をちゃんとと把握することだと感じた。 これは…

abc で冷えた後なのでこういう問題は冷静に瞬殺できる。 明らかに全探索するわけがなく、数学的要素が強そうなので素晴らしい。 x,y に至るまで (+1,+2) を i 回、(+2,+1) を j 回したとすると、 x = i + 2*j, y = 2*i + j となって 答えが０でないためには …

３完。負け。いつも愚直に全探索するだけの問題を難しく考えすぎてそこで詰まる。 全探索するかとは一回は思うのだけど、今いち全探索しても間に合う制約なのかどうかが全く分からず結局他の方法を考える→時間切れみたいになっている。 Dも最初から因数分解…

C - Align数列を並び替えて隣り合う２数の差の最大値を求める問題。 直観的に一番小さいものと一番大きいものが隣り合うように、出来るだけ真ん中に置くように並べるのがいいと予想できるが、単にそれを実装するのではなく、 隣り合う２数の差 = 大きいもの…

今回の反省と学び 19C10 ≒ 46000 くらいの全探索が通ること。（総数が19C10 なのは分かっていた） 重複組み合わせの itertools が用意されていること。 itertools 使うときは順列の要素がデフォルト時は 0 から始まるので注意 次は5完する。 import sys inpu…

文字列 s から作られる部分列の中で辞書順で k 番目に小さいものを求める問題。 k import sys input = sys.stdin.readline s = input().rstrip() l = len(s) k = int(input()) chk = set() for i in range(26): for j in range(l): if s[j] == chr(i+97): fo…

10**5までの素数のリストをどう作るのが早いかという話。 とりあえず python 素数判定 高速 でググってこれをコピペしてみた。ミラーテストというらしい。 Pythonを使って高速素数判定をしてみる - Pashango’s Blog k = 13 のときで 1700ms だった。 4**13分…

C - Next Letter 先頭から a に変えれそうなら a に変える、最後尾までみたときにまだ k が残っているなら k が０になるまで最後尾の文字を変える s[ i ] を ' a ' にするときに毎回 s = s [ : i ] + ' a ' + s [ i + 1 : ] としているのは何とかならないの…

D - HarlequinAtCorder Problems でおすすめされていたので解いた 実験していくうちに、A1,A2,..,A(n-1),An と A1,A2,...,A(n-1),An+2 A1,A2,..,A(n-1),An,２ との勝者が同じではと気づいた よってA の中に奇数が一つでもあれば first になり、すべて奇数な…

A の小さいものを Ci のうち一番大きいものに変えていくのが一番大きくなるなあと考えた。 大きいものから変えていくので、N枚変える or Aの最小値が現在の Ci 以上になったらそこで終了してよい。 最小値を取り出すのを heapq で高速化 値の変更がなくても …

最近緑diff をすんなり解けるようになって成長を感じる。上達というよりは緑diff 程度の問題なら考えることはこのくらいかな～みたいな頭の動かし方に慣れてきたんだと思う。今回は数列の隣り合う２数の正負を好きなようにして最大値を求める問題。 負の数が…

直観的に一回の動作で、１と１との間にある０を全て１にする、 次の動作では、前１にしたところより１つ右にある０の塊を全て１にする… という動作をｋ回繰り返したものの中から連続して１が並ぶ最大値が作れるとわかる Sのなかに０が連続していくつあるか、…

i = 1 ~ 2**10-1 まで bit 全探索する問題。 与えられた F を 2 進数としてみると、i ＆ F =１となっている桁の個数でどの P になるかが決まる。 '10' をそのまま 2 進数として扱いたいときは int( '10', 2 ) としてやる。 （ print すると 10 進数表記の 2 …

maspy さんの解説をひたすら読んだ [AtCoder 参加感想] 2019/12/08:ABC 147 | maspyのHP XOR関連の共通した着目点は、各桁ごとのbit 演算は独立して計算できるということ i を2進数表示したときの n 桁目は ( i >> n ) & 1 で表せる ある桁のXORのｎ個の総和…

ダイクストラ法の問題 この問題は道路を片方向にしか通れないので、１からｋまでの最短路とｋから1までの最短路は別に求める必要がある。 import sys input = sys.stdin.readline n,m,t = map(int,input().split()) a = list(map(int,input().split())) a = …

素直に問題文を言いかえせずに解いたら解けるという変わったパターンだった。 制約が最大５０＊５０なことを重視するべきだった。 辺を一つ減らして毎回 Union-find をして一つの木でなかったら (大きさが N でなかったら）ans += 1 するという方針 n, m = m…

ほかっておいた蟻本の2-5章を進め始めた 蟻本がC+で書かれていても、先人の方々が python のコードをまとめてくださっているので独学でもなんとか耐えている 神サイト 蟻本 初級編 python カテゴリーの記事一覧 - じゅっぴーダイアリー今回はワーシャルフロ…

a から b までのXORの累乗和を計算する問題 1から１５までのXORの累乗和を順に求めていくと、 １、１１、０、１００、１、１１１、０、１０００、１、１０１１、０、 １１００、１、１１１１、０ となっていき、3 (mod4)のときに０になることがわかる また、…

https://qiita.com/saba/items/affc94740aff117d2ca9コードはこれを参考にしましたこれもとりあえず辺のリストを作成 ループがあることをどう表現するかがポイント 一周したというのを、「一回見た頂点に戻ってきた」と置き換えると memo = [True]*n で一回…

辺がn-1本あるので、すべての頂点が一つの木を構成しているとわかる。辺のリストを管理するには、 for i in range(n-1): u, v = map(int, input().split()) u -= 1 v -= 1 g[u].append(v) g[v].append(u) としてやればよく、辺を全て全探索するには、 def df…