0.はじめに
ビギナーとは・・・。。
と、なるくらいＣ以降の難易度が高く感じました。
まぁ私のレベルが低いのかもですが。
1.A - ^{-1}
リストを配列に入れて、頭からチェックでAC頂けました。
https://atcoder.jp/contests/abc277/submissions/36409527
2.B - Playing Cards Validation
【考え方】
(1)1文字目OK文字の辞書dict1を用意
(2)2文字目OK文字の辞書dict2を用意
(3)重複がないかをチェックする辞書dictinを用意
(4)SiをN回読み込んでいく
(4-1)Siの一文字目がdict1にあるかチェック
→なかったら"No"を出力しプログラム終了
(4-2)Siの２文字目がdict1にあるかチェック
→なかったら"No"を出力しプログラム終了
(4-3)Siがdictinにあるかチェック
→あったら"No"を出力しプログラム終了
→なかったらdictinにSiを登録
(5)Siのチェックがすべて通ったら"Yes"を出力しプログラム終了
解説をみたら正規表現等使うスマートな回答がありましたが
まぁ、辞書使うのでもいいかなと思いました。
https://atcoder.jp/contests/abc277/submissions/36417441
3.C - Ladder Takahashi
初見DPかなと思いましたが、戻るケースもあるなと思うと
DP初心者には難しいとあきらめモードでした。
まぁ、よくみると木の探索系であると気づき
とにかくやってみようと始めました。
【考え方１】
(1)全フロアごとにどのフロアへの階段があるかの配列を持つ表Lを作り初期化
(2)全フロアごとにそのフロアのチェックが終わったかの表Pをつくり初期化
(3)以下再帰関数chkF(引数nm)を定義
(3-1)表Lのインデックスnmの表を順に読み込む
(3-1-1)読み込んだ値：iがチェック済みかをチェック
(3-1-2)チェック済みでない場合
→表Pのiをチェック済みに変更
→chkFを引数iで呼び出し
-以下メインルーチン-
(4)A,Bを読み込み、表Lに格納していく
(5)引数に1をセットしchkFを呼び出し
(6)表P内でチェック済みとなっている一番大きいフロアを表示して終了
実装して実行したところ、表Lの定義時にメモリーエラー・・・。
さすがに、10の9乗の配列をもつ表はきつかったか・・・と方針変更。
配列を辞書にすれば、大体何とかなるので辞書を採用
【考え方２】
(1)フロアをキーに、どのフロアへの階段があるかの配列を値に持つ辞書Lを作り初期化
(2)チェック済みのフロアをキーに登録する、フロアチェック済み保持辞書Pをつくり初期化
(3)以下再帰関数chkF(引数nm)を定義
(3-1)辞書Lのキーnmの値配列を順に読み込む
(3-1-1)読み込んだ値：iがP表示あるか(チェック済みか)をチェック
(3-1-2)チェック済みでない場合
→表Pにiを登録
→chkFを引数iで呼び出し
-以下メインルーチン-
(4)A,Bを読み込み、表Lに格納していく
(5)引数に1をセットしchkFを呼び出し
(6)表PのMAXキーを表示
例題は難なくACが出たので、提出したところ、半分RE。
いろいろ試したけど分からないので、諦める・・・
と、思いましたが実装内容からREになるケースは再帰上限オーバーだな・・・と推察。
再帰上限オーバーのなんか素晴らしい回避策ロジックがないかをぐぐる。
いいロジックはなかったけど、再帰上限パラメータを書き換えることができることが分かる。
import sys
import resource
sys.setrecursionlimit(200000)
Atcoderでは認められないだろうな・・・・と思いつつ
テストケースで試すと通った・・・。
そのまま提出するとみごとAC。
何か反則っぽいけどまぁ良しとしました・・・。