競プロっておいしいの？(仮)

ARC 087 参加記録

CombNaf、明日！！！！

さて、DまでACしたので解説書いて明日の準備します。

ただ、D問題まで行くの時間かけて負けです負け。

明日CombNafなので準備したいですね。

あとyukicoderの Advent Contest、私の担当が明日ですので、

このあと、yukicoderも良ければ覗いてください。

(あの問題は、私の後輩に身に着けて欲しいテクニックで解ける問題を出題しました)

C問題

  1. まずソート。
  2. 種類を数える
  3. 数えた種類がその数と同じでないときに処理を挟む
  4. その数より多いときは差の分だけ
    その数より少ないときは個数分を
    ansに足し算
  5. おわり。

D問題

JOI過去問 - 1年生 (A First Grader)

が類題です、

DPでメモする意味がわからなかったが、添字メモったら一発で通ってクソかよｗｗｗｗｗとなりました。

boolDPを書いてしまいました。

  1. まず、X座標とY座標を分解します。
  2. Tが出てきたらX座標とY座標を交換する
    要は FFF T FF T F T Fなら(X座標3,1:Y座標2,1)分動ける
    (プラマイどっちにも行けるが、初手Xだけプラスのみ)
  3. ここで a+or-b+or-c+or-... =X(Y)にできるかどうかのDPをする
  4. DP(int a,int b)と取ったときに、aが何個目を見ているか、bがa-1個目までの和を表しています。
  5. それをやるとうまくいきます
  6. XのDPは(1,A[0])としないと初手マイナスという不適なものをカウントしてしまうのでNG。YのDPはDP(0,0)でOK

こんな感じです。

詳しくはソースを読んで下さいな。

Submission #1878367 - AtCoder Regular Contest 087

おまけ。レート

f:id:nafmo17:20171216231404j:plain

 

perf. : 1593
rate : 1240 (+48) highest!!

水色になれました。ありがとうございます！！！！！

あの水色ってきれいだよね。(競プロ!! AdC)

競技プログラミング Advent Calendar

競プロ、それは魔窟。

何言ってるかわかりませんね。私もわかりません。どうもNafmoです。

今回は競技プログラミング Advent Calendarに参加させていただくことになりました。これは16日目の記事です。

続きを読む

ABC 080 参加記録。

ABC AtCoder 競技プログラミング

ごめんなさい。

ちょっと今回は雑です。時間ないので。

A問題

ans=min(B,N*A);

B問題

cin>>S;
N=stoi(S);
for(auto x:S){
    A+=int(x-'0');
}
cout<<(N%A==0?"Yes":"No");

C問題

日本語読めませんでした。

要はやるやらないを10コマ試せば良い

2^10(ただし全部やらない1通りを引く)分だけ全探索。

Bitですね。

D問題

これを丁寧に書きたい。

いもす法 を使って終わりですね。(いもす法解説ページのリンク)

0.5なので、2倍したらいい感じになる。...さて。私は別の解き方でときました。

Nafmo's Answer (ソースコード)

私は普通にいもす法をした後に、開始終了時刻をチャンネルごとにsetにぶち込み、録画が終わる時間で、次の録画が同じチャンネルかどうかをsetで調べました。

同じでない場合はtemp++をして加算します(録画機を増やすしかないため)

最後は ansとA[i]+tempで最大値比較

とやるとかぶりを発掘できてうまくやれます。

暇ができたら丁寧に書きますね。

わからなかったら @Nafmo2 まで聞いてくださいな。

おまけ。レート。

はい。

perf. : 1370
rate : 1176 (+24) highest!!

 

ABC 079 参加記録

全完じゃああああああああ

お久しぶりです、全完さん。

わかりやすさを心がけていきたいですね。

デザイン簡略化していきまーす

A問題

後ろ3桁は1000で割ったあまり。

前3桁は10で割ればいい(切り捨てなので)

三項演算子を用いて

((A/10)%111==0||(A%1000)%111==0)?"Yes":"No";

B問題

素直に書きました

if(0,1)だけ例外処理

ans=a+b

b=a,a=ans;

を回しまくります。

long longに変数を統一しないとオーバーフローします(int 混ぜないでね)

C問題

A+-B+-C+-Dを素直にべた書きしてください。こっちのほうが早いです。

私は、Bit全探索を書きました。

 参考情報

D問題

問題概要と解釈

  1. 書いてあるすべての数を1にしたい。
  2. 全体でいくらコストかかるか求めよ。
  3. 1になれるのはすべての数。
  4. コストが羅列されている

  5. こんな感じなのが全てに生えていると言える
    すべての数に魔法が使えてなれるので
    (中心が変わったものが全てにある)

  6. あれ？これ、グラフっぽくないか？
  7. 一番小さいコストを求める、ということは、
    どこか経由してもいいから、結果1にできればいいよね。

  8. あれ？全部の頂点との最短距離求められるのでは？

  9. 各頂点から1までの距離が、コストでは...？
  10. できるじゃん！！！

というわけで、ワーシャルフロイド書きます。

で、ワーシャルフロイドの解説は別で書くかもしれません

 このリンクのソースは私のソースだった()

ワーシャルフロイド回して、d[a][1]を平面操作します(aは書いてある数値(-1はスルーする))

これで通せます。

おまけ。レート。Highest

 

 

 わーい

JOI 2010 本選 3 つらら

JOI AtCoder 競技プログラミング

え？私覚醒した？

†DP†で通しました。

解法書きまーす

問題概要

  1. N本つららが並んでいます
  2. 両脇のつららよりながければ、1cm/hで伸びる
  3. Lまで行くと折れる
  4. さて全部折れるまで何時間？

  5. https://www.ioi-jp.org/joi/2009/2010-ho-prob_and_sol/2010-ho.pdf

解法

両脇が折れる時間+L-今見てるところの長さでその見てるところの長さは出せる

じゃあどうするか。再帰っぽい。

あれ？DPじゃね？

空からDP解法が降ってきた。

両脇より高ければ L-A[i]でreturn

どっちも高かったら低い方だけ見ればいい

どっちかだけ高かったら高い方だけみればいい

みたいなことやって全探索したら幸せになれました

Submission #1681110

DP解、つらい。

でもなんかできて嬉しかった。

プライオリティーキュー解もあるのでそっちも考えてみるといいかもです