こんばんは．tax_free です． 新居で椅子がない生活を2週間しています．椅子がないと，勉強と作業のモチベがあがらない... 東工大から配られた m.titech.ac.jp ドメインのメールを iPad の Gmail から見れるようにした話です． 細かい話は公式サイトを確認し…

令和4年度 東京工業大学 情報理工学院 総合型選抜に合格したので，そのレポートです．日本語が下手なのは許してくれ． 東京工業大学の総合型選抜 情報理工学院の総合型選抜 出願理由 志望理由書 活動実績報告書 共通テスト(某受験報告風) 第1段階選抜の結果…

お昼にあったJOIで散々な結果だったのでABCでリベンジしたかったが... A - ABC Preparation listで受けとって，min from sys import stdin input = stdin.readline l = list(map(int, input().strip().split())) print(min(l)) B - Smartphone Addiction バ…

はい．

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…

難易度5が前回で終わり，今回から難易度6に突入!!!!．思い込みの影響もあるかもしれないが，難易度5に比べると難しくなってるように感じる... E - おせんべい Rが小さいので縦のどこを操作するかで全探索する．横の操作の枚数は操作する行でのみ変化するので…