7K12 blog

猫でも分かるアルゴリズム解説

第三回アルゴリズム実技検定 PAST を受験した感想

f:id:tkr987:20200606181218p:plain

ABCDEFGとJの8完で58点、中級まで点数が1問足りなかった…(´・ω・`)

全体的に、普段の競技プログラミングで出題される数学的傾向の強い問題ではなく、数学は使わないけどプログラミング特有の発想、考察、実装力を問う問題が多い印象を受けた。競技プログラミング未経験の人でも実装を学べて楽しめる問題が多いと思う。

 

A - ケース・センシティブ

f:id:tkr987:20200606181336p:plain

https://atcoder.jp/contests/past202005/submissions/13497947

std::transformを使って書けないかと思ってググったりしてたけど、コンパイルエラーで使えず。結局アスキーコードで条件分岐させて対応した。正直5時間も頭を使うのが面倒だったため、あまりヤル気がなくてA問題で10分も時間を費やして実装した 笑

 

B - ダイナミック・スコアリング

f:id:tkr987:20200606181808p:plain

https://atcoder.jp/contests/past202005/submissions/13501062

別に計算量とかは考えなくて良いけど、二次元配列とか使ってプログラムを書いてみよう的な問題。Bでも割と重いんだな~と思いながら実装した。ABC-C相当?15分かけて実装した。

 

C - 等比数列

f:id:tkr987:20200606182206p:plain

https://atcoder.jp/contests/past202005/submissions/13504395

普通に実装するとオーバーフローするので、競技プログラミングに慣れてない人は困ったりしそうだな~と思いながら実装を考えてた。言うて自分も数弱なので割と時間かかる。対数を使うの面倒だな~と思いつつ19分かけて実装した。

 

D - 電光掲示

f:id:tkr987:20200606182800p:plain

https://atcoder.jp/contests/past202005/submissions/13506336

実装するだけ問題。こういうのはABCでは見かけないけど、たぶん普通の人が考えるプログラミングスキルに近いので、未経験の人でも楽しめると思われる。13分かけて実装、提出した。

 

E - スプリンクラー

f:id:tkr987:20200606183601p:plain

https://atcoder.jp/contests/past202005/submissions/13507797

この問題は考察ゼロだけど、グラフ的なデータ構造のプログラミング方法を知らないと書けない。グラフ構造は一度もプログラミングしたことないという人も多いと思うので、このあたりから未経験だと厳しそうではある。実装自体はNyaGadget::NyaaBFSを貼るだけ。9分で提出した。

 

F - 回文行列

f:id:tkr987:20200606184544p:plain

https://atcoder.jp/contests/past202005/submissions/13513286

これも実装するだけ問題。行列という単語に拒否反応せず、落ち着いて問題文を読むと複数の文字列から回文を生成しよう、的な実装するだけ問題と分かる。ただし、添字とネストが増えやすくて実装が重いため、未経験だと発狂するかもしれない。40分かけて実装、提出した。

 

G - グリッド金移動

f:id:tkr987:20200606185456p:plain

https://atcoder.jp/contests/past202005/submissions/13531946

NyaGadget::GT_NyaaGridBFSを貼るだけなんだよな~10分で提出、GGEZ のはずが無限に広がるを読んでなくて200ピッタリのグリッド上で考えていて永遠にバグらせていて頭が破壊された。試験10分前にサイズを201に増やしたら通った。これだからプログラミングは糞という気持ちになった。

 

H - ハードル走

f:id:tkr987:20200606190122p:plain

G問題で頭を破壊されて完全にヤル気を失ってしまった。

DPだろうということは分かったが、0.5とかいうのが面倒で考えるのを辞めた。

 

I - 行列操作

f:id:tkr987:20200606190318p:plain

難しい。「行列の計算をしよう」という問題のはずがなく(それだと脳死で全員できてしまう)当然ながら普通に処理したら無限に時間かかるので、操作の性質に気づく必要がありそうだが、何も分からなかった。

 

J - 回転寿司

f:id:tkr987:20200606190708p:plain

https://atcoder.jp/contests/past202005/submissions/13530459

これ以上問題を解いても中級に届かずヤル気を失っていたが、問題文を読んだら最長減少部分列(最小分解個数の増加部分列集合)だと気づいたので、NyaGadget::DS_NyaaLDSを貼る。ただし、テンプレート引数を構造体にする必要があったので、そこだけ修正する。提出したらAC通った。これはライブラリを持っている自分の勝ち!と思ったが、同レート帯の知り合いが自力実装していた上に点数でも1問差で負けていてショックを受けた…(^^;