はい．

4 - JOIポスター (JOI Poster) 数学感がある問題．参考にした提出．細かい条件 from sys import stdin input = stdin.readline n, w, h = map(int, input().strip().split()) xy = [list(map(int, input().strip().split())) for _ in range(n)] ans = 0 for…

A - JOI紋章（JOI Emblem） 実装の面倒さで難易度6にいる．私は気合で場合分けしました() from sys import stdin input = stdin.readline m, n = map(int, input().strip().split()) flag = [input().strip() for _ in range(m)] crest = [input().strip() f…

B - IOI饅頭（IOI Manju） ]] := i番目の箱まで使えるときの，j個以上の饅頭を入れるために必要な金額の最小として，dpします．饅頭は高い方から売った方がいいので，降順でsortして，累積和を取っておきます． from sys import stdin input = stdin.readlin…

B - 古本屋 (Books) DPDPDPDPDPDPDPDPDPDP． DPで解く．ジャンルごとに売る本を決めるとき，同じジャンルの中で高いものから売った方が合計買取額は大きくなる．そこで，ジャンルごとに降順でsortし，買取ボーナスも含めた値段で累積和を取る．ジャンルの累…

anagram - アナグラム (Anagram) 計算自体は数学でも見る問題だが，実装が破滅したので，こちらを参考に from collections import Counter from math import factorial from sys import stdin input = stdin.readline s = list(input().strip()) def comb(x)…

D - JOI国のお散歩事情 (Walking in JOI Kingdom) それぞれの国民が他の国民と会い，おしゃべりを始める点を調べる．番目の国民をとする．が東向きに進むとき，よりも東にいて，に一番近い西に進む国民をとすると，十分な時間があれば，二人はとなる．ただし…

H - JOIOJI まず，各文字の個数で累積和を取る．それぞれの累積和をcsum_j, o ,i とする．区間(i, j)で J, O, I の個数が同じになるとき，csum_j[ j ] - csum_j[ i ] = csum_o[ j ] - csum_o[ i ] = csum_i[ j ] - csum[ i ]となる． 上式を， csum_j[ j ] -…

A - オレンジの出荷 (Oranges) DP．dp[i]を番目までのオレンジを詰めるための最小のcostとして，計算する． 参考にした記事オレンジの出荷 (Oranges) - ia7ck-competitive-programming from sys import stdin input = stdin.readline n, m, k = map(int, inp…

B - スタンプラリー ２ (Collecting Stamps 2) J は先端に，I は一番後ろに挿入したときに組み合わせは最大になる． O を挿入する場合を考えると，挿入した地点よりも前のJと後ろのIの積だけ増加することが分かります．これは累積和で計算できます． from sy…

A - フェーン現象 (Foehn Phenomena) 各地形変動が別々の事象だと誤読．地形を保存する方法が思いつかず終了． 場合分けでバグったせいで，inf時間かかった．参考にした提出 from sys import stdin input = stdin.readline n, q, s, t = map(int, input().st…

D - 日本沈没 (Japan Sinks) 解説と同じ考え方をしたが，になった．海面を上げていくときに，それぞれの要素の両隣調べる方法が分からなかった． それぞれの高さのindexをdictに記録して，海面を上げたときの島の増減を計算する．参考にした提出．このコード…

A - 長いだけのネクタイ (Just Long Neckties) 最初はDPと思っていたけど，sortして，順番に計算していけばよい．A，B のどちらも昇順でsortして前から順番に差を求めたときに"奇妙さが"が最小になる．最小値になるネクタイ以外を除いた場合は，もちろん最小…

B - JJOOII 2 (JJOOII 2) 全てのJから条件を満たす文字列を作るのに，どれだけの操作が必要かを考えればよい．それぞれの文字のi番目のindexが分かっていると早く計算できる．'O'，'I'の開始位置を二分探索で求める． 参考(コピペ)した記事 from bisect impo…

C - 夜店 (Night Market) 問題からDP感がでてる．時刻からまでのDP1，時刻からまでのDP1で解く． DP1[ i ][ j ] := お店 i まで調べて，時刻jまでに実現できる最大の楽しさの和． DP2は1と考えかたが逆で， DP2[ i ][ j ] := 時刻 j からお店 i ~ N を訪ずれ…

ひさしぶりの写経しました． E - イルミネーション (Illumination) 建物の中にあるイルミネーションしないマスをどうやって数えるかが分からなかった． 写した記事 from sys import stdin input = stdin.readline w, h = map(int, input().strip().split()) …

ioi - 国際情報オリンピック (IOI) 沼った．途中のACはちゃんと解いてないやつ． score = 与えられる各選手の得点 final_score = 自分以外の選手が残りの問題を完答したときの得点() を昇順でsort sort_score = 与えられる得点を昇順でsort limit_num = 金メ…

banner - 横断幕 (Banner) 愚直に計算すると組み合わせ数が爆発して死． そこで，4個の頂点のなかで，1個の頂点の色は自由に選べることに注目する．長方形から1つの頂点を取り除いた形で，他の3個の頂点の色が全て異なるような図形を考える．その図形はのこ…

stairs - 階段 (Stairs) 解法は思い浮んだけど，実装できず... ]を段目までの行きかたの場合の数，とすると，]はまで一回のジャンブで行ける範囲のの総和となる．の累積和を用意すれば，一回のジャンプでまで行くことができる範囲は二分探索で求めることがで…

C - つらら indexを付けて，最初のつららの高さでsortする．sortされたつららの配列から高い順に折れる時間を決定していく． n, l = map(int, input().split()) turara = [[int(input()), i] for i in range(n)] turara_s = sorted(turara, reverse = True) …

メモリが厳しい． nile - ナイルドットコム (Nile.Com) 問題文から溢れるDP臭．愚直なDPにするとになったから，うまく更新回数を減らす必要がある． そこで，日目に新しく行くお店(連続して買わないお店)は，前日の最も安い要素から移動することに注目する．…

解説AC E - 通勤経路 制約のせいで場合分けが面倒．どこから来て，今どこへ曲れるかを考えて実装する． w, h = map(int, input().split()) dp = [[[0]*4 for _ in range(w)] for _ in range(h)] for i in range(h): for j in range(w): if i == 0 and j == 0…

難易度6，初自力AC B - ピザ お店の住所の配列に，配達先の住所の要素を挿入する．ここで，お店の住所の配列がsortされているなら，二分探索で挿入先のindexを調べることができる．indexが分かったら，左右どちらのお店が近いかを調べる． from bisect impor…

解説AC． C - 連鎖 どこの色を変えるかを回調べて，それぞれで何連鎖するか計算します． from collections import Counter n = int(input()) p = [int(input()) for _ in range(n)] ans = n for i in range(n - 3): delete = p[i: i + 4] color, cnt = Count…

期末テストが終わりやっとJOIできると思ったら，あと一週間しかないこの頃． C - ダーツ めちゃくちゃ有名?な問題．半分全探索で解けます． from bisect import bisect_left n, m = map(int, input().split()) p = [int(input()) for _ in range(n)] one_thr…

こんばんは，tax_freeです．先週のABCは頭が痛くで参加できなかったので，二週間ぶりのABCでした(コード自体はJOI対策で書いていた)． A - Determinant 問題文の定義の通りに計算する. a, b = map(int, input().split()) c, d = map(int, input().split()) p…

A - JJOOII (JJOOII) 連続するJ，O，I を数える．JJOOOIIIのようなケースに気をつける． s = input() cnt_j, cnt_o, cnt_i = 0, 0, 0 ans = [0] for i in range(len(s)): if cnt_i != 0 and s[i] != 'I': cnt_j, cnt_o, cnt_i = 0, 0, 0 if s[i] == 'J': if …

A - 惑星探査 (Planetary Exploration) PythonだとTLE，PyPyだとMLEで死ぬので，C++で解く．許して．二次元累積和 #include <bits/stdc++.h> using namespace std; int main() { int m, n, k; cin >> m >> n >> k; vector<string> geo(m); vector<vector<int>> query(k, vector<int>(4)); for (int i </int></vector<int></string></bits/stdc++.h>…

B - 共通部分文字列 文字列sを前から1つずつ除いたものと文字列tを比べる，文字列tを前から1つずつ除いたものと文字列sを比べれば最大の共通部分が分かります． #include <bits/stdc++.h> using namespace std; int main() { string s1, s2; cin >> s1 >> s2; int l1, l2, c</bits/stdc++.h>…

D - パスタ (Pasta) bit全探索は厳しいので，DPを使ってとく．指定されたソースを使う日の処理，最後に10000で割ることに注意して実装する． n, k = map(int, input().split()) ab = [list(map(int, input().split())) for _ in range(k)] dp = [[0 for _ in…