AtCoder Regular Contest 129 A - Smaller XOR 解けなかった方いますか? 僕はエスパーしました。
皆さんこんばんは。
ARC129お疲れ様でした!!
なんとか2完出来て耐えました。。
所でA問題を皆さんどのようにして解きましたか?
僕はエスパーしました。
ということで
今回はエスパー記事第3弾です!!!!
↓今までのエスパー記事はこちら↓
ryusuke920.hatenablog.jp
それではまずは問題から見ていきましょう。
1. 問題の概要
整数N, L, R が与えられます。
以下の条件を満たす整数 x の個数を数える問題
2. 問題の制約・入力例
2-1. 問題の制約・入力例
2-2. 入力例
入力例1
出力例1
入力例2
出力例2
入力例3
出力例3
3. エスパー方法
まずは実験です。
解けなかった方、ちゃんと実験しましたか?
実験はエスパーを行う上で本当に大切です。
今回の勝因は完全に実験です。
入力例1, 3は両極端なので今回は2を使って説明します。
すると、以下のような結果になります。
もう見えましたよね?
これ、ずつ条件を満たすものと満たさないものがあります。
なので、 R の2進数の長さ分 for文を回して条件を満たしていれば、をカウントするだけです。
4. ACコード
n, l, r = map(int,input().split()) def f(x): ans = 0 for i in range(len(int(bin(x)[2:]))): if 2 ** i ^ n < n: ans += min(2 ** (i + 1) - 1, r) - 2 ** i + 1 return ans print(f(r) - f(l - 1))
5. 最後に
ここまでエスパー出来てるのになぜ2ペナしてる?と思う方いるかも知れません。
それは...
1 ~ R までの個数で求めていてずっと気づきませんでした!!!!!!!!!!!!!!!!!
1 ~ R で考えてもこの入力例が全て通ってしまうのは罠ですね...
最後までありがとうございました!
AtCoder Beginner Contest 157 D - Friend Suggestions (Python)
本日はこちらの水diff!!
問題はこちら〜
https://atcoder.jp/contests/abc157/tasks/abc157_d
友達関係の問題!
現代社会にまつわる問題ですね(笑)
1. 問題の概要
N人の人々の間にM組の「友達関係」とK組の「ブロック関係」があります。
各人々 i に対して、友達候補の数を出力せよという問題。
ここでいう友達候補というのは簡単にいうとAさんから友達を伝って行ってBさんまでたどれればAとBは友達候補になります。
2. 問題の制約と入力例
2-1. 問題の制約
- 入力は全て整数
2-2. 入力例
入力例1
出力例1
入力例2
出力例2
3. 問題を見て考えたこと
友達の関係と言われたらぱっと思いつくのはやはり Union-Find ですよね。
でもどのように管理すれば良いかがよくわからない。
とりあえず「友達関係」の集合を Union-Find で管理してその後は...と言う所で少し躓いてしまいました。
それでは解説していきます。
4. 解説
この問題はお気づきの通り、 Union-Findで解くことができます。
まず、「友達関係」の集合を Union-Find で管理します。
その中で「友達候補」になることができないのは、自分自身もしくは「ブロック関係」にある人々です。
したがって、まずM個の入力で「友達関係」の集合を管理し、K個の入力で が同じグループに属していれば「友達候補」になれない集合(今回の場合は out 配列)に加えます。
そうすると、各人々 i に対して出力する友達候補の数は
となります。
ここで out[i] := 人 i に対して友達候補になれない人数です。
をしているのは自分自身を除くためです。
このようにしてこの問題は解くことが出来ました。
5. ACコード
class UnionFind: def __init__(self, n): self.n = n self.p = [-1] * n def leader(self, a): while self.p[a] >= 0: a = self.p[a] return a def merge(self, a, b): x = self.leader(a) y = self.leader(b) if x == y: return x if self.p[x] > self.p[y]: x, y = y, x self.p[x] += self.p[y] self.p[y] = x return x def same(self, a, b): return self.leader(a) == self.leader(b) def size(self, a): return -self.p[self.leader(a)] n, m, k = map(int,input().split()) uf = UnionFind(n) out = [[] for _ in range(n)] # 友達もしくは同じグループの中で喧嘩の組み合わせの集合 for _ in range(m): a, b = map(int,input().split()) a -= 1 b -= 1 uf.merge(a, b) out[a].append(b) out[b].append(a) for _ in range(k): c, d = map(int,input().split()) c -= 1 d -= 1 if uf.same(c, d): out[c].append(d) out[d].append(c) ans = [] for i in range(n): ans.append(uf.size(i) - len(out[i]) - 1) print(*ans)
6. 最後に
ここ2日間ですが、早朝に起きて精進をする生活をしています。
朝を有効活用するととても得した気分になるので今後も続けて行けたらやっていきたいなと考えています。
Twitterのスペースを活用しているのでよければ作業がてら来てください!
最後まで見ていただきありがとうございました!
AtCoder Beginner Contest 080 C - Shopping Street (Python)
本日は前まで解けなかった緑diffが今考えたら解けたので紹介したいと思います!
問題はこちら〜
https://atcoder.jp/contests/abc080/tasks/abc080_c
とにかく問題文が長い...
見るだけで嫌になってしまいますよね。
1. 問題の概要
月曜日〜金曜日までの5日間、それぞれ午前・午後に分けた10区間に対して、お店がそれぞれ開店、もしくは閉店している。
joisinoお姉ちゃんは各店が営業している時間帯に店を開くと、その個数に応じた利益が得られます。(説明がとにかく複雑なので詳しくは問題文を見てください...)
このとき、利益の最大値はいくらになるか。
2. 問題を見て考えたこと
冒頭にも書いたようにとにかく問題文が長い...
読解するだけで自分は15分ほどかかってしまいました...
どのように考えれば良いか考えましたが、10区間しかなく、それぞれ営業するかしないかの2択!
これは〇〇しかなさそうですよね???
3. 問題の制約
- を満たす全ての整数 i に対して、 を満たす (j, k) が必ず1つ以上存在する
- 入力は全て整数
4. 解説
こちらは bit全探索 のアルゴリズムを用いることでACすることができます!
N 個のお店それぞれ10区間に対して営業するかしないかを考えると、計算量も余裕で間に合います。
bit全探索でjoisinoお姉ちゃんのお店を開くか・開かないかを列挙し、josinoお姉ちゃんが店を開いているかつお店 i が開いていれば個数をカウントし、その個数に対応した利益を格納する配列(今回の場合はplus)の合計値の最大化をすれば解くことができます。
コーナーケースとして、全てのお店が開いていない場合は例外と問題文に書かれているのでその時だけは除外しましょう。(そうしないと入力例2で0が出力されます。)
5. ACコード
from itertools import product n = int(input()) f = [list(map(int,input().split())) for _ in range(n)] p = [list(map(int,input().split())) for _ in range(n)] ans = -10 ** 18 # マイナスの場合もあるので初期値は負のINF for i in product([0, 1], repeat=10): if i.count(0) == 10: continue # 店が1つも空いていない時はNG is_open = [0] * n # 各お店とjoisinoお姉ちゃんが両方とも営業している時間帯の数 for j in range(n): for k in range(10): if i[k] == 1 and f[j][k] == 1: # どちらも営業している is_open[j] += 1 plus = [] for j in range(n): plus.append(p[j][is_open[j]]) ans = max(ans, sum(plus)) print(ans)
6. 最後に
つい3ヶ月ほど前にロックアウトで1度出たのですが、全くわからず撤退してしまいました...
でもこうして時間を空けると思いのほか解けてしまいます。
成長を実感できて良かったです!
最後まで見ていただきありがとうございました!
キーエンスプログラミングコンテスト2021-Nov. (AtCoder Beginner Contest 227) C - ABC conjecture (Python)
お久しぶりです!
久々に解説記事を書きたいと思います!
問題はこちら!
https://atcoder.jp/contests/abc227/tasks/abc227_c
数学問題なので得意分野だし解説しようかと思いま〜す
1. 問題の概要
2. 制約と入力例
2-1. 制約
2-2. 入力例
入力例1
N = 4 のとき、条件を満たす組み合わせは、
(1, 1, 1), (1, 1, 2), (1, 1, 3), (1, 1, 4), (1, 2, 2) の5つです。
入力例2
N = 100000000000 のとき、条件を満たす組み合わせは、 5745290566750 個です。
3. 見てすぐに考えたこと
- 入力例2からわかるように N が最大の時の個数がとても多いので単純に回すのは絶対に無理
- 整数問題でよくある O(N^2) 解法でもTLEしてしまう。
- 高校数学の整数問題 に似ている?
ということで、3つ目の直感で思ったことから不等式で条件を絞っていこうと考えました。
4. 解説
まずは与えられた不等式を用いて範囲を絞ります!
とわかるので、探索するAの範囲は までで良いことがわかります。
次にBの範囲を絞っていきます。
したがって、探索するBの範囲は までで良いことがわかります。
ここまで、範囲が絞れたらあとは条件を満たすを満たす C の個数を求めれば良いです!
5. ACコード
n = int(input()) ans = 0 for a in range(1, int(n ** (1 / 3)) + 10): for b in range(a, int((n / a) ** 0.5) + 10): ans += max(0, int(n // (a * b)) - b + 1) print(ans)
6. 最後に
久しぶりの数学問題 & 水パフォが出てとても嬉しかったです。
年内の入水を目指してこっそり精進しています。
最後まで見てくださってありがとうございました!!
AtCoder Regular Contest 035 🧪 C - アットコーダー王国の交通事情 (Python)
久々投稿です!
おはこんばんにちは〜
今日は毎晩やっているバチャで面白い問題があったので紹介したいと思います!
問題はこちら!
https://atcoder.jp/contests/arc035/tasks/arc035_c
試験管🧪で難易度は青で1655diffとなってます!
解説記事の水以上は初めてなので緊張してますが、頑張っていきます!(' _ ')
ダイクストラ法やワーシャルフロイド法を知っている方であれば、
灰色の方も理解できるように頑張って作ったので見ていただけると幸いです。
1. 問題の概要
要は全ての都市間の最短経路長の総和を求めろと言う問題。
総和を S, 2頂点間の最短距離を D(i, j) とすると、
となるので、 S を出力する問題である。
ただ求めるだけならば、ダイクストラを貼って O(N^2) で終わるが、
この問題は K 個のクエリが与えられ、毎度辺が追加されるという特徴がある。
これをどう処理していくかが重要である。
2. 入力例と制約
3. 解説
まず、計算量について考えてみよう。
今回の制約の特徴は何と言っても N が小さいことにある。
K 回のクエリごとに辺を追加し、最短距離を更新した後に、毎回全通りの D(i, j) を求めても O(KN^2) となるので間に合うことがわかる!
つまり、ダイクストラでクエリ処理前の全ての2頂点間の最短距離を O(N^2logN) 求めた後に、辺を追加していくことを考える。
では、頂点 (x, y) 間に z で行ける距離を追加した場合どのような更新が行われるかを考えよう。
以下、 dist[a][b] を a から b までの最短距離と定義する。
1つ目のパターンは、頂点 (a, b) の距離を a → x → y → b で辿っていく場合が考えられる。
2つ目のパターンは、頂点 (a, b) の距離を a → y → x → b で辿っていく場合である。
したがって、このように3パターン(更新せずに a → b に行くパターンを含めた)のうち、最短となるものを求めて更新していけば良いことがわかる。
a → b の組み合わせは 、
通りあるので、これは O(N^2) で処理することが可能となる。したがって、
- 前処理としてダイクストラ法(ワーシャルフロイド法でも可能)で全ての2頂点間の最短距離を求める。
- K 回のクエリごとに最短距離を更新 O(N^2) し、クエリごとに毎回全ての2頂点間の全通り O(N^2) を試して総和を求めることができる。
したがって、計算量は O(N^2logN + KN^2) となる。
4. ACコード
ACしたコードはこちらになります。
import sys input = sys.stdin.readline from heapq import heappush, heappop # ダイクストラ法で最短経路を求める def dijkstra(s, graph): dist = [INF] * n check = [False] * n dist[s] = 0 q = [(0, s)] while q: v = heappop(q)[1] if check[v]: continue check[v] = True for i, j in graph[v]: if check[i] != False: continue if dist[i] <= dist[v] + j: continue dist[i] = dist[v] + j heappush(q, (dist[i], i)) return dist INF = 10 ** 9 n, m = map(int,input().split()) # ノードの追加 g = [[] for _ in range(n)] for _ in range(m): a, b, c = map(int,input().split()) g[a - 1].append((b - 1, c)) g[b - 1].append((a - 1, c)) # 全ての2頂点間の最短経路を求める dist = [] for i in range(n): dist.append(dijkstra(i, g)) k = int(input()) for _ in range(k): x, y, z = map(int,input().split()) # 最短距離の更新を行う for i in range(n): for j in range(n): if i == j: continue dist[i][j] = min(dist[i][j], dist[i][x - 1] + dist[y - 1][j] + z, dist[i][y - 1] + dist[j][x - 1] + z) # 総和 S を求める ans = 0 for i in range(n - 1): for j in range(i + 1, n): ans += dist[i][j] print(ans)
5. 最後に
久々に解説記事を書きました。
途中ではPower Pointを使用した画像を入れてみましたが、どうでしょうか?
また気分が向いたら記事を書きたいと思います!!
AtCoder Beginner Contest 200 - D Happy Birthday! 2 を嘘解法した (嘘・エスパーシリーズ Ver.2)
皆さんこんばんは!
炎上記事Part 2 です!!
本日行われたABCで今度は嘘解法してしまいました!!!
というか、今回はエスパーのつもりはなくて、とりまなんもすることないし、適当にやって嘘解法でも提出しちゃえ!!!ってやったらACして発狂しました。。。
ちなみに前回のエスパー記事はこちら
問題はこちら
要約すると、配列 A からいくつか取り出し、余りが同じになる異なる取り出し方はありますか?という問題です。
コード
早速ですが、まずはACしたコードを載せようと思います!こちら!!
n = int(input()) a = list(map(int,input().split())) for i in range(n): a[i] %= 200 num = [[] for _ in range(200)] for i in range(n): cnt = a[i] cnt %= 200 num[cnt].append([i + 1]) for i in range(n - 1): for j in range(i + 1, n): cnt = a[i] + a[j] cnt %= 200 num[cnt].append([i + 1, j + 1]) for i in range(n - 2): for j in range(i + 1, n - 1): for k in range(j + 1, n): cnt = a[i] + a[j] + a[k] cnt %= 200 num[cnt].append([i + 1, j + 1, k + 1]) for i in range(len(num)): if len(num[i]) >= 2: print("Yes") print(len(num[i][0]), *num[i][0]) print(len(num[i][1]), *num[i][1]) exit() print("No")
最初に言います。
なんでこれでACできるのかわかっていません!!
鳩の巣原理でなんかやるんだろうなーとは速攻で思ったんですけど(これも合っているのか分からんが。)そこからがわからなかった。
あとNが大きい時はどうせ鳩の巣原理で絶対にYesだろうくらいには思いました。
これ、何をしているのかと言うと、時間内に間に合う限りで全探索してみようと言う発想です!
N <= 200 の制約になっていたので、O(N^3) までなら間に合うかと言うことで、
Part 1 すべての始まりO(N)
num = [[] for _ in range(200)] for i in range(n): cnt = a[i] cnt %= 200 num[cnt].append([i + 1])
ここでは、まず O(N) で余りが 200 パターンのうち、何になるかを計算しています。
Part 2 ちょっとレベルアップ O(N^2)
for i in range(n - 1): for j in range(i + 1, n): cnt = a[i] + a[j] cnt %= 200 num[cnt].append([i + 1, j + 1])
ここでは、2つの組み合わせで作れる余りを全列挙しています。時間も余裕で間に合いますよね。
Part 3 最後のステップ O(N^3)!!!!!
for i in range(n - 2): for j in range(i + 1, n - 1): for k in range(j + 1, n): cnt = a[i] + a[j] + a[k] cnt %= 200 num[cnt].append([i + 1, j + 1, k + 1])
ここでは、3つの組み合わせで作れる余りを全列挙しています。
答えはYes or No ?
最後にこのnum(上記の余りのパターンを格納した配列)の中身を全探索(200通り)し、あるあまりが2パターン以上(lengthが2以上)あれば、違う組み合わせで余りが同じになるパターンがあると言うことなので、それを出力します。
逆に見つからなかった場合は、一致する余りがないと言うことになる(はず)なので No を出力してACしました。
最後に
なんでこれでACしたのか本当によくわかりません。
緑になってから、エスパーして大幅にレートが上がるか、失敗して下がっているかの2択です。辛いです。
追記(解説見ました 2021/05/08/23:00現在)
Bit全探索???
は??なにそれおいしいの????
AtCoder Regular Contest 117-B - ARC Wrecker のエスパーしてみた!!!
皆さんARC117お疲れ様でした!!
いつも通り?2完速解きコンテストでしたね...
自分のコンテスト結果はこんな感じです!!
昨日の色変と言い、今日のコンテストと言い速解きでパフォが出てしまっているので今後が怖いです!!!
そんな中で、今日はタイトルにもある通り、B問題のエスパーの仕方を紹介したいと思います!!
目次はこちら!!
こんな記事書いたら炎上しそうです...
問題
問題はこちら!!!
N個の連なるビルに対して、大砲を撃っていき、撃った全ての階が崩壊する。
この時、何通りありますか?というもの...
見た瞬間はまじでわかりませんでした。
なのでどういう風に考えて10分ほどで解けたのか、紹介していきます。
エスパーの仕方
※以下、入力例3を例に紹介していきます!!
1. set 取れますやん
最初はsetをとって、同じ高さのビルの重複があればビルの個数減らせるじゃん!というものです。
だってそうですよね?同じ高さのビルがあっても、同じ崩壊の仕方をするだけですから、重複してるビルは消去しても問題ありません。
2. sort 出来ちゃうんですよねーー
つい昨日の事なんですが、コンテスト中に迷ってしまった場合、何をすればまとめたリストを作成しようと思い、Twitterで募集をかけました。
作るかこれ pic.twitter.com/noEzXq3Hpf
— カイリュー (@ryusuke__h) 2021年4月17日
このときに、 harurun さんが ソートしてみる とコメントを下さいました。
ソートしてみる
— harurun🌹 (@harurun_p) 2021年4月17日
そうなんですよ、、やることがなくなったら次はソートするんですよ!!!
そしたら、各ビルが何階くらい離れてるのか知りたかったので、差をとってみました!!
すると、以下のような結果になりました!!
なるほどなーこれもなんか ソート してみるか!!
としてみたら以下のようになりました。
んーーなんかわからんな???
手が進まなかったら、次はもちろんあれだよな???
3. デカイ数字はとりま素因数分解!!!
今回のB問題は出力例3がいつもと違って、modを取る前の答えが書いてありました。
なので、これを素因数分解するとなんと...!!!
あれ??107???
さっきの差を取った時に出てきてるやんwwwwwwww
ここが本日の勝因となりました。
ということでここでこのソートして差を取ってきたことが無駄ではないと確信しました。
ここで一旦先ほどの差を取った配列を全てかけてみることにしました。
しかし、答えが少し小さい値になってしまいました!!
4. 何が足りない!?
ということで、ここで後何をかければ、答えが 20192492160000 になるのかをめっちゃ考えました。
ここで考えたのが、先ほどの素因数分解の結果と今回の差の配列の全ての素因数を比較して、何が足りないのかを考えることにしました(俺は一体何をしてるんだ??)
その結果がこちらです!
さて、ここまできたぞ!!
あとは、この160の正体はなんぞや!ということですね。。
5. 160って何者???
そしたら、ここで160を思い浮かべるものがありますよね??
それは、
与えられた配列Aの最小値に1を足したもの!!!
ということです!!!
さて、他にこんなことを考えた参加者はいるのでしょうか?(いないと信じたい。)
なので最後に
ans *= (min(a) + 1) ans %= mod print(ans)
とやると、見事AC出来たという訳です。
Pythonコード
n = int(input()) a = list(map(int,input().split())) mod = 10 ** 9 + 7 a = list(set(a)) a.sort() x = [] for i in range(len(a) - 1): x.append(a[i + 1] - a[i] + 1) ans = 1 for i in range(len(x)): ans *= x[i] ans %= mod ans *= (a[0] + 1) print(ans % mod)
最後に
エスパー記事いかがでしたか?
なかなか面白いものが出来たと個人的には思っています。
結論は...
こんな感じでレート上がっても嬉しくないよ!!!
以上!!!!!
最後までありがとうございました!!!