jj1gujのブログ

アイコン画像は音速の奇行子 様よりいただきました

ABC160参加

プログラミング 競技プログラミング

ABC157に参加しました.
結果はこちら
Fortranで5完でした.
やったね！

A問題

問題文のとおりに実装しました.

B問題

$X$を500で割ったあまりを$Y$としたときに$1000 \times \lfloor X/500 \rfloor +5 \times \lfloor Y/5 \rfloor$を出力しました.

C問題

なんか考察中に頭の中がごちゃごちゃになって無限に時間を書けてしまいました…
結局隣同士の家の距離を求めて, その距離の総和から最も大きい隣同士の距離を引きました.

D問題

これもC問題で無限に時間を書けてしまった焦りから頭の中がごちゃごちゃになってしまっていました...
今回制約が$2 \times 10 ^ 3$で二重ループをかけられるので各点$i$から, その点の右側にある点$j$までの最短距離を$\min ( j-i, abs(i-X)+abs(j-Y)+1)$で求め, 合計を求めました.

E問題

実はD問題解いてるときに問題文を読んでてなんか解けそうな気はしていました...
結局無色のりんごは赤リンゴにも青りんごにもなれるので, 最初に$P$から大きい順に$X$個, $Q$から大きい順に$Y$個取り出し, 1つの配列$S$に格納しておきます. そうするとABCの過去問にありそうな$S$の要素を$R$の要素で書き換えて$S$の総和を最大化する問題になるのであとはこれを解けばよいです.

今回C問題AC時に冷えることがほぼ決定していてかなり焦っていました. しかし, なんとか終了間際にE問題まで通すことができて本当に良かったです！！ Cに時間をかけてしまったのは正直精進不足だとおもいます.
これからはCまで20分以内に安定して解けるように頑張ります！！

ABC159参加

プログラミング 競技プログラミング

ABC159に参加しました！！ コンテスト結果は[こちら]( Fortranで2完, Pythonで2完でした.

A問題

Fortranで通しました.
2つの数の和が偶数になる組み合わせは (偶数)+(偶数)と (奇数)+(奇数)しかないため {} _ N C _ {2} + {} _ M C _ {2}を出力しました.

B問題

最初に与えられた文字列が回文か判定し, その後真ん中を除いた前半分と後ろ半分がそれぞれ回文かを判定しました.

C問題

サンプルからエスパーして ( \frac{L}{3} ) ^ 3を出力しました.

D問題

あらかじめ全ての組み合わせ Bを計算し, 与えられた Aに含まれる各 A _ {i}の登場回数を数えておきます.
これを C _ {i}としたときに B- {} _ {C _ {i} } C _ {2}+{} _ {C _ {i}-1 } C _ {2}を出力しました.


なんか今日のA問題, むずかしくなかったですか？ぼくはむずかしいとおもいました.
とりあえず今回1日未満で緑色に復帰することができました！
次は落ちないように気をつけたいです. まる.

f:id:jj1guj:20200322231645p:plain
緑復帰RTA成功！

AtCoderで茶色になった

競技プログラミング プログラミング

AtCoderで茶色になりました！！
や　っ　た　ね
コンテスト成績はこちら

どうして…どうしてこうなった

今日のAGCでA問題見たらかCafeCoderで見たことあるような雰囲気だったのでそのままDPしたらWAになりました.
問題文はしっかり読もうね.


とりあえず明日のABCで色変します()
問題文の誤読には気をつけましょう

f:id:jj1guj:20200322000036j:plain
みんな、気をつけような…

AtCoderで緑色になった

プログラミング 競技プログラミング

昨日あった日立製作所社会システム事業部プログラミングコンテスト2020*1でとうとう！緑色に！！なりました！！！や　っ　た　ね！！！！！！！
コンテスト成績はこちら
ってことで念願の色変記事を書いていきます*2.

はじめたきっかけ

もともとB1の頃からプログラミングを始めてて五目並べやオセロソフトを作ってました.
一応自分のアルゴリズム能力とかそこら辺を伸ばすためにAOJをポツポツとやってました.
AtCoderの存在もB2あたりで知ったのですがなかなか始められませんでした.
B3になったくらいの頃にたまたまこの記事を読んで面白そうだなぁって思って始めました.

note.com

茶色になるまで

とりあえず10回以上参加しないとレーティングが低く出てしまうのでだいたいそのくらいまでに茶色になりたいなぁって思いながら特に何も考えずにやってました.
最初はPythonでやってて途中から速さが欲しくなったのでC++やCも使うようになりました*3.
一応数学問題にそこそこ強く4完水パフォ取ったこともあって2回連続unrated回引き当てたことはあったものの特にこれといった苦労はなくrated10回参加で茶色になりました.

できるようになったこと

  • 大まかな計算量の見積もり
  • Pythonでの {} _ n C _ {r}の計算方法

茶色~緑色*4

7月〜9月

茶色になって最初のABCでいきなり6ペナ3完とやらかす.

Contest Result - AtCoder

その後最強学生コンでバイト帰りか何かののスマホコーディングで3ペナ1完75分をやらかし激冷えしました.
そこそこプログラムを書ける人であれば灰色の間はスマホコーディングでやらかしても多少はレートは上がると思うのですが*5 茶色になったら確実に冷えます.
スマホコーディング, ダメ！ゼッタイ！
その後のABCでまたやらかしました.
これで合わせて100近くレートが下がりました…
その後ぽつぽつとレートは上げ, 9月末にはHighest近くまでレートを復帰させたもののまぁ自分の適性ここらへんかなぁ…と思いつつやってました*6.

転機となったのが最強学生コン本選イベントです.
そこでAtCoder緑色はp◯izaのSランクとだいたい一緒というのを聞き, 更にエンカした人たちがみんな強くてぼくもそこまで行きたいと思うようになりました.

f:id:jj1guj:20200309205947j:plain
電通さん, ありがとう！
ただ, あまりにも実力のなさを痛感していたためこれをきっかけに学類を卒業するまでに緑色になることを決めました.

やったこと

  • レートの劇冷え()
  • スマホコーディング
  • 緑を目指す決心*7

10月〜12月

で, 何を始めたかというとFortranのお勉強です！(は？)
もともとC++よりも速いという噂を聞いていたこと, あんましやってる人がいないこと, そして現在もシミュレーションに使用されている言語であることからやってみたいと思っていました.
そしてただお勉強するだけではつまらないのでFortranを使ってABCのA問題〜C問題を埋め始めました*8.
おかげでもともとC問題まで30分くらいかかっていたのが15~20分くらいまでに短縮できました.
更に, ABC144(話題のWater Bottle回)でWater Bottleを数学で殴って50分4完したことでとてもあったまりました！*9やったね！
まぁその後はちょっと冷やしつつも停滞する日々が続きました(適当).
あとはブログを書き始めました.
ただ全然強くもなければ説明するのも上手くないのでそのとき頭の中でどう考えていたか垂れ流すだけ垂れ流すことにしました.

正直ブログに関しては効果のほどはわかりません(正直これで強くなってる実感はない気がする…)が, Fortranのお勉強は割とおすすめです！
というのも速さはC++と同等かそれ以上でソードのライブラリ等用意しておけばC++よりもコード長がスッキリするからです*10(もちろん諸説あり. というか全方位から怒られそう).

やったこと

  • Fortranのお勉強
  • ABCのA~C埋め
  • ブログ

1月〜2月

確かここらへんでだいぶ緑化が見えてきたので目標時期を3月末に変更することにしました.
そして, EDPCの問題をちょいちょい解きつつDPのお勉強を始めました.
なぜDPにしたかというとCafeCoderでDPっぽい問題が出てコンテスト中に解けて気をよくしたからですね().
そのおかげでABC153で5完40分水パフォでほぼほぼ緑へのマジックが点灯しました！
そこで目標時期を2月末に変更しました.



が, 2月はレートを劇冷えさせ, それを回復させるだけで終わってしまいました…
特にABC156のD問題で解法が5分くらいで浮かんだにも関わらずmodの逆元をよく知らなかったために実装できずに終わってしまったのが痛かったです.
更に追い討ちをかけるようにこの回でぼくよりあとから始めたサークルの1年生に抜かされてしまいました…*11
ただ悪いことばかり起きたわけではなくなんだかんだでFortranのLanguage Owners第3位になったりFortranのAC数が200を超えたりしてました*12.
この頃お年玉が入ったので蟻本を買ってちょいちょいお勉強を始めました.

やったこと

  • DPのお勉強
  • modの逆元のお勉強
  • 蟻本🐜

3月

とりあえずもうできるだけ早く緑化することを目標にして戦略を立てました.
戦略としては3/1にABCが生えてたのでここでなんとか最低でもパフォ1000で緑化できるくらいに上げて日立コンで早解き勝負を挑むというものです.
3/1のABC156でなんとか緑直前まで上げられたためかなり望みが見えました.
そして, 直前に生えたABC157はパスして昨日の日立コンに臨みました.
そしてこれが見事にはまってやっと緑色になれました！！

twitter.com

ただのクソ長いポエムになったのでまとめ

できるようになったこと

かなり調子こいてるけど緑色を目指す人たちへ

なんだかんだ精進してる時とか気分じゃないときは休んだりさぼったりしてたので無理やり精進しなきゃって思うよりも楽しんでやるといいと思います！

今後の目標

目標としてはとりあえず茶色に戻らないようにすること*13, そして年内にレートを1000まで上げることです.
正直今の実力だと適正がよくて900弱くらいだと思ってるので蟻本や銀髪赤眼本使って精進したいと思います！

*1:名前長くないと思いませんか??ぼくは思います

*2:そもそも色変記事を書くこと自体が目的になっちゃってる感あるのでそんなに参考にならない気がする…

*3:まぁC++使い始めてからはほとんど使ってない

*4:ここが色々やらかしててもうほんとひどい

*5:あくまで個人の感想です

*6:夏休み中, 劇冷えさせて元に戻して終わったので虚無だった…

*7:そんなに重い感じじゃなくてなりたいなぁ〜って感じ

*8:真面目に精進してないのでまだ埋まってないです…ﾕﾙｼﾃ…

*9:こるとんさん, ありがとう

*10:いつかFortran布教記事書きたい

*11:というか入学当初プログラミングできない状態だったのに1年も経たずにここまで伸びるとか異常じゃないですか⁇

*12:2位との落差がすごい

*13:predictorで見てみたらパフォ400取らない限り大丈夫らしい(フラグ)

ABC157参加

ABC157に参加しました.
結果はこちら
Fortranで1完, C++で1完, Python3で1完でした.

A問題

Fortranで出しました.
\lceil N/2 \rceilを出力して終わりでした.

B問題

C++で出しました. とりあえずゴリゴリ実装しました.
ビンゴで穴が開いた箇所を1とし, 穴が開いていない箇所を0とした配列を用意し, 縦・横・斜めの和をとって3になる箇所があるときにYesと出力するようにしました.
最初, Fortranで実装したのですが何故か動かなあったのでC++で実装し直しました.

C問題

Python3で出しました.
出力する数の各桁の数を要素とした配列を用意しました.
その後, 入力に従って配列の要素を操作しました.


D問題, E問題はデータ構造の知識問題っぽいところがあったっぽいですね…
もっと精進しておくべきでしたね…
今回で緑直前まで来たので次回上がれるようにがんばります.

ABC156参加

プログラミング 競技プログラミング

ABC156に参加しました.
結果はこちら
Fortranで3完でした.

A問題

$N \leq 10$なら$R+100(10-K)$を, それ以外なら$R$を出力して終わりでした.

B問題

$N$を$K$で何回割れるか数えて回数を出力して終わりでした.

C問題

$N$, $X _ {i}$共に小さかったので$P$を$X _ {i}$の最小値から$X _ {i}$の最大値まで回してその時の消費する体力の総和で最も小さくなるものを出力して終わりでした.

D問題

問題文読んでから5分くらいで$2 ^ {n} - {} _ n C _ {a} - {} _ n C _ {b} -1$を計算すればいいことは見えたのですが, ${} _ n C _ {r}$を$10 ^ {9}+7$で割ったあまりの求め方がわからなくてずっと求め方を調べていたら終わってしまいました.
悲しい.


今回, D問題の考察までかなりいいペースだったのに実装でやられてしまいました.
もしコンテスト開始20分くらいでD問題まで通していたらパフォーマンスが1400行ってたので緑化してたようです…
悔しすぎてキレそう…
達成できたのにできなかった…↓

コンテスト終了後ひたすら発狂してました…
今回ライブラリを持っておくことの重要性を身を持って実感したので今日明日にもmodのライブラリ実装します…
3/1にABC生えてくれぇぇぇぇぇ

ABC155参加

プログラミング 競技プログラミング

なんだかんだ書いてなかったので書きます.
ABC155に参加しました.
結果はこちら.
自分でも驚くほど激冷えしました.
今回はFortranで2完, Python3で1完でした.

A問題

入力された変数を配列に格納→ソート→隣同士で同じものがあってかつみんな同じじゃないか判定しました.

B問題

先頭から順に見て問題文のとおりに判定しました.

C問題

かっこつけてPythonで辞書型使ったらバグりました(敗因).
最終的にソートして隣同士が違うものになるまで足し算して出現回数を数え, 出現回数の最も多かったものを辞書順に出力しました.


かっこつけちゃだめですね…
(これ以上の感想が出てこない...)