ABC131(A-E)
全体的に問題文が優しかったような気がする。
問題の難度も普通かそれよりも優しいものが多い印象。
その所為か提出速度でパフォーマンスが決まる感が強かったような。
いつもこんな感じなんだっけ。
Si : 文字列Sの i 文字目A
SiとSi+1を比較して一度でも==ならBad
i+1を| S |-1以下に収めないと範囲エラーに注意。
こういうのってforなしでスマートに書けないのかな。
Submission #6054840 - AtCoder Beginner Contest 131s = input()
is_bad = False
for i in range(1,len(s)):
if s[i-1] == s[i]:
is_bad = True
break
print('Bad' if is_bad else 'Good')
リンゴ i の味はL+i-1
Lはどのリンゴでも等しい定数。 リンゴの味の総和からリンゴの味の絶対値が最小のものを減算すればよさそう。 Submission #6057024 - AtCoder Beginner Contest 131B
i はリンゴが何番目か。
アップルパイの味への影響が最小となるリンゴ1つをつまみ食いする。
つまみ食いされたリンゴ以外のリンゴからできるアップルパイの味を出力する。n, l = map(int, input().split())
low = 9999
ans = 0
for i in range(n):
taste = l+i
low = min(taste, abs(low))
ans += taste
print(ans - low)
時間かかった。ifで結構時間をかけてしまった。 途中でc*dではなくlcmが必要だと気づいて、pythonならどこかにあるでしょうってことで調べたらmathとfractions(3.4以前)と出てきた。 Submission #6068902 - AtCoder Beginner Contest 131C
C - Anti-Division
解説見ると後でifで1か0を追加するよりも(a-1//c)としたほうがスマートっぽい。
多分動くだろうし。
f(B) - f(A-1)は典型なので思いつきたい。
(思いついたのは少し違う。 f(B) - f(A) でAをカウントしても良いなら+1する)
Atcoderのpython3は3.4.3なので以前ではない・・・よな、と思ってmathで提出したらREですね。
Atcoder python3( 3.4.3)ではfractionsを使いましょう。import fractions
a, b, c, d = map(int, input().split())
c, d = min(c,d), max(c, d)
ans = b - a + 1
if d%c == 0:#4 8 4 2
ans -= b//c - a//c + (0 if a%c != 0 else 1)
else:
x = b // c - a//c + (0 if a%c != 0 else 1)
y = b // d - a//d + (0 if a%d != 0 else 1)
lcm = c*d // fractions.gcd(c,d)
t = b //lcm - a//lcm + (1 if a >= lcm and a%lcm ==0 else 0)
ans = ans -x-y+t
# print(x,y,t,lcm,ans)
# ans += t
print(ans)
Dっぽくない。いっそCより簡単だと思う。 反対に締め切りを降順ソートすると、昇順ソートでは処理できるのにこっちだとできないケースがありそうなので不適でしょう。 締め切りXが等しい仕事Wが複数があったとして、締め切りXを過ぎるまでにWsがすべて完了していないといけない。 とか考えると締め切りでソートしたら解けるっぽい。 pythonだと結構時間かかってるのでちょっと肝が冷えた。 Submission #6071150 - AtCoder Beginner Contest 131D
罠かと思って色々考えたんだけど罠ではないっぽい...
1回目のソートは多分いらんのだろうけどそこ以外で早くなるのかなぁ。
itemgetter使ってみたけどlambdaと時間あまり変わらない。
n = int(input())
abn = [list(map(int,input().split())) for _ in range(n)]
#abn.sort()#これは本当はいらない
abn.sort(key = lambda x:x[1])
#print(abn)
ts = 0 # time_stamp
enable = True
for abi in abn:
a, b = abi
if not ts + a <= b:
enable = False
break
else:
ts += a
print('Yes' if enable else 'No')
Eにしては簡単な気がする。 ここまで試した。 n k => できるgraph;という感じで見てほしい。 kの上限 : (n-1) * (n-2)/ 2 で表せそう。 kが上限を超えたら-1E
要求する前提知識がとても少ないので取り組みやすい。
問題文が何を言いたいのか理解するまで少しかかった。
手元の紙にいろいろ書いて試すのに時間がかかってコンテスト中に提出はできなかったのは残念だけど解けたのはうれしい。
AC 23:16:35なのでCをもっと早く実装できてたら行けたかもしれないのかなぁ…。
n = 2 k = 0 => 1-2
n = 2 k > 0 => -1
n = 3 k = 0 => 三角形
n = 3 k = 1 => 1-2-3
n = 3 k > 1 => -1
n = 4 k = 0 => 四角形+ ×
n = 4 k = 1 => 四角形+ /
n = 4 k = 2 => 四角形
n = 4 k = 3 => 1-2; 2-3; 2-4 (NH3：アンモニアみたいな)
n = 4 k > 3 => -1
n = 5 k = 0 => 五角形 + 星
n = 5 k = 1 => 五角形 + 星 - /
...
n = 5 k = 4 => 五角形 + /
n = 5 k = 5 => 五角形
n = 5 k = 6 => 1-2; 2-3; 2-4; 2-5 (CH4 : メタンとか？)
n = 5 k > 6 => -1
できるグラフがわかればその辺の数Mもわかるはず。
できるグラフの辺の本数M : n * (n - 1) / 2 - k で表せそう。
kがちょうど上限ならグラフはstar（星、ウニともいうらしい; すべての辺がある1つの頂点から出ている）
kが上限未満なら完全グラフからk本の辺を引いたもの
(完全グラフ : すべての頂点間に辺がある)
(除いていく辺は図形の輪郭以外のもの; 図形の内側にある辺に限る)#include<vector>
#include<iostream>
#include<cstddef>
using si = std::int32_t;
si main(){
si n, k;
std::cin >> n >> k;
si max_ = ( n - 1 ) * ( n - 2 ) / 2;
if( max_ < k )
{
std::cout << -1 << "\n";
return 0;
}
/*
if( n == 3 && k == 1)
{
std::cout
<< 2 << "\n"
<< 1 << " " << 2 << "\n"
<< 2 << " " << 3 << "\n";
return 0;
}*/
std::cout << n*(n-1)/2 - k << "\n";
if( k == max_ )
for( si i{ 1 }; i < n; ++i )
std::cout << 1 << " " << i + 1 << "\n";
else
for( si i{}; i<n; ++i )
for( si j{}; j < i; ++j )
{
//条件文; 図形の内側にある辺なら
if( k > 0 && (i - j != 1 || i-j != n-1) )
--k;
else
std::cout << i + 1 << " " << j + 1 << "\n";
}
return 0;
}
