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

ABC190 参加記

AtCoder Beginner Contest 190

お疲れさまでした．今回も書きます．
D問題がかなり好きでした．

A:Very Very Primitive Game

これは先手視点で考えると，相手より多くのアメを持ってないと勝てません．それを先手2パターンについて場合分けをして書くとできます．

B:Magic 3

これは単純に条件を満たすものを前から探すだけです.....
素直に見ましょう.....

C:Bowls and Dishes

これはbit全探索をします． 0,1でC,Dのどちらを選ぶかというのを対応させて全探索をします．すると2N通りだけ試し，最後に条件M個を見て条件を満たしているか調べればよく，計算量的にも間に合うので，解けると言った感じになります．

bit全探索の参考(過去に作った問題) yukicoder.me

D:Staircase Sequences

N=\frac{n(2a+(n-1)d)}{2} を使います． nを項数として，dを公差，aを初項とし，d=1として変形すると 2N/n-(n-1)=2aと変形できるので2Nを素因数分解して，nを列挙し，nを代入した時に左辺が2で割り切れればaが整数で存在し，数列が構築できるので，それを満たすnの数を数えると答えになるという問題．かなり好き．

E以降

復習がんばります......

それではお疲れさまでした．

ABC189 参加記

AtCoder Beginner Contest 189

お久しぶりです．Nafmoです．Nafmoって名乗る回数も減りましたね...
さて，久しぶりに参加記を書きたくなったので書きます．理由としてはアウトプットしてミスを減らそうという流れですね．

f:id:nafmo17:20210123225419p:plain

A:Slot

これはstringで受け取ってS[0]==S[1]==S[2]を判定するだけです．

B:Alcoholic

これです．教訓ですが...

小数を小数のまま扱わない
でしたね．

割り算は誤差を生みます．主に2n以外で割ると厳しいはずです(ほんまか？)そのため割るのではなくすべての値に掛け算をします．すると大小関係は保持されるので問題なく処理できます．今回の場合は，%で表示されているため，100で割らずに残りの値(上限X)に100を掛けてあげれば問題なしです．後は単純にシミュレーションをすればいいだけです．

C:Mandarin Orange

これは全探索をします． 二重ループを使って，1重目で範囲の始点を決め，その要素を持ちます．そこから2重目で範囲の終点を決めます．その際に，先の保持している要素と比べ小さい方を持ちます．こうして範囲をスライドしながら最小値を更新します．要素数は1でも問題ないです．範囲の数とその最小値の値をかけたものの最大値が答えです．

範囲の中にある最小値✕範囲 がその領域をいっぱいいっぱい使うときの最善のはずだからです．

D:Logical Expression

これはメモ化再帰を使いました． DP(n,y)という関数としたときに，n個目までで，yが1(true) or 0(false)になるときの{x1,x2...xn}のパターン数を返す関数としました．

  • n個目のyがtrueのとき
    • ANDのときはn-1個目のyがtrueでなくてはならない
    • ORのときはn-1個目のyがtrueなら2パターン，falseなら1パターン存在する
  • n個目のyがfalseのとき
    • ANDのときはn-1個目のyがtrueなら2パターン，falseなら2パターン存在する
    • ORのときはn-1個目のyがfalseでなくてはいけない のような形で掛け算をしてメモ化をするとできます．

E以降

復習がんばります......

目標は水色！頑張るぞい！ f:id:nafmo17:20210123232147p:plain

ABC173 参加記

自分の弱さと母集団の上昇を感じる

どもーNafmoです．精進を再開しましたがなかなか思うように結果が出ませんね． DEは解き直したら追加します．しばしお待ちを(感想だけ先にブログ化しちゃう) 精進不足を感じています．頑張りたい

A Payment

1000-1000で割ったあまりです．ただ，これをすると1000という結果が出る場合がありますが，それは割り切れてるのでお釣りは0です．そこの分岐だけしましょう．

B Judge Status Summary

逐一AC WA TLE RE のどれに対応してるかif文で分岐して数を数えるだけ
C++のmapでキーと対応させてあげると早いかもしれません(連想配列)

C H and V

bit全探索を2回します．2H * 2W で2W+H乗ですが,W+Hが12以下なので間に合います．
どの列を選ぶのかどうかの組み合わせをbitの01に対応させて，行でも同じことをします．そのあと，選択した行と列に関して黒の数を数えて，全体の黒の数から引きます．その際にダブルカウント(ちょうど十字がクロスするところで起こる)してるところのケアを忘れずにして終わり．

D Chat in a Circle

ソートして上から見ていくのが正しそう．ある数についてその配列にある数回だけ追加できそうだなぁと思ったんですけど反例だらけ，時間を溶かしたがとりあえず次を読んだ，

E Multiplication 4

正の数と負の数に分けてしゃくとりしたいなぁ，負の数は2ずつindexをすすめると良さそう...と思ってたのですが，全部付の場合や，負の数しか作れず絶対値の最小かつ負という可能性が存在することに気づき反例が大量に出てきて手が止まった．

全体感想

いやー辛いですね．まだまだ精進が足りてないみたい．
もっと溶けるように頑張って精進します． 今週中にはDE通したいですね．

ABC172 参加記

ABC AtCoder 競技プログラミング

お久しぶりです。

久々に競プロ界隈に戻ってきたのでいつもどおりアウトプットをします。これは自分の感じたこと，考えたやり方を記録するのが目的です。

続きを読む

受験記。と高校生活を振り返る†禊†

受験、終了。

 ありがとうございました。

これから受験勉強パートと、その他パートで高校生活を振り返ります。

受験パートだけ参考にしたい人がいるのでそこだけ先に簡潔にまとめます。

残りは書きたいように書くので読みやすさは求めないでください。ここに文字に起こすことで、区切りをつけたいという自己満足の塊です。そのため、あいつのあれ見た？意味わかんなくね？みたいな晒しや大声で言及はちょっと避けてもらえると嬉しい、書きなぐりなので許してほしい。(執筆時間21:00～一発書き)

それでは行きますか。理系の話をします。数学多めです。

あとは一応先取りカリキュラムの話になってしまうんですけれど、そこはうまく読み替えてください...

※あくまで1個人の意見と結果論です。参考にできるとこだけ参考にしてください。正しさは保証できないので、これを実践してなにかに悪影響を及ぼしても責任はおえません...

続きを読む

ABC096 参加記録

はー？頭悪いかよ。

というわけで全完しました。Nafmoです。

来月これやります。今日公開になりました。

きてね！

A問題。

5/4までは 4コ
5/5からは 5コ

それなら 月<=日で月 それ以外で月-1で答え。

はい。

B問題

sortして後ろの最大値をK回2倍します。

全部足して終わり。

C問題。

ある黒マスの上下左右に黒マスがなければNo

それ以外はYes

理由としては黒マスと重ねられるからってことで。

D問題。

最初に出力した数字

「5637」

これは55555以下の素数の数だ。

次に考えたこと。それは

奇数同士足せば偶数だな...行けるじゃん！！！！

任意の組み合わせについて満たさない為ダメ。

 

どうしよう....ないなぁ...

5*6とかで... 6 6 6 6 6 とかで生成できないかしら.....

できねー。2ヶ月ぶりの競プロは険しいわｗｗｗｗｗ

f:id:nafmo17:20180505222721j:plain

空から解法降って

ｷﾀ━━━━━━(ﾟ∀ﾟ)━━━━━━ !!!!!

1 1 1 1 1 で5の倍数にすればいいんや。

1の位1のやつの素数の数は...

「1408」

ｷﾀ━━━ヽ(∀ﾟ )人(ﾟ∀ﾟ)人( ﾟ∀)人(∀ﾟ )人(ﾟ∀ﾟ)人( ﾟ∀)ノ━━━!!!!

勝ちました。勝ちましたよ。勝ち勝ち。

5行実装で終了。

 レートグラフ

更新されたら貼ります。多分下がる。