AtCoder Beginner Contest 178 参加記
2020/9/13に開催されたAtCoder Beginner Contest 178に参加しました。
先週はコンテストがなかったので、ABCの過去問などで精進してました。
そろそろ精進の結果が出てきて欲しいところです。
AtCoder Beginner Contest 178 - AtCoder https://t.co/VxvruZFTpG
— devgenjin77 (@devgenjin77) 2020年9月13日
2週間ぶりのABC。パフォーマンス落とさない様頑張ります。
今回の結果
で、肝心の結果ですが、今回は2完を喰らってしまいました。(T_T)
パフォーマンスは相当悪化するかと思いましたが、微減で勘弁してくれました。
残念ながら今回2完でした。これに懲りずに次回頑張ります。
— devgenjin77 (@devgenjin77) 2020年9月13日
devgenjin77さんのAtCoder Beginner Contest 178での成績：5612位
パフォーマンス：521相当
レーティング：577→570 (-7) :(#AtCoder #ABC178 https://t.co/04RiPu6u57
振り返り
C問題以降全く歯が立たずでした。
A問題
条件分岐の基本問題みたいなものでした。問題なくAC。
B問題
問題文を一読して、条件分岐面倒くさそー！と思った。
しかし、よくよく考えると、どんな条件でもの候補としては
か
が、
の候補としては
か
を採用することになるので、それぞれの掛け算の結果のmaxを取れば良いことに気づいた。
方針が決まれば、あとは実装するだけでAC。
C問題
この問題でドツボにハマってしまいました。。
問題にある条件のうち、例えばとなる
が存在する条件を満たすものの数え方を完全に間違えてしまい、その結果、出力がサンプルのケースに全く合わないので焦ってしまいました。
その後も修正が効かず、結局この問題で大幅に時間を消費して解けずでした。
D問題
問題を一読して、組み合わせ論の問題かと思いましたが、それ以上の考察が全く進みませんでした。
終了後解説を読むと、どうもDPで解決できる問題だということらしいということがわかりましたが、こういう問題をノーヒントで解ける様になりたいと思います。
E問題
これも解法がわからんかったが、どうも過去に類似の問題があったようです。
同種問題が過去にあったかを早く調べることが重要であるとの知見を得ました。
F問題
他の問題に時間取られすぎて、全く考察できずでした。また時間をとって解説ACをすることにします。
これまでの実績
茶色レーティングで停滞のムードが漂ってますな。
総括
最近あまり勉強してなかった組み合わせ論の問題でドツボにハマりました。
しかし、ここ最近の結果をみても、なんだかんだで自分の実力通りの結果が正直にでているような印象があるので、良い結果を収めるには精進していくしかないかと。
次回も懲りずに頑張ります。
ABC177参加記
2020/8/29に開催されたABC177に参加しました。
前日まで開催が確定してなかったんで少し不安でしたが、なんとか開催していただけたのでよかったです。最近良い結果が出てないので、今度こそレートが上がる様にという気持ちで臨みました。
AtCoder Beginner Contest 177 - AtCoder https://t.co/mgj1bIDwmc
— devgenjin77 (@devgenjin77) 2020年8月29日
参加します。最近停滞気味なのでなんとか4完以上めざします。
今回の結果
で、今回は久々の4完達成でした！
緑パフォーマンスで久々にレーティングが上がりました！
devgenjin77さんのAtCoder Beginner Contest 177での成績：3728位
— devgenjin77 (@devgenjin77) 2020年8月29日
パフォーマンス：826相当
レーティング：540→577 (+37) :)#AtCoder #ABC177 https://t.co/1CuH9EU0Yv
久々の4完でレートも少し上昇。このパフォーマンスを維持できるよう精進します。
振り返り
あわや今回も3完どまりかというとこで、D問題に助けられました。
A問題
ならNoを出力。それ以外はYesを出力する。
問題なくAC。
B問題
問題を一目見た瞬間、難しめの問題か？と思ったが、ゴリ押しでやれば問題なかった。
先ずの先頭から
を比較して、異なる文字数をカウント。あとは
との比較開始位置を1つずつ右にずらして同じことをしていけばOK。
配列外へのアクセスがない様慎重に実装してAC。
C問題
愚直にやるとTLEになる系の問題。整理すれば簡単だった。以下考察。
と仮定した時、求めるべき答えは以下になる。
これは以下の式に変形できる。
よくみると、配列の後ろの要素の累積和とその一つ前の要素を掛けたもので構成されてることがわかる。この性質を活用すると計算量が減らせる。
あとは、modの計算に気をつけて実装してAC。
ここまで開始30分弱で3完。今度こその4完を目指してあとの問題に目を通してみた。
D問題は、Union-Findを使う系という印象。でもUnion-Findを実装したことないw
E問題は、GCDというか、素因数分解で解いてく問題かな？という印象。
F問題は、一読して何が言いたいのかがよくわからんからパス（笑）
以上から、とりあえずE問題に取り組むことにした。
E問題
で、とりあえず考察してみたものの、上手い解法が思いつかず。。
苦しまぎれに、入力の数列をソートしてから、配列の最小値以下の奇数と2で、それぞれ数列内の数字が何個割り切れるかで場合分けすればなんとかなるんじゃないかいう雑な考察で実装し、なんとかサンプルを通すコードを作成。
で、、これが実際投げてみるとTLEとWAのダブルパンチを喰らってしまったw
んで、気づけばもう1時間近くこの問題で浪費している。
ここから修正しようにも、WAはともかく、TLEの回避は無理ということで、あえなくE問題から撤退。
D問題
ダメ元でD問題に帰ってきた。
改めてこの問題を考察すると、とりあえずUnion-Find木を作って連結成分サイズの最大値を返せばいいんじゃね、ということに気づいた。
もう残り時間も少ないので、ここはUnion-Find木を使ってそうな過去問からACしてるソースを漁ってきてコピペするという戦略をとることにしたw
ちょうど当日の昼に考察していた問題がそれに該当したので、あとは使えそうなコードから不要部分の削除と出力の変更を行い、ギリギリサンプルが通ることを確認してから投げたらなんとかAC！
あーD問題先にやっとけば良かったわ（笑）
F問題
F - I hate Shortest Path Problem
コンテスト後に問題を読み返しましたが、未だに問題すら理解できてませんw
まあ、後日時間をとって取り組むことにします。
これまでの実績
総括
今回久々の4完でしたが、問題の難易度が低めだったことが幸いした結果だと思うので、まだまだ努力が必要だなーという感想です。次も頑張ります。
ABC176参加記
2020/8/22に開催されたABC176に参加しました。
ここ2回のABCは2完終了と残念な結果なんで、今回はなんとか3完以上取らんといかんなーという気持ちで参加しました。
参加します。最近2完続きなんで、今回こそ3完以上を！
— devgenjin77 (@devgenjin77) 2020年8月22日
AtCoder Beginner Contest 176 - AtCoder https://t.co/HehwL6NOPF
今回の結果
で、今回はなんとか3完達成しました。まあ一応ノルマ達成みたいなもんです。
パフォーマンスは現在のレーティングとほぼ同じ。レーティングは現状維持でした。
devgenjin77さんのAtCoder Beginner Contest 176での成績：5277位
— devgenjin77 (@devgenjin77) 2020年8月22日
パフォーマンス：553相当
レーティング：540→540 (±0) :|#AtCoder #ABC176 https://t.co/rsyeo5onPZ
3完茶パフォで現状維持でした。2完を脱出できたのでまあ良しとします。
振り返り
3完までは順調でしたが、それ以降がダメダメでした。
A問題
N÷Xを切り上げた値にTを掛ければよい。
が、、最近割り算の切り上げとかプログラムでやったことなかったので、剰余があるかどうかのIF文を入れてなんとかAC。
B問題
各桁の数字を足し合わせて 9の倍数かを判定する問題。これは特に問題なくAC。
C問題
最近鬼門のC問題だが、問題文をみた瞬間、結構簡単そうにみえたので一瞬目を疑ってしまった。
配列を前からみていって、直前の人が身長が高い場合、その高さの差を合計に足し込んでいけばOK。
検証に少し時間をかけたが一発でAC。
D問題
20分ちょいでC問題完了という、個人的には結構なペースでここまで進みましたが、こっから停滞しました。
問題文をみる限り、迷路探索でBFSを使う典型問題の感じでしたが、ワープの条件の実装で大分悩んでしまいました。
結局、色々悩んで時間を潰した挙句、残り10分となったところで、毎回ワープできる時はワープするという、大分効率が悪そうなコードを投げてみたが、それが通るほど世の中甘くないようでTLEを喰らいました。(´・ω・`)
結局時間切れでこの問題は解けず。
E問題
D問題に固執しすぎてコンテスト中に問題文を読めなかったが、見た感じ自分でもなんとか解けそうな問題。なんでD飛ばしてE見なかったの？と一瞬後悔しました。（ま、実際はいうほど簡単ではなかったが。）
解法は以下の通り。
爆破対象を行、列ごとにカウントする。爆破対象が最大数存在する行と列の交点が爆弾の設置候補となる。
つぎに、全ての爆破対象の位置より、その行、列にある爆破対象の数が先に計算したそれぞれの最大数と両方一致するかをみる。
爆弾の設置候補の数と、行と列両方爆破対象が最大数となる爆破対象の数が一致したら、全ての設置候補が爆破対象になるので答えは行列それぞれの最大数を足して1を引けばよい。一致しない場合は、1を引かなくて良い。
この問題は、コンテスト後にACしました。
F問題
コンテスト中に問題が読めなかったが、なんかAGCに出てきそうな感じの問題。解説をみて大分難しそうでしたが、今週中には時間をとって実装しようかと思ってます。
これまでの実績
8月にはいってから相当停滞気味です。精進はしてるんだが、結果が出ないなー。
総括
今回はなんとか3完達成でしたが、今回の問題の難易度からいうと決して出来がよかったとは言えません。ここ最近はいい結果が出てないですが、諦めずに頑張ります。
ABC175参加記
2020/8/15に開催されたABC175に参加しました。
前回のABCでは2完でレート下げを喰らったので、今回はなんとか3完以上を目標にがんばってみることに。
参加します。前回は2完という残念な結果だったんで、最悪3完以上目指します。
— devgenjin77 (@devgenjin77) 2020年8月15日
AtCoder Beginner Contest 175 - AtCoder https://t.co/SfNhA3ddWr
今回の結果
で、肝心の結果ですが、2完で終了です。(´；ω；｀)
振り返り
C問題でWAを喰らいまくりでした。。
A問題
A問題にしては、少し難しめのこの問題。前回がRでRが連続したらカウンタをプラスするというような少し複雑なコードを出したら、バグってたらしくWAを喰らってしまいましたw
少し修正して、A問題としては少し遅めの6分台でAC。
B問題
3本の棒で三角形が作れるかどうかの条件は少し前に蟻本で見たので、それを参考になんとか実装。が、、それぞれの長さが異なる、という条件を見落としていてサンプルが通らずで時間がかかってしまう。
20分台でなんとかAC。
C問題
移動回数Kがケースによっては大きい数になるので、普通にシミュレーションすると、TLEになるかも。ということで、まず原点からの距離Xを、移動距離Dで割った結果で場合分けすればなんとかなるかという方針で実装。
しかし、サンプルを通した実装を提出するも、大量のWAを喰らってしまい、少しパニクってしまいましたw
その後は、アタリをつけて修正してはWAを食らうのボロボロな内容。 結局、最後の1ケースがどうしても通らずで結局コンテスト中には解けずでした。
結局、コンテスト後にイチから実装したらすんなりAC出来たので、難易度的に解けないという問題じゃなかったのですが、焦りからいろいろミスをやらかして、修正もきかなかったです。
D問題
Cが全然ACになる気配がなかったので、Dはなんとか行けるかと思い、問題に目を通してみた。とりあえず、移動経路に周期性があるので、1周あたりの合計とその余りを計算すればという感じで考えたが、実装が思いつかずでギブアップしました。
E問題
C,Dの出来が酷すぎたのでコンテスト中は何も出来ずでした。
F問題
コンテスト中は問題も読めなかった。。
今回の実績
2回連続でレート降下。ヤバイ！灰色落ちするかも。
総括
C,D問題が出来ずなのは、実装力が足りていないのが原因でしょう。過去問を解く回数を増やして、なんとか次回はいい結果が出せるように頑張ります。
AGC047参加記
2020/8/9に開催されたAGC047に参加しました。
AGCは過去3回参加して、0完、0完、1完という惨憺たる成績であり、自分もまだ茶色レートなのでunratedのコンテストですが、何事も勉強という思いで参加しました。
茶色だけど勉強がてら参加します。
— devgenjin77 (@devgenjin77) 2020年8月9日
AtCoder Grand Contest 047 - AtCoder https://t.co/CpRk9Jme4J
今回の結果
で、肝心の結果ですが、今回はあえなく0完で終了です。
本当にありがとうございました。
振り返り
A問題
300点問題なので、なんとか1時間ぐらいありゃ解けるかと思ってましたが、大きな間違い。
整数と小数部ありの実数ないまぜの入力が与えられ、掛け合わせると整数になる組み合わせは何通りかという問題。これが初手からの考察が間違っていました。
入力から整数部と小数部を切り分ければいいのではという方針で色々検討したものの、これが大分検討外れだと気づいた頃には1時間以上経過した後。結局入力から小数点を除いて掛け合わせ、あとで小数部を除くときに掛けた10のx乗で割り切れるかという判定でなんとかサンプルが通るプログラムが作れたものの、提出結果はTLE。。
入力がでかいケースもあるので、ScannerをBufferedReaderに変えれば、もう少しマシになるかと思ったが、これも全然ダメ。結局この辺で時間切れとなり、終了となりました。
結局コンテスト終了後、解説を読んでこの問題はACしましたが、入力を整数に変換した後、2と5で割れる回数を予め計算しておくというやり方が全く思いつかずというところでした。大分勉強になりました。
B問題
問題文までは読んだが、A問題が上記の有様だったので、まともな考察ができず、解法思いつかずでした。
C問題
問題も読めてません。
D問題
問題も読めてません。
E問題
問題も読めてません。
F問題
問題も読めてません。
今回の実績
画像は前回の使い回し。Rated対象ではないのでレート変化なしです。
総括
今回無念の0完でしたが、ツイッターのTLを眺めていると、結構上位レートの方も0完報告が多かったです。結構難易度高めだったということでしょうか。
まあ、いつまでもAGCクラスの問題が解けないままでは時間かけて競プロやってる意味もないと思うので、今回の問題も時間を見つけて解いていこうと思います。
ABC174参加記
2020/8/2に開催されたABC174に参加しました。
先々週、先週のコンテストでは3完以上できているので、今回も4完が目標という感じで挑みました。
参加します。今回も4完が目標ラインという感じで
— devgenjin77 (@devgenjin77) 2020年8月2日
AtCoder Beginner Contest 174 - AtCoder https://t.co/pnX83rw0o9
今回の結果
結果は、無念の2完終了です。。
振り返り
A問題
IF文一回書くだけのやるだけ問題。とくに詰まるところなくAC。
B問題
Dの2乗とAの2乗＋Bの2乗を比較する問題にすれば難しくない。これも問題なくAC。
C問題
まともに計算するとlongの範囲に収まらない計算問題。
コンテスト中に解法が思いつかず。
サンプルに出てくる999983とかに意味があるのではと、ググってみるも全然手がかりも出てこず。それではと、タイトルの単語も調べてみたが、これも全く意味不明。。
結局、コンテスト後解説ACをしましたが、タイトルの意味は全くわかりませんでした。
D問題
これもコンテスト中に解法が思いつかなかった問題。しかし、解説を見てみると非常に単純に思える問題でした。この種の問題で解法が思いつかないのも経験値が足りんからかなーと思ってしまいます。
E問題
コンテスト中に問題文だけ読んで、なんか似た問題をどっかで見たかなー、、という気がした問題。結局、CとDが解けなさすぎてこの問題に取り組む余裕がなかったのですが、蟻本を探すと類似問題がありました。（POJ-1064）
ちゃんと蟻本やっとけよという教訓を得ました。
F問題
コンテスト中は問題文すら見てませんでしたが、コンテスト終了後にコピペで解けたとの報告がツイッターに相次いでいたので、典型的なアルゴリズムの問題かなと。。
今回の実績
灰パフォを叩き出してしまい、レーティング下げを喰らいました。
まだまだ遠い緑色。
2完終了で灰パフォでした😩
— devgenjin77 (@devgenjin77) 2020年8月2日
次回は落ちない様頑張ります。
devgenjin77さんのAtCoder Beginner Contest 174での成績：6820位
パフォーマンス：311相当
レーティング：605→568 (-37) :(#AtCoder #ABC174 https://t.co/1UIUMH78gU
総括
再度2完という残念な結果に。まだまだ精進が足りないと思いました。
盆休みはまとまった時間が取れそうなので、ABC過去問を大量に解いて精進していこうと思います。
M-SOLUTIONSプロコンオープン2020参加記
2020/7/25に開催されたM-SOLUTIONSプロコンオープン2020に参加しました。
今回の配点もABC並の点数。最近、同種のコンテストでは2完、2完、3完という残念な内容が続いてるので、今回こそは4完以上をという気持ちで臨みました。
参加します。今回は4完以上できたらいいな。てな感じで。
— devgenjin77 (@devgenjin77) 2020年7月25日
M-SOLUTIONS プロコンオープン 2020 - AtCoder https://t.co/VrgOBIxkiZ
今回の結果
で、今回はなんとか4完達成できました！
振り返り
A問題
言われた条件でひたすらIF文を書くだけの簡単な問題。それなりに時間がかかったが、一発ACでした。
ま、コーティング量を抑える解法もありましたが、ハマると面倒なのでゴリ押し実装ということで。。
B問題
B問題らしく、Aより複雑な問題という感じ。以下の解法で解きました。
- 赤カードの数字＞＝緑カードの数字のとき、緑カードの数字を2倍。
そうでない場合は、青カードの数字を2倍する。 - 1の処理をK回繰り返す。
- 赤カードの数字＜緑カードの数字＜青カードの数字のとき、Yesを出力。
「真に大きい」とかいう表現があまり馴染みがなかったので、言葉の意味からググってしまいましたw
C問題
最初の期末テストの点数とK+1学期の期末テストの点数を比較すれば、K学期の評点とK+1学期の評点の大小関係がわかります。あとは同様の要領で大小比較を行う学期を1ずつずらして評価するという解法でACが取れました。
ま、問題文のとおり掛け算で対処すると、オーバーフローとか食らうんだろうなー。
D問題
株価の推移を見ていって、安値で全力買いを入れ、高値で全部売り抜ければ良いです。
本番では余計な条件判定も入れてしまいめんどくさい実装になりましたが、なんとか一発でACが取れました。
E問題
Dが終わった時点で残り50分弱だったので、EかFが解けるかと思ってましたが、こっからが難問続き。
E問題は、コンテスト中に問題文を読みましたが、色々検討しても解法が思いつかずでした。
F問題
問題文まで読みましたが、コンテスト中には解けずに断念しました。
コンテスト後に解説を読んでACしましたが、90度角でぶつかる飛行機の条件として、X＋Yが同一またはXーYが同一というところが思いつかずでした。これがノーヒントで思いつくぐらいの実力がない自分には厳しい問題でした。
今回の実績
久々の4桁パフォで、レーティングもそれなりに上昇しました。
4完の緑パフォでした。次回に向けてまた精進します。
— devgenjin77 (@devgenjin77) 2020年7月25日
devgenjin77さんのM-SOLUTIONS プロコンオープン 2020での成績：2007位
パフォーマンス：1072相当
レーティング：514→605 (+91) :)
Highestを更新し、7 級になりました！#AtCoder #M-SOLUTIONSプロコンオープン2020 https://t.co/H2uP0u4L9a
総括
久々の4完で、もう少しで緑に到達出来そうです。今後も4完以上はできる様に日々の精進を頑張ります。
