AtCoder Regular Contest 106 振り返り
結果
3完40分+1ペナ。パフォ1757でした。
Dが解けなかったのがかなり悔しいです。
| A | B | C | D | E | F |
|---|---|---|---|---|---|
| 2:02 | 11:03 | 40:36(1) | (2) | - | - |
問題
B - Values
問題概要
各頂点が値を持っていて、辺で繋がっている頂点に値を1渡すor1もらう操作を繰り返す。初期状態Aから状態Bにできるか答えよ。
感想
各連結成分で値の和が等しければOK。UnionFindに変な改造を施して値の和を管理できるようにした。
C - Solutions
感想
構築問題。区間スケジューリングの正しい解法と嘘解法で答えの差がちょうどMになるものを答える。
高橋くんの方法が区間スケジューリングの最適解だと気づけば、M<0にならないことがわかる。
D - Powers
感想
うーん、悔しい。二項展開したあたりでかなり近い式は出ていたのですが、最初に複雑な解き方を選んだために途中で値が狂ってしまった。
「重複を許して%%(i, j)%%についての総和 → 2×(重複のない%%(i, j)%%のペアについての総和) + %%(i, i)%%についての総和」という言い換えがすぐに浮かべばもう少しシンプルに考察を進められた気がします。
実力不足がよく表れた感じです。
追記→2で割る操作をして壊れていただけだった。逆元を掛ける。だいじ。
AtCoder Beginner Contest 180 振り返り
結果
ABCDEの5完でパフォ2307。初の黄パフォです！
EFの間に大きめの壁があったおかげで早解きがパフォーマンスに直結しました。
Eは巡回セールスマン問題ほぼそのままの問題で、過去の提出コードをコピペして提出しました（汗
| A | B | C | D | E | F |
|---|---|---|---|---|---|
| 0:21 | 1:26 | 2:39 | 7:34 | 20:39 | - |
問題
C - Cream puff
問題概要
約数を昇順に出力する。
感想
問題文を読まずに入力例2を見て約数列挙をコピペしました。
練習のときはちゃんと書いてるので、本番コピペは許されます（は？
D Takahashi Unevolved
問題概要
整数が与えられる。A倍する or Bを足すの操作を行うことができるが、整数がY以上になったらそこで終了。最大何回操作を行うことができるか。
感想
読解に少し手間取りました。Bを足してからA倍するより、A倍してからBを足すほうが操作回数は多くなるので、最初に何回A倍するかを全探索。
後半でBを連打するので実質Bボタンキャンセル。
E - Traveling Salesman among Aerial Cities
問題概要
巡回セールスマン問題。典型との違いは、1つの都市に複数回立ち寄ることができる点。
ただし、移動コストがマンハッタン距離のような形で与えられ、三角不等式が成り立つので同じ都市に複数回立ち寄る必要はない。
感想
コピペゲーでした。すみません…。
F - Unbranched
問題概要
N頂点M辺のグラフ(単純とも連結とも限らない)で、次の上限を満たすものの個数を答えよ。
- 自己ループを持たない
- すべての頂点の次数が2以下
- 各連結成分の大きさの最大値がちょうどL
感想
時間はあったものの、ほとんど考察が進みませんでした。
考察のステップ一つ一つが未履修という感じで、現時点での実力では解けそうになかったです。
いかにも教育的な問題という気がするので、しっかり復習しておきます。
考察ステップ
頂点の次数が2 → パス or サイクルの言い換え
最大値がちょうど%%L%%の場合の数 → %%f(x) =%% 最大値がx以下の場合の数として、 %%f(L) - f(L - 1)%% を求める
重複なく数え上げるために、ラベルの最も若い頂点を固定する
%%dp[n][m]%%: %%n%%頂点%%m%%辺のグラフのうち連結成分の大きさの最大値が%%L%%以下であるものの数
コンテスト後の提出コード
Educational Codeforces Round 96 (Rated for Div. 2) 参加記録
結果
| A | B | C | D | E | F | G |
|---|---|---|---|---|---|---|
| 00:04 | 00:07 | 00:21 | 00:30 | 00:54 | - | - |
5完。Div.2 rated内45位。あったまり。
感想
C - Numbers on Whiteboard
問題概要
1～Nまでの数字がある。2個選んで取り除き、その平均値（小数点以下切り上げ）を新たに追加する。数字が1つだけになったとき、その数字の最小値を求め、そのような数字の選び方を1つ答えよ。
考え方
切り上げ云々はさておき、平均を最小にする戦略を考える。
2つの数字aとbを選んで、その平均をxとする。次に、xと別の数字cを選んでその平均を新たなxとする。これを繰り返していくと、後に選んだ数字ほどxの値に影響するので、大きい数字から順に使っていけば良い。
感想
切り上げに惑わされて時間を使った。完全二分木のような形で計算していく方法を考えてしまった。
D - String Deletion
問題概要
0と1からなる文字列が与えられる。次の操作を行うことができる回数の最大値を求めよ。
操作:
- 1文字選んで削除する。
- 先頭から同じ文字が続いている範囲をすべて削除する。
ただし、1と2は必ず両方行う。また、必ずこの順に行う。
考え方
圧縮する。11101001 → [3, 1, 1, 2, 1]。圧縮後のリストを%%L%%とする。
すると、操作は「%%L%%の要素を1つ選んで1減らしたのち、先頭の要素を削除する」と読み替えることができる。
1減らす要素を選ぶときは「連続で同じ文字が並んでいるところ、かつ、なるべく先頭に近いところ」から選びたい。
毎回%%O(N)%%で線形探索するわけにはいかないので、少し工夫する。
現在減らそうとしている要素の位置を変数に保持しておいて、要素の値が1になるか、削除済みになった場合に次の位置を探しに行くという方針がシンプルか。
%%L%%の要素がすべて1になったら、あとは先頭から2個ずつ削除していく（最大%%\left\lceil \frac{|L|}{2} \right\rceil%%回操作できる）。
感想
Hackしていて気づいたけど、もう少しオシャレなやり方があるみたい。
最大%%\left\lceil \frac{|L|}{2} \right\rceil%%回操作を行うことができる。
%%L%%の要素を先頭から順に見ていって、どれだけ無駄に削除する必要があるかを見ていくと、うまくいく。
E - String Reversal
問題概要
文字列を反転させたい。隣同士の文字をswapする操作の回数が最低何回で達成できるか。
codeforces -> secrofedoc
考え方
隣同士のswapという操作からいかにも転倒数を使って考えたくなる。問題をソートに帰着すれば解けそう。
上の例の場合、反転後の文字列を0123456789と置き換え、それがもとの文字列に対応させることで、転倒数を使って解くことができる。
すべての文字が1回しか出てこない場合はただ数列を反転するだけだが、同じ種類の文字が存在する場合はもっと効率の良い操作がある。
すなわち、同じ種類の文字について、反転前後で各文字の順序は変えずに対応させる。
2471583960 codeforces -> 0123456789 secrofedoc
これを実現するには、'a'から'z'までそれぞれの文字の位置を記録したリストを持っておく。
各文字種cに対して、左からi番目の出現位置idx[i]を反転した位置N-1-idx[i]を、右からi番目にあるcの反転後の位置に対応付ける。
あとは転倒数を求める。
感想
自作のライブラリをしょっちゅう書き換えるので、正しい出力が得られないときにBITのバグを疑ってしまった。
F - Realistic Gameplay
解けず！ 途中でお腹痛くなって離脱しちゃった。考えてみる！
不調になったらやること(競プロ編)
寝る
睡眠に優るものなし。
区間DP
連鎖行列積
import sys input = sys.stdin.buffer.readline N = int(input()) *A, = map(int, sys.stdin.buffer.read().split()) A = [A[0]] + A[1::2] INF = 1 << 30 dp = [[INF]*N for _ in [0]*N] # [l, r]まで積を取ったときの最小乗算回数 for i in range(N): dp[i][i] = 0 for length in range(1, N): # 区間を徐々に広げていく for l in range(N-length): r = l + length for i in range(l, r): # [l,i]と[i,r]を結合する d = dp[l][i] + dp[i+1][r] + A[l]*A[i+1]*A[r+1] if dp[l][r] > d: dp[l][r] = d print(dp[0][-1])
