ABC229感想

結果

苦しみながらなんとか４完。

A問題

市松模様の配置になっている時のみ、Noを出力します。

B問題

各桁ごとに見て、和が10以上なら繰り上がりありです。

C問題

1gあたりの美味しさが高いものから順に見ていきます。これまで食べたチーズの重さを保持していって、境界となるチーズは、食べられるだけ食べます。

D問題

まず、"."がk個以下の時、全てを"X"にできます。それ以外の時は、操作はk回行うべきです。現状の左端の位置を保持しつつ、左から貪欲に見ていって、"."の出現回数がk回を超えたらans=max(ans,現在の位置-左端の位置)としていけば、O(n)で求めることができそうだという考察ができました。

ここからの実装が地獄でした。敗因は左から見ていって操作をk回行う以前と行った後を一緒のループで処理しようとしてしまい、実装が複雑になったことだと考えます。私の弱々頭はごちゃごちゃになってしまったので、2WAを経てもっと簡単に実装する手を考えました。

最初に"."の位置を全てqueueにぶちこみ、左端の情報を管理しやすくすることでなんとかACできました。自分の思考を言語化するのって本当に難しいことだなと感じます。D問題の理解度が低いため、言葉でうまく説明できないのでしょう。拙文of拙文で申し訳ございません。

E問題

n,n-1,...,,2,1の順でグラフを構築していき、Union -Findでその都度連結グラフの個数を数える道筋しか思いつかず、提出したところTLE。その後、頑張って計算量を軽くしたつもりでもTLE。pypy3をpython3に変えて祈りを捧げるもTLE。あえなくタイムアップ。今月もまた５完ならずでした。

思いついた解法と公式解説の道筋がほとんど同じでした。嬉しさ1%悔しさ99%です。頂点を追加するときに、num+=1。辺を追加するときに、それまでに連結していなかった成分同士を連結させたならnum-=1。とすることで連結成分数を容易に保持できるという考えに至れていませんでした。なるほどなるほどなるほど。

E問題　解説AC

総括

11月はレートがずっと横ばいです。泣きそうです。取り組み方を見直さなければいけない気がします。

余談

今後、「くじかつ」というものに最低週１は参加していきたいと思います。

ABC228感想

結果

時間ギリギリの4完。先週は時間ギリギリの３完だったのでホッとしました。しかし、D問題を早解きできるようにならないと水色にはなれなそうです。

A問題

最近、A問題が難しい気がします。前回に引き続き、問題の理解に時間がかかりました。

B問題

0-indexと入力を合致させるための-1を入れる場所を間違えてWA。無能が無能たる所以です。

C問題

３日目終了時点で上位k番に入っている人は、下位の人が全員０点を取れば、当然k番目に入れます。上位k番に入っていない人は、ちょうどk番目の人が０点をとって、自分が満点を取った場合に、その人を追い越せるか否かのみを判断すればいいです。C問題は先週のコンテストでトラウマになっていたので、解ききることができてよかったです。

D問題

「どこまでずらすか」という操作を高速化しなければいけない問題だということは最初の5分で気づけました。成長を感じました。しかし、高速化手法が全く思いつきませんでした。自分が成長できていないことを痛感しました。結論、成長できていないことを痛感しました。

まず、次に移るべきindexを辞書で管理するという謎の方法を実装し、WA。1分考えたらバグだらけであることに気づきました。提出する前に立ち止まって考えるべきでした。

どうしても高速化手法が思いつかず、実行時間制限4secを見て、意外と高速化しなくても通るんじゃないかなんていう淡い期待を抱いて、愚直にずらして提出。祈りは届かずTLE。

E問題をWAしたのち、D問題に帰ってきて考察を再開。「区間ごとにまとまりを作っていきたい」と感じて、何かしらをまとめて行くのにUnion-Findを使ったことがあるのを思い出しました。まだ使われていない場所を親とみなして実装。親が保持する負の値は、そこから何個連続で既に使われているかを表します。ある入力xから、どこまでずらすかを考える時は、まずはxの親を探して、親のindex-親が保持している値を計算すれば良いです。

元々自分が書いたことのあるUnion-Findは、indexが若いものが親になるというものでしたが、今回はそうとは限らなかったのでWA。どちらが親になるのかを適切に書き直してなんとかACできました。WAしまくった問題が通った瞬間の喜びは測り知れません。

E問題

「m^(k^n)だと思うんだけど、、、」→「一応、サンプル通してみよう」→「え、どっちも通るんですけど。」→「提出じゃああああ」→「知ってた。」でD問題に帰りました。

この問題はフェルマーの小定理たるものを以下に理解しているかを問うてきた問題だったと思います。過去問を解く中で何度か出てきたのですが、よくもわからず、xで割るときの998244353のあまりは、x^(998244353-2)をかけた時のあまりに等しいというのを暗記したのみでした。「いい加減な学習してないですか？」って出題者の方に指摘された気がします。

pが素数でaがpの倍数でない時、a^(p-1)%p=1。しっかり覚えました。理解できていたとして、解けていたかは別問題です。あはは。

E問題　解説AC

総括

新しい問題を解くだけでなく、一度解いた問題を解き直す必要がある気がしました。

余談

ac-predictorという便利ツールをインストールすると、コンテスト中にリアルタイムで自分の現在のレート遷移がわかります。とても便利です。使ってない方は是非使ってみてください！

ABC227感想

結果

時間ギリギリの3完。今週はまあまあ精進したつもりだったので、ショックが大きすぎます。

A問題

問題の読解に時間を要しました。今回のコンテストはなんだか難しい予感がビンビンしました。開始直後に抱いたこの予感は的中してしまいました。

B問題

入力のとりうる値が小さいB問題は大抵全探索で解ける気がします。個人的にはA問題よりB問題の方が解きやすかったです。

C問題

問題を見た時、「いやこれ間に合わないでしょ。」って思いました。最初に思いついたのはAにもCにも影響を及ぼしそうなBを1から√nまで全探索して、そこから二分探索してなんとか条件を満たすAとCの数を求めるというものでした。実装してみましたが、入力が10**11の時に全く間に合いません。その他に解法も思いつかないのでD問題を解くことにしました。ラスト15分で返ってきて再考すると、Aがとりうる範囲が一番小さいんだからAから見ていけば良いんじゃないのか？と気づき、血眼で実装したらなんとかACできました。最初の考察でこれに気づくことができていればレートを減らさずに済んだかもしれません。完全なる力不足です。

D問題

最初、昨日履修したセグメント木を使えるのでは？なんて考えがよぎるも、あ、無理だと思いました。履修した内容がすぐに出題されるなんていうそんなラッキーはそう簡単に起こらないみたいです。その後は、「まずはaをソートして上からk個とってきた配列をtmpとする。残った配列をresとする。これの最小値を取り出して、最終的な答えに加算。resから最も大きいものをtmpに加える。」という操作をresがなくなるまで繰り返す解法しか思いつかず、それを気合いで実装。最初はTLEとWAの嵐。誤りに気付いて再度実装し、勝ちを確信して提出すると12AC、17WA。デバッグに大量の時間を注ぎ込むも、何が間違いか気づくことができず諦めてしまいました。

D問題　何が違うか分からない

解説を見てびっくり仰天＋感動しました。プロジェクトをp個として、各部署からp人を超えない範囲でできるだけ多くの人を派遣した合計が、p*kを上回れば、そりゃプロジェクトをp個作ることができますね。。。問題を見る角度を変えて解くという力が圧倒的に不足しています。頭の弱さを痛感するばかりです。

D問題　解説AC

E問題

密かに5完を狙ってましたが、問題を見ることすらできませんでした。来週までにACしたいと思います。

総括

年内水色が現実的ではなくなってきてしまいました。精進あるのみです。

余談

今週、vimiumっていう便利すぎるchromeの拡張機能を知りました。Webページの閲覧、移動がキーボード入力で行える超優れものです！使ってない方はぜひ使ってみてください！

ABC226感想

結果

４完。4月の自分なら考えられないから嬉しいですが、グラフ系の問題はかなり解いてきたので、E問題が解けなかったのが悔しすぎます。

A問題

四捨五入の仕方がわからず、ググってround関数なるものを使ったらWA。便利なものは理解して使わなければ不便みたいです。結局、少数第一位部分が５以上か否かの判定を自分で書いてACしました。

B問題

B問題にしては難しい気がして涙目。setに随時数列を入れて、最後にsetの長さを出力しました。setの中にlistを入れることはできないことを今更知りました。

C問題

思考の整理をしないまま、各技を習得するのに必要な時間を前から計算していったらWA。A問題と合わせて2つ目のWAにより、押し寄せる絶望感。息をついて冷静になると後ろから見ていくべきであることに気づきました。まず技N習得に必要な時間を加算。技N習得前に習得しておかなければならない技の時間を加算。さらにそれより前に習得しておかなければならない技の時間を加算、、、という風に後ろから見ることでACできました。

D問題

使用する移動は、できるだけ小さいほうが、数多くの場所間の移動に使えそうです。例えば、(4,2)移動するならば(2,1)移動して(2,1)移動したほうが良さそうです。なぜなら(6,3)移動したい時に(4,2)移動のみでは辿り着けませんが、細かくしておくことで(2,1)を３回することでたどり着けるからです。この考察を元に、各ij間の移動をできるだけ細かくしてから、setにぶち込みその長さを出力しました。今回のABCではsetが大活躍です。i→j間の移動とj→i間の移動は対象なので最後に２倍しました。忘れなかった自分に拍手です。

E問題

「閉路がないと条件を満たすことはできない」「閉路が1つあれば2**1=2通り、閉路が2つあれば2**2=4通り、閉路が3つあれば2**3=8通りできる」という考察のもと、dfsで閉路が検出できたらans*=2するようなプログラムを実装してみましたが、サンプルコードが通らず。考察が間違っているのか、実装が間違っているのかわからないままタイムアップしてしまいました。

結局、考察が間違っていました。まず、連結成分ごとに考えるという思考が欠如していました。そして、頂点の数と辺の数が等しくなければ条件は満たし得ないということに気づくことができていませんでした。普段解説ACばかりで、紙とペンでの実験が甘いことを痛感しました。

全然惜しくはありませんでしたが、個人的に今までで1番解ける気がしたE問題でした。力不足をしっかりと受け止めて前向きに頑張ります。

E問題コンテスト後AC　我ながらなかなか綺麗なコード

総括

とにかく水色で年を越したいです。

ABC225感想

結果

４完。10月中に５完という目標を掲げていたのですが、達成ならず。特技の有言不実行をかましてしまいました。ただ前回に引き続きの４完は少し自信になりました。

A問題

もっと賢い書き方があるんだろうなーと思いながら、大人しく場合分けを3つ書きました。

B問題

頭の硬い私はとても周りくどい解き方をしてしまいました。繋がっている辺の本数だけを更新していけばよかったんですね。グラフでa,bをつなぐ辺ときたら、とりあえずg[a].append(b)とg[b].append(a)をするっていう固定観念を抜け出せない応用力のなさを痛感しました。

頭カチカチコード

頭やわコード

C問題

記述した条件が甘々で、エラーの嵐でした。配列の長さをオーバして１RE。７で割った余りが０のものが左に来てはダメなんだと気づかず、１WA。１列の時を考えておらず、２WA。合計３エラー。途中２完で終了という未来が頭をよぎりました。実力不足を痛感したC問題でした。

D問題

多数のqueryを処理する問題は、何らかの工夫をして高速化しなければならないって思っていたので悩みましたが、それぞれの操作を逐一行っていく解法しか思いつかず、苦戦しながら書いてみたら運良く通りました。各電車の前と後ろの電車の番号だけを更新していきました。

E問題

方針は合っていました。floatの比較はダメだってことを思い出して、Decimal関数を使いましたが、エラーがとれず。Decimal(y/(x-1))のように記述していましたが、Decimal(y)/Decimal(x-1)って書かなきゃだめなんですね。Decimal関数を通すことで機械に２進数として数値を渡すことができると考えたらとても自然です。Decimal関数というものをきちんと理解せず使うからこういうことになるのです。仮にDecimal関数を正確に使えていたとしてもPypyを使っていたのでTLEになっていました。回帰とDecimal関数を使う時はPythonと脳裏に刻んでおきます。知識が一つ増えました。

F問題

嫌な予感はしましたが、F問題っていう響きに怯えず問題を開いた人へのボーナス問題だーーーと思って喜んで、提出してやっぱりWAでした。思う壺です。最後の10分間考え続けたものの判例すら思いつきませんでした。来週までに必ず理解します。

総括

水色で歳を越したいです。このままでは無理です。精進します。

ABC224感想

結果

今の私に５完は無理だと悟っていたので、４完は率直に嬉しかったです。D問題は似た問題を多めに解いていたのでラッキーでした。

A問題

サンプルコードにatcoderやtouristを使用しているところに遊び心を感じました。

B問題

O(50^4)=O(6.25*10**6)=O(10**6)だから全探索できました。50**4を概算する力がない私は、最初全探索が間に合う気がしませんでした。5**4はO(10**2)、10**4はO(10**4)なので、かけ合わせてO(10**6)って考えれば良いのですね。とても小さく成長しました。

C問題

点a、b、cがあったとき、aとbを結ぶ線分とaとcを結ぶ線分の傾きが異なれば三角形を構築できることは、中学か高校で習った記憶がありました。それぞれの線分の傾きを求めて等式で評価したところ、0で割ってはダメだというエラーが出てきました。分母が０になるときの場合分けを追加してみると、答えが合わなくなってしまいました。どちらの分母も0なら三角形は構築できず、片方だけ0なら三角形構築できると思ったのですが何が違ったのでしょうか。何が間違えているか理解できなかったので、a/b=c/dをa*d=b*cにしてみると、ACできました。私にしては柔軟に対応できたと思います。

D問題

配列pによって、頭がごちゃごちゃになりました。インデックスを情報として捉えなきゃいけない問題は私の脳のキャパを超えてきます。

考えられうるコマの動かし方を全て考えて、終了条件に合致したらやめるっていう解法しか思いつく気がしなかったので、それを書いてTLEになったら諦めようと思いました。グラフ系の問題の計算量の見積もりが全くわからないのでどうにかせねばと思ってはいるのですが、放置してしまっています。無能が無能たる所以です。

無限にループしては大変なので、あらかじめpの状態として考えられるものを全て列挙して、作られた状態はそこから消していきました。こうすることで一度作られたpがもう一度出てきた場合、そこでストップできます。と、あたかもすぐこの発想が出てきたかのように話していますが、これを思いつくのに20分くらいはかかりました。

配列pによって苦しめられた私は、実装に多大なる時間を要し、もうダメかと思いましたが、なんとかACできました。dequeを使ってグラフを辿っていく問題は相当な数を解いたのですが、まだまだ実装に時間がかかります。無能は人よりたくさん精進しなくてはならないことを再確認すると同時に、なんとかACできたことに成長を感じました。D問題の最速正解4分34秒って書いてあるんですけど、どんな頭してるんですか。こちとら、問題文の意味を理解するのに5分以上かかってるんですが。本当に凄すぎます。

E問題

残された時間は20分弱。実装は諦めて、どうやって解くんだろ〜って考えてました。aの大きい方から見ていくべきな気がするけど、そんなことよりこれ実行時間に間に合う気がしないんですけどって思ってました。解説を読んだところ、この考察はあながち間違ってなくて嬉しくなりました。嬉しくなるより前にどうやって高速化できるか考えろって話です。５完できる日はまだまだ遠そうです。

前処理して高速化する方法が本当に考え出せません。解説ACばっかりじゃなくて自分で考える訓練をしなきゃダメなんだろうな〜と思います。

E問題　コンテスト後AC

総括

このまま行くと、水色になれる日はとても遠そうです。有言不実行が特技の私ですが、今週はたくさん精進したいと思います。

ABC223感想

結果

昨日のARCに引き続き、辛い結果となりました。３完茶パフォ。豆腐メンタルがボロボロになりそうです。精進しなくてはなりません。

A問題

x!=0の条件をサンプル３で教えてくれるのは親切設計です。サンプル３がなければ、間違いなく1WAくらってました。

B問題

左シフト、右シフトで作られる可能性のある文字列を全部リストに入れて、ソートして、前と後ろを出力しました。ここまでは順調でした。

C問題

解けそうだけど、何から手をつけていいか分からず思考が停止してしましました。小学校で習った「きはじ」をしっかりと使いこなすことができれば、こんなに時間はかからなかったと思います。距離を求めたい時に、時間×時間をしていました。これに気づくのに多大なる時間を要しました。

手当たり次第に実装を始めるより、解答の筋道を立ててから実装した方が、結果的に早くなるんだなって気付かされた問題でした。

D問題

問題文を読んだときに、解ける気がしませんでした。グラフ的な考えが使えそうってことにすら気づけませんでした。twitterにはトポロジカルソートっていう言葉が溢れてましたが、聞いたことしかなく勉強不足を痛感しました。

辞書順の問題は前から決めていくのが定石。っていうのは他の問題の解説で見たことがあった。その記憶を思い出せなかったのも反省。次に入り得る数字の候補をheapqで保持し続ければいい。納得。

D問題　コンテスト後AC

E問題

コンテスト前は5完するなんてほざいていましたが、これまた解ける気がしませんでした。

来週までに解説読んでACします。明日やろうは馬鹿やろう。

総括

精進が足りていないことを痛感した土日でした。ここで心折れて競プロを辞めてしまったら、競プロをやる前の自分と同じなので踏ん張って入水したいと思います。5完するなどという今の自分には無謀な目標をやめて、謙虚に精進していきます。

それにしても、twitterで競プロ関係の質問をすると、必ずどなたかが解答をくださいます。競プロ界隈の暖かさに救われるばかりです。

ARC128感想

結果

辛すぎる結果となりました。AB２完を目標に挑みましたが、０完。ARC難しい。。。

A問題

高い方からn//2個かけ合わせて、低い方からn//2個の数字で割れば答えじゃん。というアホな考えでコードを書いている途中に、金銀の状態によってはかけたり割ったりできないものもあるじゃん。って気づいて自分のアホさに嫌気がさしました。

これはdpで書けるのではないかと思い直し、金銀それぞれの状態で重さが最大となるような選び方を保持していって更新していこうと思って、実装してみたら、WA、TLE、MLEの３大エラーを全て詰め込んだ結果が返ってきて、嫌になって諦めてしまいました。

1日に何度も交換したとしても最終的なスコアは変わらないという考えが頭良すぎて発狂しました。

B問題

どれか２色のボールの数を３で割った余りが同じ、かつ最後の１色のボールの数が十分ある場合は、２色のボールを必ず同じ数にできる。という点に気づいて、それが最小となることを証明することもなく提出すると１AC、５WA。諦め撤退してしまいました。

意外と方針は間違っていなかったので、少し救われました。最後の１色のボールの数が何個であろうが操作の順序を工夫すれば必ず同じ数にできることに気づけなかったのが敗因でした。悔しいです。

スパース性とは。1分で説明してみた

スパースとは、英語で「わずか」という意味。

ものごとに含まれる本質的な情報は、ごく「わずか」であるという性質をスパース性という。

複雑な現象から、本質的な情報を抽出するように分析する技術をスパースモデリングという。

ABC222感想

結果

先週はお出かけしていて参加できなかったので、2週間ぶりのコンテスト。 1週間参加しないだけで、随分久しぶりな気がしました。 5完を目標にしていましたが、無念。精進不足です。最初の状態から考えると、4完できるようになっただけでも嬉しいです。今月中に1度は5完したいな。。。

C問題

活字が苦手で本も読まない私は、問題文の文字の多さに少し気分が悪くなってしまいました。

それぞれの人の勝ち数を多い順に保持していかなければならないことに気づくのに5分かかりました。「番号が小さいほうが強く、勝ち数が大きいほうが強い」っていうような状況下ではどちらか一方をを負の数で保持していくと、sortするときに便利っていうのは他の問題で学んでました。4月の頃の自分だったらこんな発想ありえなかった。少し成長を感じました。

C問題　自分の提出

じゃんけんの勝ち負け判定のスマートさに驚きました。

C問題　神コード

D問題

最初、b[i]-a[i]+1をかけあわせていけば答えじゃん！簡単じゃん！って思ってコードを書きました。そんな私がc[i]>c[i+1]となる状況が生まれるという驚愕の事実を知るのは、7分くらい後でした。己の愚かさに悲しみを抱きながら、998244353という数字があるのでDPあり得るのでは？というセコセコな考えが思い浮かびまして、頑張って実装してみたところ、なんとかACできました。

D問題　自分の提出

E問題

各辺を何回通るか、配列cntに保存。r=(sum(cnt)+k)//2、b=(sum(cnt)-k)//2になるので、そのような塗り分け方を計算したい。「組み合わせ　和」でググったら、動的計画法による数え上げが一番早そう。とりあえず実装して提出！WAとTLEのオンパレード。。。

E問題　コンテスト中のWA＋TLDコード

解説見ると、解法が自分のコンテスト中の思考とかなり同じでびっくりして悔しくて、でもちょっと嬉しかった。しかし、何がダメだったのか考えると全部違った。まず、(k+sum(cnt))//2が整数とならない場合を考慮できていなかった。おそらくこれがWAの一因。あと、cnt[i]って書きたいところにiって書いてしまっている自分らしさ全開のミス。そして、最短経路を調べてcntを更新していく過程が間違っていた。何が間違っていたかはわからない。わからないままだから伸びないのかな。。。汚いコードはバグを見つけづらい。神コードを読んで超納得した。次からはできる気がする。さらにはDPの構成が違った。総和xの配列の中から部分和yになるような組み合わせの数を求めたいときは、dp[x]を用意して上から順に更新していき、dp[y]を出力すれば良い。次出たら通せる自信ができたのでよき！dequeの初期化にq.clear()っていうのがあることも知れた。

E問題　コンテスト後のACコード　最短経路を探す部分結構分かりやすいはず！

コンテスト楽しすぎ！