FC2ブログ

スポンサーサイト

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

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感覚で参加できるようになれればなーと思います。






スポンサーサイト

comment

管理者にだけ表示を許可する

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ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。