ABCDの4完！Cのくだらない1ペナうわあああああ
3週間連続出られてる&上がってる！もうすこしで緑パフォだった。次こそは！
今回は反省点がしっかりある。特に…アクアパッツァについて……
A問題
問題概要
| 1 | 2 | 3 |
| 4 | 5 | 6 |
| 7 | 8 | 9 |
この内2つの数字がa, bとして与えられるので 左右に 隣接しているか判定してね
制約でa < bであることは保証されているよ
考察
- 隣だから
a + 1 == bかどうか、か - でも、aが右端の時だけはだめだな
コード
#入力 a, b = map(int, input().split()) if a + 1 == b and a % 3 != 0: print('Yes') else: print('No')
感想
ペナ率45.45%はすごくびっくりした
ABはやときで誤読しづらいの、速読できるからと、テキストコミュニケーションに慣れているから…？
本番では条件を if a == 3 or a == 6 or a == 9: って書きながら「あ…余剰で書いた方がはや…い…まあ…いいか…」と突き進んだのがよい思い出
B問題
問題概要
1と0からなるN × Nのグリッドの、外側だけを時計回りに1ずらして回転して出力してね
考察
- 賢く解くのは無理なので、時間かけていいからしっかりと条件を整理しよう
- 真ん中のことは考えなくてよいので
i = 0j = 0i = n - 1j = n - 1のそれぞれについて条件を整理 i = 0：1行目のj = 0： 1列目は、1行下を出力- それ以外は、1列前（左側）を出力
i = n - 1：最終行のj = n - 1：最終列は、1行上を出力- それ以外は、1列後（右側）を出力
j = 0：それ以外の1列目は、1行下を出力j = n - 1：それ以外の最終列は、1行前を出力- それ以外は、内側なので、そのまま出力
コード
#入力 n = int(input()) # 文字列で受け取る g = [input() for _ in range(n)] for i in range(n): # 1行分を格納する文字列 inner = '' # 列のループを回し、各条件チェック for j in range(n): if i == 0: if j == 0: inner += g[i + 1][j] else: inner += g[i][j - 1] elif i == n - 1: if j == n - 1: inner += g[i - 1][j] else: inner += g[i][j + 1] elif j == 0: inner += g[i + 1][j] elif j == n - 1: inner += g[i - 1][j] else: inner += g[i][j] # 1行分のループが終わったら出力 print(inner)
感想
条件整理をコードで書いてしまって時間かかった（なぜ）
書き写すときに気付いて修正するの手間だったので、次から日本語でやる
賢く解くのではなく、丁寧な場合わけをしたの、すごくえらい
N <= 100 でも文字列追加はこわくてPython3で投げるのも とてもえらい
C問題
問題概要
お薬いっぱい（N種類）処方されたよ…今日から飲んでいくよ…
それぞれのお薬について、今日からA日間、B錠飲むよ。
1日に飲む量がK錠以下になる日を知りたいよ…健康イズ大事
考察
- めっちゃ飲むやん
- とりあえず表にまとめてみた。日数が経つごとに、絶対に薬は減っていく。よい
- A日目は言い換えると「量が減る前日」なので、K錠以下になる「X日目」はA + 1日目になる
- 例外として、1日目で既にK錠以下だった場合は、1日目だよ〜を吐いて終了
- ソートしてもOKだなあ
- Bを全て合計したものから、各Bを引いていけば、K錠以下になるタイミングが掴めそう
コード
#入力 n, k = map(int, input().split()) d = [] # bの合計値 1日目に飲む全ての量 s = 0 for _ in range(n): a, b = map(int, input().split()) s += b d.append([a, b]) # 日数と錠数を、日数を基準にソート d.sort() # 初日（全てを飲む日）k錠以下だったら、1日目で達成 if s <= k: exit(print(1)) for i in range(n): # 全体の合計から、各日の錠数を減らしたあと s -= d[i][1] # k錠以下だったら、翌日に達成 if s <= k: exit(print(d[i][0] + 1))
感想
「1日目で減ったときK以下になった場合は、2日目に達成、が例外だな」という謎理論をかまし、その場合の出力を2と設定し1ペナ
「何日間続けて飲むか」の最小が1であることなど保証されていないので…
速攻気付けたのえらいけど、しょーもなさすぎた。条件整理をもう少し俯瞰する必要がある
D問題
問題概要
分かれた状態になっている2つのグラフが与えられる。
2つを繋げ、頂点番号1〜最後から辿る際、辺をたくさん通りたい。
最適な繋ぎ方をしたら、最大でいくつの辺を通れるだろうか。
考察
- 制約をめちゃくちゃ見る（えらい）そしてありとあらゆるパターンを描く（えらい）
- グラフ①の1〜最後の頂点と、グラフ②の最後〜最初の頂点の 最大の距離 を調べ、合計し、繋げる辺としてさらに +1 してあげるとよさそう
- （冷蔵庫にしまい忘れたアクアパッツァが目に入る おいしそう…ぱくぱくもぐもぐ！8分経過）
- ふう！まんぞく！どうせDは時間かかるからな！さて本気出すぞ〜BFSの関数をいじるとよさそう
- （コピペにて瞬殺 あれ？）
コード
# BFSで使用するqueのインポート import collections # 入力 n1, n2, m = map(int, input().split()) g = [[] for _ in range(n1 + n2)] # 隣接リストを作り、どこがどこと繋がっているのかを保管 # （0-indexedなので、以後全て-1） for _ in range(m): a, b = map(int,input().split()) g[a - 1].append(b - 1) g[b - 1].append(a - 1) # xからyへの距離を測るBFS def bfs_dist(x, y): d = [-1 for _ in range(y)] max_d = 0 que = collections.deque() que.append(x) d[x] = 0 while que: p = que.popleft() z = d[p] + 1 for i in g[p]: if d[i] != -1: continue que.append(i) d[i] = z max_d = max(max_d, z) return max_d # グラフ①0 〜 n1までと、グラフ②n1 + n2 - 1から他頂点までの最大距離 + 1 # グラフ②について、最大のループ数を確保したいのでyがn1 + n2になっているが、結局グラフ②が保持している頂点だけを見るのでOK print(bfs_dist(0, n1) + bfs_dist(n1 + n2 - 1, n1 + n2) + 1)
感想
テストケース、めちゃ多くてどきどきした
考察をしっかりしたもの、ちゃんと1発で通るんだなあ（それはそう）
アクアパッツァぱくぱくタイムがなかったら8分くらいははやかった…
来週のburiodenは
録音したCDがディスクユニオン各店頭に並ぶので、ありがとうよろしくお願いします！する旅をした後、たぶん路上ライブして、ABCに出るぞい
今週中に灰diffを埋めて、茶diffしか解けない世界線に自分を強制連行したい所存
