読者です 読者をやめる 読者になる 読者になる

年中春休み

年中春休みじゃないです。

競技プログラミング 3 (過去問 ABC 042)

abc042.contest.atcoder.jp

 

A問題

5が2つ、7が1つのときだけYESと出力するようにしました。

 

B問題

解けませんでした。というか文字列配列にsortかけたら辞書順に並ぶことを知りませんでした。

まぁ次は確実に出来ると思うので勉強だったということにします。

 

C問題

いろいろごちゃごちゃ考えた後にわからなくなったんですが、よく考えるとNを1ずつプラスして毎回条件に合うか判定してもNが小さいから間に合うかな?と思ったら間に合いました。よかったです。

 

D問題

学校の授業でやった動的計画法を使えばいいのかな?と思ったんですが二次元配列が大きくなりすぎて(i, j)に到達する経路をa[i][j]と置くのはダメっぽかったので諦めてしまいました。(大きい二次元配列の実現は可能らしいのですが計算量的にどうかはわかりません)

解説見たら考え方はそこまで間違ってなさそうなので二次元配列を使わないのでもっと簡潔に書くのを目指して後日チャレンジしようと思います。

 

追記:普通にcombinationでやればいいだけですね、計算量は工夫しなくても大丈夫かどうかがわかりません。

 

 

解けないB問題にぶち当たると1つ基本的な知識が増えるのでそこまで落胆することでもないのかなと思います。

C++の本1冊読んでその後他の勉強全くしないで競技プログラミングの勉強してるので知らないことが多すぎる。