FC2ブログ

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

ABC106参加した感じ

前回がABC082とかまじってなってる今日この頃

AtCoder Beginner Contest 106出ました。言語はC。
団つよバハに自発参加するためには全完55分以内が必須・・・。無理でした。
B問題に無駄に時間かけなければーって感じではありますが。


A問題

問題文ほぼ見てない。図が強い。50秒切れた。
(a-1)*(b-1)


B問題

1~nの奇数iを1~iで割った余りが0になる回数が8になるiの数を求めればいい。
のだけれど急に素数がうんたらとか考え始めてあまりにも遅いうえに1WA。


C問題

”翌々日には~”の時点で「あ、これは」ってなるやつ。
K回以内に1以外が出たらその数。1のみなら1。
なお実際に提出したものはあまりにも雑魚。

int main(){
char s[101];
ll k;
scanf("%s %lld", s, &k);

int len = strlen(s);
REP(i, len) {
if (s[i] != '1') {
if ((ll)i < k) {
printf("%c\n", s[i]);
break;
}
else {
PRINTD(1);
break;
}
}
if (i == len - 1) {
PRINTD(1);
break;
}
}

}

判定の仕方がもう自分で見ててつらい。


D問題

2次元累積和は頭良すぎなので累積和の足し算。

int main(){
int n, m, q;
int l[500][500] = { 0 };
scanf("%d%d%d", &n, &m, &q);
REP(i, m) {
int a, b;
scanf("%d %d", &a, &b);
l[a-1][b-1]++;
}
REP(i, n) {
REPS(j, n-1) {
l[i][j] += l[i][j - 1];
}
}
int ans;
REP(i, q) {
ans = 0;
int a, b;
scanf("%d %d", &a, &b);
a--; b--;
FOR(j,a,b+1) {
ans += l[j][b];
}
PRINTD(ans);
}

}

O(QM)が明らかに無理なので事前になんか計算してのO(QN)の解法探したらまぁこんな感じになるだろうなぁと。


しばらく期間空いているのですでにunratedですがレートをば。
rank_20180818.png
rate_20180818.png
スポンサーサイト

ABC082参加した感じ

なんか深秘録の大会やってたのでロビーで対戦してたら開始に遅れました。(12分くらい?)
そんなわけで今回は1WAの三完でした。言語はC。
dpの扱い方があまりにも下手・・・。


A問題beta.atcoder.jp/contests/abc082/tasks/abc082_a

入力の正整数a,bの平均値を切り上げしたものを出力。
(a+b+1)/2


B問題beta.atcoder.jp/contests/abc082/tasks/abc082_b

文字列s,tが与えられる。それぞれの文字順を好きに入れ替えてs',t'にしたときに辞書順でs'<t'にできるか。
要するにsを最小、tを最大になるように並べ替えた時にs'<t'になるか見るだけ。
ソートして比較して終わり。
比較がstrcmpで済むところをif文書いて判定したのを気にしてなんかいない。いない。
あとWA出したのはこいつでYesをYESにしていた。


C問題beta.atcoder.jp/contests/abc082/tasks/arc087_a

長さNの正整数の列aを良い数列にする。
数列bが良い数であるとは、次の条件が成り立つこと。
・bの各要素xについて、bに値xはちょうどx個含まれる。
aを良い数列にするために取り除くべき要素の個数の最小値を求める。

ABC081にも出現数を数える問題が・・・うっ、頭が。
今回aiは最大109なので出現数[ai]をインクリメントしていく方法は使えない。
Nは最大105なのでこちらはたいした数ではない。
つまり前回の頭悪そうな数え方が正攻法のはず。
そういうわけで入力を全部配列に突っ込んでソートし、頭から出現数を数えていく。

出力としては取り除くべき要素の個数なので、今見ている値をcとすると
cの出現数<cの時、cはすべて取り除くため答えに出現数を足す。
cの出現数>cの時、cはの出現数をcにするために答えに出現数-cだけ足す。


D問題beta.atcoder.jp/contests/abc082/tasks/arc087_b

二次元平面上の原点から命令列sに従い移動した時(x,y)に移動できるか。
sは次の2文字。
・F : 今向いている向きに長さ 1 だけ移動する。
・T : 時計回りまたは反時計回りの好きな方向に 90 度だけ向きを変える。
最初はx軸の正の向きを向いている。

まず最初にTが出るまでのFは必ずx軸の正の方向へ移動することになるので移動し終わった場所を原点として(x-(先頭のFの個数),y)へ移動する問題にできる。
この後がいろいろ迷走して、最初の方針の回答がx軸方向、y軸方向に全部で何回移動できるか調べて(x-x軸移動数)%2==0&&(y-y軸移動数)&2==0ならいけるのでは!?と書いてWAが5/49のところまでなまじ行けてしまったので余計悩むことに。
当然TFFで(0,0)が行けることになってしまうので間違いなわけで。
じゃあやっぱりdpだなということでdp[xの位置][yの位置][指示の回数][向いてる方向]・・・16000*16000*8000*4・・・w
その後xとyを分けたりしてとかなんやかんやしてても正解にたどり着けなかったので解説を見ることに。

正解としてはxとyは独立していてi回目の移動距離をdiとすると、
dp[0][8000]=1
dp[i][x+8000]=dp[i-1][x+8000-di] || dp[i-1][x+8000+di]
の漸化式からdp[移動回数][x+8000]=1になるかどうかを考えればいい。yも同様


そんなわけでレート推移。


開始遅かったのが悪い(自業自得)

余談ですが今回D問題AC後に他の方でC言語でD問題をACした提出を見てみたわけなのですが、
コメントを見ると貪欲法でやってる・・・?実際にコード見ても貪欲法。
TTFFFFFFTTFFFFFTTFFFF(x軸方向に6,5,4移動できる)
3 0
という入力があったとすると貪欲法では解けません。
twitterを見ても同様に言及している方がいましたので嘘解法が通るテストケースだったようですねぇ。

ABC081参加した感じ

そういえばブログとかあったなって思ったのでプログラミングコンテストの記録残し用に使ってみる。

本日は風呂に入ってたので遅れて(誤差程度)スタート。言語はC。
結果としては2WAの全完でした。


A問題beta.atcoder.jp/contests/abc081/tasks/abc081_a

'1'か'0'からなる3文字の文字列が与えられるので'1'の個数を数えて終わり。



B問題beta.atcoder.jp/contests/abc081/tasks/abc081_b

N個の正の整数が与えられるので、すべての数値が偶数なら2で割っていく操作が何回できるか求める。
入力値を配列に突っ込んで頭から全部2で割れるか見ていき、割り切れるなら全部2で割り、cntをインクリメント。
割り切れないものが出た時点でbreakしてcntを出力。



C問題beta.atcoder.jp/contests/abc081/tasks/arc086_a

N個の正の整数が与えられる。いくつの整数を書き変えれば値をK種類以下にできるか。
とりあえずぱっと思いついたので出現回数が少ないN-K種類分の値の合計出現数を足せばよい。
まず1≦N≦200000なのでA[200000]の入力値-1の要素に各値の出現数を数えればいい・・・のだけどなかなかあほな数え方をしてしまった。

  • QSort(A, 0, N - 1,1);
  • //ShowData(A, N);
  • int tmp=A[0];
  • int idx = 0;
  • int cntK[200000];
  • int cnt=0;
  • for (i = 0; i < N; i++) {
  • if (i == N - 1&&tmp!=A[i]) {
  • cntK[idx++] = cnt;
  • cntK[idx++] = 1;
  • break;
  • }
  • if (tmp != A[i]) {
  • tmp = A[i];
  • cntK[idx++] = cnt;
  • cnt = 1;
  • //ShowData(cntK, idx);
  • }
  • else {
  • cnt++;
  • if (i == N - 1)cntK[idx++] = cnt;
  • }
  • }

※QSortはここでは昇順のクイックソート。
配列に入力値全部突っ込んでからソートして頭から数値が連続している回数を別の配列に詰め直す。

???動きゃいいんだ

その後は出現回数を降順ソートしてcntK[K]~cntK[N-1]までの値を足していって出力。
数え方があほなだけでやってること実質同じだからセーフ。出現数数えるってよくあると思うんですけど。



D問題beta.atcoder.jp/contests/abc081/tasks/arc086_b

N個の整数(数列a)が与えられる。
ayにaxを足す操作を繰り返してa1≦a2≦・・・≦aN-1≦aNとする。(操作は0回以上2N回以下)
出力は操作の回数と空白区切りのx,yの組み合わせを操作した分。
なんとなく左から全部足してけばいいのではと思ったが今回aは-106≦ai≦106なのでaが全部正の時しか成り立たない。
そんなわけでしばらく正の固まりと負の固まりで~とかなんかてきとーなこと考えていたわけだが操作回数は2N以下とあるのでこれ全体に対する操作2回やるだけでよさそうなんだよなーと思い直し。
最初の全部足していく考えは最大N-1回の足し算なので全体に対する操作N回で全部正の状態に持っていければいける。
そういえば全部負でも逆順で足していけばできる。
絶対値が一番大きい数を足せば正か負に必ずできる。(全部0は例外)
なんかできた。

そんなわけで上に書いたのを実装して提出したらなぜかWA。
出力の仕方悪かったのかと思ってちょい直してもWA。というかなぜかサンプルでWAになってるやつがある。
実際に動かして出力を脳内操作してもちゃんと昇順になるのになぜだ・・・と思ってたらyとxが逆になってました。完。

そんなわけでレート推移
https://screenshots.firefoxusercontent.com/images/1ceea913-6a11-464d-8c30-d3a8d1b601ef.png


最近割りと真面目にやり始めてるのでいい感じに伸びてますね。
ARCはまだ早いと思いますが今のABC感覚で参加できるようになれればなーと思います。






11 | 2018/12 | 01
Su Mo Tu We Th Fr Sa
- - - - - - 1
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25 26 27 28 29
30 31 - - - - -
プロフィール

yy

Author:yy

最新記事
最新コメント
月別アーカイブ
カテゴリ
リンク
検索フォーム
ブロとも申請フォーム

この人とブロともになる

QRコード
QR
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。