マガジンのカバー画像

競技プログラミング

145
運営しているクリエイター

2022年9月の記事一覧

ほぼ日刊競プロ ABC269  C - Submask

ほぼ日刊競プロ ABC269  C - Submask

C - Submask

問題文
非負整数 N が与えられるので、以下の条件を満たす非負整数 x を昇順に全て出力してください。
x を 2 進数として表記した時に 1 となる位の集合が、 N を 2 進数として表記した時に 1 となる位の集合の部分集合となる。
すなわち、全ての非負整数 k について、「 x の 2^kの位が 1 ならば、 N の 2^kの位は 1 」が成り立つ。

考えたこと

もっとみる
ほぼ日刊競プロ ABC154 D - Dice in Line

ほぼ日刊競プロ ABC154 D - Dice in Line

D - Dice in Line

問題文
N 個のサイコロが左から右に一列に並べてあります。左から i 番目のサイコロは 1 から piまでの pi​種類の目がそれぞれ等確率で出ます。
隣接する K 個のサイコロを選んでそれぞれ独立に振ったとき、出る目の合計の期待値の最大値を求めてください。

考えたこと

まず1からpiまでしか出ないサイコロの期待値を求める.
1の時=1,2の時=1.5,3の

もっとみる
ほぼ日刊競プロ ABC199 C - IPFL

ほぼ日刊競プロ ABC199 C - IPFL

C - IPFL

問題文
長さ 2N の文字列 S があります。
この文字列に対して Q 個のクエリが与えられます。i 番目のクエリでは 3 つの整数 Ti,Ai​,Bi​が与えられるので、以下の処理をします。Ti​=1 のとき : S の Ai​文字目と Bi​文字目を入れ替えるTi​=2 のとき : S の前半 N 文字と後半 N 文字を入れ替える(Ai​,Bi​の値は用いない)
例えば S

もっとみる
ほぼ日刊競プロ ABC175 C - Walking Takahashi

ほぼ日刊競プロ ABC175 C - Walking Takahashi

C - Walking Takahashi

問題文
数直線上で暮らす高橋君は、今座標 X にいます。これから高橋君はちょうど K 回、座標の正または負の方向に D 移動する行為を繰り返そうと考えています。より正確には、1 回の移動では 座標 x から x+D または x−D に移動できます。高橋君は、ちょうど K 回移動した後にいる座標の絶対値が最小となるように移動したいです。K 回の移動後の座

もっとみる

ほぼ日刊競プロ ABC177 C - Sum of product of pairs

C - Sum of product of pairs

問題文
N 個の整数 A
1,…,ANが与えられます。
1≤i<j≤N を満たす全ての組 (i,j) についての Ai​×Aj​の和を mod(10^9+7) で求めてください。

考えたこと普通に2重for文ではタイムオーバーしてしまうため,効率よく計算する方法を考える.

sum = A1*A2+A1*A3+A1*A4+A2*A3+A

もっとみる
ほぼ日刊競プロ ABC193 C - Unexpressed

ほぼ日刊競プロ ABC193 C - Unexpressed

C - Unexpressed

問題文
整数 N が与えられます。 1 以上 N 以下の整数のうち、 2 以上の整数 a,b を用いて a^bと表せないものはいくつあるでしょうか?

考えたこと制約上Nの最大値は10^10なので2以上の整数aは2から10^5の範囲,bは2から多く見積もっても100で確かめればよい.
setを用いてハッシュテーブルで数を追加していく.

N=int(input()

もっとみる
ほぼ日刊競プロ ABC182 C - Travel

ほぼ日刊競プロ ABC182 C - Travel

C - Travel

問題文
N 個の都市があります。都市 i から都市 j へ移動するには T
i,jの時間がかかります。

都市 1 を出発し、全ての都市をちょうど 1 度ずつ訪問してから都市 1 に戻るような経路のうち、移動時間の合計がちょうど K になるようなものはいくつありますか?

考えたことitertoolsを用いて準列を用いる.

N,K = map(int,input().s

もっとみる