halcの競プロ精進ブログ

はるくが競プロしたことを書き留めるなにか

【今日の精進】ARC152D - Halftree

競プロ 今日の精進 ARC 黄Diff

毎日格上の問題を解くやつの11日目です。1

問題リンク

atcoder.jp

問題概要

N 頂点 0 辺の無向グラフに以下の操作を施して木にできるか判定してできるなら実際にやってみてね。

  • 頂点 a,b 間と頂点 (a+K)\%N,(b+K)\%N 間に辺を追加する。

解法

頂点数が偶数なら明らかに不可能です。

逆に、奇数であれば可能です。方法を言葉で説明するのが難しいので提出コードを見てほしい2のですが、だいたい以下のようなことをやっています。

  • G=gcd(N,K) とすると、G 個にグループ分けできる。
  • すべてのグループをいい感じにつなげる。このとき、偶数番目のグループではすべての頂点は何かしらの奇数番目のグループにつなげる。
  • 奇数番目のグループ内の頂点をつなげると、偶数番目もつながってくれる。

提出コード

import math

def calc(a,b):
    return (b*K+a)%N

N,K=map(int,input().split())
if N%2==0:
    print(-1)
    exit()
num=math.gcd(N,K)
ans=[]
for i in range(0,num-1,2):
    for j in range((N//num-1)//2):
        ans.append((calc(i,j*2),calc(i+1,j*2)))
    ans.append((calc(i+1,N//num-1),calc(i+2,N//num-1)))
for i in range(0,num,2):
    for j in range((N//num-1)//2):！
        ans.append((calc(i,j*2),calc(i,j*2+1)))
print(len(ans))
for i in ans:
    print(*i)

Submission #46130072 - AtCoder Regular Contest 152

感想

自分が強くなってるのか問題が簡単めなのかわからぬ

空いた日にやってたこと

10日目3

  1. 今日コンテストがありますがAtCoderではなくゆきこなのでノーカンです。↩
  2. あなた実装も下手でしょ↩
  3. 先生！こいつ大事な10日目にブログ書いてません！↩