Help us understand the problem. What is going on with this article?

Codeforces Round #671 (Div. 2) バチャ復習(9/22)

今回の成績

スクリーンショット 2020-09-22 12.58.55.png

今回の感想

焦りで考察がグダグダになってしまい勿体ない回でした。E問題は発想ゲーで思いついたのですが、十分な時間を確保できませんでした。

やはり考察の確度や勘がまだまだ悪いので、より多くの問題を解いて精緻にする他ないのかなと思っています。

A問題

(以下では、先攻のRazeをR,後攻のBreachをBとします。)

最後に残る数に注目します。最終的に一つ残った時の数が奇数のときはRの勝ちで、そうでないときはBの勝ちです。このとき、数が奇数個ある場合は最終的に奇数番目の数が残るので、先攻のRは勝利するように奇数を残せばよく、奇数番目に奇数が少なくとも一つあればRの勝ちになります。また、数が偶数個ある場合は最終的に偶数番目の数が残るので、後攻のBが勝利するように偶数を残せばよく、偶数番目に偶数が少なくとも一つあればBの勝ちになります。

出力する数を間違えて1WAを出しました。

A.py
for _ in range(int(input())):
    n=int(input())
    a=2**n+sum(2**i for i in range(1,n//2))
    b=sum(2**i for i in range(n//2,n))
    print(a-b)

B問題

非自明だったので、他の問題から解きました。このような図形の問題では実験を正確に行うことが大切です。

$n$段の階段を$n$個のみの正方形を使って作ったものをナイスと呼びます(初め、長方形と誤読しました。)。このナイスな階段が作れる場合を考えて実験を行います。

このとき、下図のようにできるだけ大きな正方形を作らないと$n$個のみの正方形で作ることはできません($\because$それより小さい正方形を使うと確実に$n$個を超えてしまうので)。すなわち、下図のようになります。

IMG_0639.JPG

上図では$n$=1~7の時を示していますが、$n$=1,3,7の時しか成り立ちません。また、成り立つのは奇数の時であるのは見れば明らかで、$n=2k+1$とした時に大きい長方形を作ると残りは二つの大きさ$k$の長方形ができることに気付きました。つまり、できる階段の大きさを$a_i$とした時、$a_{i+1}=2a_i+1$であることが必要です($a_0=1$)。

また、与えられるタイルの枚数は高々$10^{18}$であり、$a_i$は等比数列よりも速いスピードで増加するので、ナイスな階段の大きさは$a_0$から$a_{29}$まで求めれば十分です

したがって、求めたいのは与えられたタイルの枚数$x$に対してできる異なるナイスな階段の個数であり、階段の大きさが異なれば階段も異なるので、小さなナイスな階段から作れなくなるまで順に作れば良いです。また、与えられているのはタイルの枚数なので、$x$から引くべきは$\frac{a_i(a_i+1)}{2}$であることに注意が必要です。

B.py
cand=[1]
for i in range(100):
    cand.append(cand[-1]*2+1)
    if cand[-1]>10**18:
        break
for i in range(int(input())):
    ans=0
    x=int(input())
    for i in cand:
        j=i*(i+1)//2
        if x-j<0:
            break
        else:
            x-=j
            ans+=1
    print(ans)

C問題

コンテスト中は焦っておかしな解法を考えていましたが、冷静になるとそこまで難しくないです。

コンテスト中は以下のような場合分けをまず考えました。

(1)全ての人のレーティングが$x$である時
一回もコンテストを開かずに感染させることができます。

(2)全ての人のレーティングの合計が$nx$である時
全体の変化量を0として全ての人を$x$に等しくすることができるので、一回コンテストを開けば良いです。

(3)(1),(2)以外の時
ある一人以外を$x$にすることができ、二回の操作で全ての人を感染させることができます。

実は、(1),(2)の場合は正しいですが、(3)の場合は正しいとは限りません。コンテスト中はすでに感染してる人をうまく調整すれば一回の操作で済みそうと勘で考えてACを取りましたが、論理的に考えれば少なくとも一人がすでに感染していればその人以外を$x$することで全ての人を一回で感染させることができると言えます。おそらく、ある一人以外をという部分に着目できていれば正しく解けていたので、場合分けは正確性が大事だと感じました。

C.py
for _ in range(int(input())):
    n,x=map(int,input().split())
    a=list(map(int,input().split()))
    if a.count(x)==n:
        print(0)
    elif sum(a)==n*x:
        print(1)
    else:
        if a.count(x)>0:
            print(1)
        else:
            print(2)

D1問題

全て異なるので、0-indexedで偶数番目に最大のものから降順に突っ込んで奇数番目に最小のものから昇順に突っ込めば成り立ちます。今回ダントツで簡単な問題だと思います。

D.py
n=int(input())
a=list(map(int,input().split()))
a.sort()
from collections import deque
b=deque(a)
l=n//2-1 if n%2==0 else n//2
ans=[]
while len(b)>=2:
    ans.append(b.pop())
    ans.append(b.popleft())
if len(b)==1:
    ans.append(b.pop())
print(l)
print(" ".join(map(str,ans)))

D2問題

最終的にACしていた方針のコードの実装を間違っていたようで、方針と実装のどちらが間違っているかを判断できませんでした。今後は方針をしっかり詰め切ってから実装できるように考察力を伸ばしていきたいです。

以下の順で並べた時に買うことのできる氷球は最大となります(ABC178-Fが類題です。)。

IMG_0640.JPG

同じ値段の氷球の最大個数が$[\frac{n}{2}]$であればD1の時の最大値を達成でき、それより多い場合はどのような並べ方をしても最大個数は達成できなそうだと思いこの並べ方をしました。他に合理的な並べ方がないと思いこの並べ方にしました。

解答を見ると、$m$個の氷球が買える時に$m+1$個のそれらの氷球より小さい組み合わせが存在するので、二分探索で$m$を探すという方法を取っていました。$m$個の氷球が買える時という仮定がおければ単調性と最大値の組みあわせから二分探索の発想は訳も無いはずなので、典型が身についてないと感じました。

D.py
n=int(input())
a=list(map(int,input().split()))
a.sort()
from collections import deque
b=deque(a[:n//2])
c=deque(a[n//2:])
ans=[]
while len(b) or len(c):
    ans.append(c.popleft())
    if len(b)>0:
        ans.append(b.popleft())
#print(ans)
l=0
for i in range(1,n-1):
    if ans[i-1]>ans[i] and ans[i]<ans[i+1]:
        l+=1
print(l)
print(" ".join(map(str,ans)))

E問題

実装ミスでコンテスト終了後10分で解き終わりました。非常に悔しいです。このような問題が安定してくると壁を一気に超えれると思っているので耐えて努力します。

サンプルを見ながら実験をしたところ、多くの場合でlcmは一回もとる必要がないのではと思いました。そこで、隣合う数どうしが互いに素にならないように配置しますが、隣り合う数のgcdが0にならないようにしたいので、隣り合う数がどの数の倍数になるかに注目しました。特に、それぞれの数がどの素数の倍数になるのかに注目しました。つまり、例えば下図のように構築すれば良いです(構築方法はいくつかあると思いますが、どの素数の倍数かに注目すれば容易に思いつくと思います。)。

IMG_0641.JPG

上記のように黄色の丸で示された境界の部分をそれぞれの素数を一つずつかけたものとすることで、任意の要素の間でgcdを1以外にすることができます。

したがって、$O(\sqrt{n})$で約数を列挙してdivisorsへと格納し、$O(\sqrt{n})$で素因数分解を行ってprimeへと格納し、primeの要素の前から順にそれぞれの素数の倍数となる要素をdivisorsから抜いて答えとして出力する配列ansに格納していきます。また、昇順で保存したいのと取り出す際の速度が安定していることから、divisorsprimeはそれぞれsetにしました。

また、ansにはdivisorsに残ってるそれぞれの素数の倍数を適当に格納すれば良いですが、境界の部分を別に行わなければならないことに注意が必要です。これは、今見ている素数と次の素数の積を後からansに後から格納することで容易に達成できます(詳しくは実装を見てください。)。

さらに、一つ目のサンプルのようにlcmを取る必要があるのは素因数が異なる二つのみかつ$n$がその素因数の積で表される場合です。他の場合は自分の構築方法で必ず条件を満たすことができます。

E.cc
//デバッグ用オプション:-fsanitize=undefined,address

//コンパイラ最適化
#pragma GCC optimize("Ofast")

//インクルードなど
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

//マクロ
//forループ
//引数は、(ループ内変数,動く範囲)か(ループ内変数,始めの数,終わりの数)、のどちらか
//Dがついてないものはループ変数は1ずつインクリメントされ、Dがついてるものはループ変数は1ずつデクリメントされる
//FORAは範囲for文(使いにくかったら消す)
#define REP(i,n) for(ll i=0;i<ll(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=ll(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=ll(b);i--)
#define FORA(i,I) for(const auto& i:I)
//xにはvectorなどのコンテナ
#define ALL(x) x.begin(),x.end() 
#define SIZE(x) ll(x.size()) 
//定数
#define INF 1000000000000 //10^12:∞
#define MOD 1000000007 //10^9+7:合同式の法
#define MAXR 100000 //10^5:配列の最大のrange
//略記
#define PB push_back //挿入
#define MP make_pair //pairのコンストラクタ
#define F first //pairの一つ目の要素
#define S second //pairの二つ目の要素

//nは含まれない
set<ll> divisors;//約数を格納するset(削除したいので)

void make_divisors(ll n){
    FOR(i,2,sqrt(n)){
        if(n%i==0){
            divisors.insert(i);
            if(i!=n/i){
                divisors.insert(n/i);
            }
        }
    }
}

set<ll> prime;//素因数分解でそれぞれの素数がいくつ出てきたかを保存するmap

//O(√n)
//整列済み(mapはkeyで自動で整列される)
void prime_factorize(ll n){
    if(n<=1) return;
    ll l=sqrt(n);
    FOR(i,2,l){
        if(n%i==0){
        prime_factorize(i);prime_factorize(ll(n/i));return;
        }
    }
    //mapでは存在しないkeyの場合も自動で構築される
    prime.insert(n);return;
}

signed main(){
    //入力の高速化用のコード
    //ios::sync_with_stdio(false);
    //cin.tie(nullptr);
    ll t;cin>>t;
    REP(_,t){
        ll n;cin>>n;
        vector<ll> ans;
        divisors.clear();
        prime.clear();
        make_divisors(n);
        prime_factorize(n);
        if(SIZE(prime)==2 and (*prime.begin())*(*++prime.begin())==n){
            cout<<*prime.begin()<<" "<<*++prime.begin()<<" "<<n<<endl;
            cout<<1<<endl;
            continue;
        }
        for(auto i=prime.begin();i!=prime.end();i++){
            deque<ll> sub;
            ll l,r;l=*i;r=0;
            if(++i!=prime.end()){
                r=*i;
                sub.PB(l*r);
                divisors.erase(l*r);
            }
            --i;
            auto j=divisors.begin();
            while(j!=divisors.end()){
                if((*j)%(*i)==0){
                    sub.PB(*j);
                    j=divisors.erase(j);
                }else{
                    j++;
                }
            }
            while(SIZE(sub)){
                ll p=sub.back();
                sub.pop_back();
                ans.PB(p);
            }
        }
        ans.PB(n);
        if(SIZE(prime)==2 and (*prime.begin())*(*++prime.begin())==n){
            REP(i,SIZE(ans)){
                if(i!=SIZE(ans)-1)cout<<ans[i]<<" ";
                else cout<<ans[i]<<endl;
            }
            cout<<1<<endl;
        }else{
            REP(i,SIZE(ans)){
                if(i!=SIZE(ans)-1)cout<<ans[i]<<" ";
                else cout<<ans[i]<<endl;
            }
            cout<<0<<endl;
        }
    }
}

F問題

今回は飛ばします

DaikiSuyama
PythonとC++で競技プログラミングをしています(highest:AtCoder:1413,Codeforces:1672)。 機械学習も少し勉強しています。 FXや株の自動売買、音楽の自動生成に興味があります。
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away