ABC120 参加メモ
https://atcoder.jp/contests/abc120 35分で全完できました！ 3237人中203位でした。
rating
980->1121(+141). 次回は水色いけるかな？
A
min(C, A // B) を出力するだけです。
B
A, B<=100なので内包表記でゴリ押しできます。
[i for i in range(1, 100 + 1) if A % i == 0 and B % i == 0][-K] が解です。
大きい方からK番目であることに注意しましょう。
Pythonのリストに対して[-i]にアクセスすると後ろからi番目の要素を得ることができます。
C
貪欲で通らないケースが思いつかず、未証明で貪欲コードを提出しました。
どうやら、 2min(S.count('0'), S.count('1')) で通るようです。エレガント。
D
1番目から順に橋が失われたとき、それぞれの不便さを求めるのはとても難しいのでは？と思いました。 しかし逆にM番目から順に橋が作成されると考えると考えやすそう。 そこで、M番目から順に解を求める方針にします。
最初の不便度はN*(N-1)/2です。 ここから、橋が増えるにつれて、不便度がどう減るかを計算します。 Union-FInd木を使って、結合する島が異なるグループかどうかを判定。 異なるグループならば、結合するグループの要素数の積だけ不便度が減ります。 例えば、3個のグループと4個のグループを結合する場合、不便度は12減ります。 これを1番目の橋まで順に計算するだけです。
ABC119 参加メモ
スキー帰りでちょっと疲労感がありましたが無事参加しました。 https://atcoder.jp/contests/abc119
rating
734から980に増加しました(+246)。 色も茶から緑になりました。 この調子でまずは水色を目指したい。
A
Pythonだと不等号を用いることで、辞書式順における文字列の大小を判定できます。
したがって、 Sが 2019/04/30 以下ならば Heisei, そうでなければ TBDを出力するだけでよいです。
B
定義通り計算するだけですね。 出力誤差についてはそこそこ許容してくれるので、浮動小数点数演算に怯える必要はありません。
C
Dより苦戦しました（Cより先にDを解きました）。 Nが8なのでゴリ押しでいけそうな雰囲気なのですが、いざゴリ押しコードを書こうとすると手が進まない。
最終的には、以下の考え方で解きました。
- N本の竹から長さのAの竹を作るために用いる竹を高々N-2本選ぶ
- 選んだすべての竹に対して、合成魔法を適用する（ポイント: 合成魔法はどの順序で適用しても結果は変わらない）
- 合成後の竹の長さがAになるように、延長魔法または短縮魔法をかける
- 残った竹についても長さB, Cを作るために、同様の処理を実行する
処理回数が指数的に増加するので、TLEが懸念されますが、各竹について、A, B, C, 使わないのいずれかのラベルを貼ると考えれば、パターンは高々 です（すべてAとかはありえないので、実際はもっと少ない）。
Nは高々8なので余裕で解けると見積もれます。
D
Cを後に回して先に着手しました。 これも難しかったらヤバイなーって思いつつも問題読んだら、手がつけやすそうな問題で安心。
まず、各xについて、訪問パターンは以下の4通り考えられます。
- そのxより西側で最も近い神社sと西側で最も近い寺tを訪問:
- そのxより西側で最も近い神社と東側で最も近い寺を訪問:
- そのxより東側で最も近い神社と西側で最も近い寺を訪問:
- そのxより東側で最も近い神社と東側で最も近い寺を訪問:
あとは、各xについて、西／東側で最も近い神社／寺を見つける方法を考えればよいです。 そしてそれは二分探索で求められます。 Pythonだとbisectという標準ライブラリを使うと楽です。
ABC103 D - Islands War
問題
https://atcoder.jp/contests/abc103/tasks/abc103_d
解法
貪欲的に解けます。 まず、bの値が小さい順に各要望をソートします。 ソートした要望を先頭からiterateし、叶えられていない要望を見つけるたびに、その要望を叶えられる橋のうち最も東の橋を取り除きます。 この方法により取り除いた橋の数が求める解です。
ACしたコード
from functools import reduce from operator import itemgetter N, M = map(int, input().split()) a, b = zip(*(map(int, input().split()) for _ in range(M))) ts = sorted(zip(a, b), key=itemgetter(1)) ans = reduce( lambda acc, t: acc if t[0] < acc[1] else (acc[0] + 1, t[1]), ts, (0, 0) )[0] print(ans)
ABC104 D - We Love ABC
問題
https://atcoder.jp/contests/abc104/tasks/abc104_d
解法
Tの先頭i文字のABC数の和を求める方法を考えます。
のとき、i文字目は役に立たないので、Tの先頭i-1文字のABC数の和です。
のとき、i文字目を使わない場合、および、i文字目のCを使う場合の和なので、
（Tの先頭i-1文字のABC数）+（Tの先頭i-1文字のAB数）です。
ここで、AB数とは、以下の条件を満たす組(i, j)の個数です。
のとき、i文字目をABCに含めない場合は?には3通りの好きな文字を入れられます。
i文字目をABCに含める場合はCを入れることになります。
したがって、3 * （Tの先頭i-1文字のABC数）+（Tの先頭i-1文字のAB数）です。
以上より、Tの先頭i-1文字のABC数とAB数が分かれば、O(1)でTの先頭i文字のABC数の和を求められます。 AB数も同様の考えで漸化式を導けます（AB数の和を求めるにはA数の和が必要。A数の和の漸化式は簡単でしょう）。
ABC数、AB数、A数の漸化式を導いたらi=1から順に|T|まで求めるだけです。
ACしたコード
from functools import reduce M = 10**9 + 7 S = input() ans = reduce( lambda t, s: (t[0], t[1] + t[0], t[2], t[3]) if s == 'A' else (t[0], t[1], t[1] + t[2], t[3]) if s == 'B' else (t[0], t[1], t[2], t[2] + t[3]) if s == 'C' else ((3 * t[0]) % M, (3 * t[1] + t[0]) % M, (3 * t[2] + t[1]) % M, (3 * t[3] + t[2]) % M), S, (1, 0, 0, 0) )[3] % M print(ans)
ABC118 参加メモ
ABC117に引き続き参加です。全完できました！
https://atcoder.jp/contests/abc118
rating
茶色になりました。
203 → 734
A
Aは1以上なので、BがAで割り切れるならば、AはBの約数です。
B
set型の積集合演算に甘えました。
すなわち、
を求めるコードを書きました。
C
ざっと読んで難しそうだと感じました。
何となく、体力が最小のモンスターを選んで、適当なモンスターに攻撃を繰り返せばいいんじゃね、と予想します。
さらに何となく、それってGCDを求めるアルゴリズムに似ているなと直感します。
時間が惜しいので証明はパス。 を解とするコードを提出したら通りました。
GCDでよい理由は、けんちょんさんの記事が参考になるかと思います。 http://drken1215.hatenablog.com/entry/2019/02/16/224200
D
貪欲に桁増やすだけじゃね、と思いましたが、マッチ棒をすべて使い切る制約が厄介そうです。 大人しくDPしました。 境界条件の処理をミスって一回WA. ACしたコードはかなり汚いので、きれいにしたい。
感想
全完できて嬉しかったです。 今後も400点問題を解けるように精進します。
ABC105 D - Candy Distribution
問題
https://atcoder.jp/contests/abc105/tasks/abc105_d
解法
解のパターンを以下の通り分割します。
- パターン1: 1番目の箱のみ使うパターン
- パターン2: 2番目の箱、および、必要ならば1番目の箱を使うパターン
- パターン3: 3番目の箱、および、必要ならば1, 2番目の箱を使うパターン
- ...
- パターンN: N番目の箱、および、必要ならば1, 2, ..., N-1番目の箱を使うパターン
上記のパターン分けは直和分割なので、最終的に求める解は上記の各パターンの解の和です。
パターンiの解をで表します
は簡単に求められます。
がMの倍数ならば、1, そうでなければ0です。
次に、 を求めます。
がMの倍数か
がMの倍数か
をチェックし、結果に応じて、0, 1, 2のいずれかの値になります。
を求めます。
同様に、3通りの計算を実施し、Mの倍数かチェックしてもよいのですが、そろそろ一般化も考えてみましょう。
この方法だと、
はi通りの計算が必要となり、計算量が大きすぎます。
ちょっと唐突ですが、 の先頭から何個かの項を除去し、Mの倍数にできないかを考えます。
をMで割った余りをRとします。
0,
,
のうち、余りがRであるものの個数が
です。
余りがRであるものを数え上げるのが大変そうですが、先頭からk要素の和の余りをハッシュで記憶しておけば、一般の場合においても、ほぼ定数オーダーの計算で
を計算できます。
（ハッシュの初期値は {0: 1} となる。ハッシュの各要素(k, v)は余りがkとなるものがv個あることを意味する）
最後に、上記のアルゴリズムの動作の具体例を書きます。 サンプル2で遊んでみます。
- 29%17=12はハッシュに含まれません。パターン1の解は0です。ハッシュに12を追加します。
- 更新後のハッシュ: {0: 1, 12: 1}
- ここまでの合計値: 12
- (12+7=19)%17=2はハッシュに含まれません。パターン2の解は0です。ハッシュに2を追加します。
- 更新後のハッシュ: {0: 1, 2: 1, 12: 1}
- ここまでの合計値: 2
- 2+5=7はハッシュに含まれません。パターン3の解は0です。ハッシュに7を追加します。
- 更新後のハッシュ: {0: 1, 2: 1, 7: 1, 12: 1}
- ここまでの合計値: 7
- 7+7=14はハッシュに含まれません。パターン4の解は0です。ハッシュに14を追加します。
- 更新後のハッシュ: {0: 1, 5: 1, 7: 1, 12: 1, 14: 1}
- ここまでの合計値: 14
- (14+9=23)%17=6はハッシュに含まれません。パターン5の解は0です。ハッシュに6を追加します。
- 更新後のハッシュ: {0: 1, 5: 1, 6: 1, 7: 1, 12: 1, 14: 1}
- ここまでの合計値: 6
- (6+51=57)%17=6はハッシュに含まれます。パターン6の解は1です。ハッシュに6を追加します（既に存在するので値を1から2に増やします）。
- 更新後のハッシュ: {0: 1, 5: 1, 6: 2, 7: 1, 12: 1, 14: 1}
- ここまでの合計値: 6
- 6+7=13はハッシュに含まれません。パターン7の解は0です。ハッシュに13を追加します。
- 更新後のハッシュ: {0: 1, 5: 1, 6: 2, 7: 1, 12: 1, 13: 0, 14: 1}
- ここまでの合計値: 13
- (13+13=26)%17=9はハッシュに含まれません。パターン8の解は0です。ハッシュに9を追加します。
- 更新後のハッシュ: {0: 1, 5: 1, 6: 2, 7: 1, 9: 1, 12: 1, 13: 0, 14: 1}
- ここまでの合計値: 9
- (9+8=17)%17=0はハッシュに含まれます。パターン9の解は1です。ハッシュに0を追加します。
- 更新後のハッシュ: {0: 2, 5: 1, 6: 2, 7: 1, 9: 1, 12: 1, 13: 0, 14: 1}
- ここまでの合計値: 0
- (0+55=55)%17=4はハッシュに含まれません。パターン10の解は0です。ハッシュに4を追加します。
- 更新後のハッシュ: {0: 1, 4: 1, 5: 1, 6: 2, 7: 1, 9: 1, 12: 1, 13: 0, 14: 1}
- ここまでの合計値: 4
- (4+42=46)%17=12はハッシュに含まれます。パターン11の解は1です。ハッシュに12を追加します。
- 更新後のハッシュ: {0: 1, 4: 1, 5: 1, 6: 2, 7: 1, 9: 1, 12: 2, 13: 0, 14: 1}
- ここまでの合計値: 12
- (12+9=21)%17=4はハッシュに含まれます。パターン12の解は1です。ハッシュに4を追加します。
- 更新後のハッシュ: {0: 1, 4: 2, 5: 1, 6: 2, 7: 1, 9: 1, 12: 2, 13: 0, 14: 1}
- ここまでの合計値: 4
- (4+81=85)%17=0はハッシュに含まれます。パターン13の解は2です。ハッシュに0を追加します。
- 更新後のハッシュ: {0: 2, 4: 2, 5: 1, 6: 2, 7: 1, 9: 1, 12: 2, 13: 0, 14: 1}
- ここまでの合計値: 0
以上より、各パターンの解を合計すると6を得ます。
ACしたコード
from collections import defaultdict N, M = map(int, input().split()) A = list(map(int, input().split())) acc = 0 s = defaultdict(int) s[0] = 1 ans = 0 for a in A: acc = (acc + a) % M ans += s[acc] s[acc] += 1 print(ans)
ABC109 D - Make Them Even
問題
https://atcoder.jp/contests/abc109/tasks/abc109_d
解法
偶数枚のコインが置かれたマスの数の最大値について、偶奇の性質から、以下の雑な見積もりができます。
- 全コインの枚数が偶数ならば高々HW
- 全コインの枚数が奇数ならば高々HW-1
そして実はこの雑な見積もりはタイトです。すなわち、全コインの枚数が偶数ならば各マスに置かれたコインの枚数を偶数枚にでき、 そうでなくとも、1マスを除いて、各マスに置かれたコインの枚数を偶数枚にできます。
最初に、そのようなコインの配置を実現する手順を述べます。
- マス(1, 1)に置かれたコインの枚数が奇数ならば、マス(1, 2)にコインを1枚移す
- マス(1, 2)に置かれたコインの枚数（マス(1, 1)から移されたコインも含めてカウント）が奇数ならば、マス(1, 3)にコインを1枚移す
- ...
- マス(1, W-1)に置かれたコインの枚数が奇数ならば、マス(1, W)にコインを1枚移す
- マス(1, W)に置かれたコインの枚数が奇数ならば、マス(2, W)にコインを1枚移す
- マス(2, 1)に置かれたコインの枚数が奇数ならば、マス(2, 2)にコインを1枚移す
- マス(2, 2)に置かれたコインの枚数が奇数ならば、マス(2, 3)にコインを1枚移す
- ...
- マス(2, W-1)に置かれたコインの枚数が奇数ならば、マス(2, W)にコインを1枚移す
- マス(2, W)に置かれたコインの枚数が奇数ならば、マス(3, W)にコインを1枚移す
- ...
- マス(H, 1)に置かれたコインの枚数が奇数ならば、マス(H, 2)にコインを1枚移す
- マス(H, 2)に置かれたコインの枚数が奇数ならば、マス(H, 3)にコインを1枚移す
- マス(H, W-1)に置かれたコインの枚数が奇数ならば、マス(H, W)にコインを1枚移す
AAで表すと以下のイメージです。
→→→...→→↓ →→→...→→↓ ... →→→...→→↓ →→→...→→終
上記手順により、マス(H, W)以外のマスに置かれたコインの枚数は偶数になることは明らかです。 それでは、マス(H, W)に置かれたコインの枚数の偶奇はどうなるでしょうか。
- 全コインの枚数が偶数ならば、他のマスのコインはすべて偶数なので、マス(H, W)に置かれたコインの枚数も偶数です。
- 全コインの枚数が奇数ならば、他のマスのコインはすべて偶数なので、マス(H, W)に置かれたコインの枚数は奇数です。
したがって、最初の雑な見積もりはタイトであることが分かりました。
ACしたコード
この問題も、計算量の都合を考えると、宣言的にプログラミングするのは難しいですね。
H, W = map(int, input().split()) a = [list(map(int, input().split())) for _ in range(H)] ans = [] for i in range(H): for j in range(W): if a[i][j] % 2 == 1: a[i][j] -= 1 if j < W - 1: ans.append((i + 1, j + 1, i + 1, j + 2)) a[i][j + 1] += 1 elif i < H - 1: ans.append((i + 1, j + 1, i + 2, j + 1)) a[i + 1][j] += 1 print(len(ans)) for y, x, y_, x_ in ans: print(y, x, y_, x_)
