ABC236
結果
A
B
C
ノーペナ完で,パフォは,rating変動はででした.
考察
A問題
私はtmpにb文字目を一時退避してa文字目と入れ替えましたが,stringの中でswapって使えるんですかね.
調べる時間の方が勿体なかったのでswapを実装しました.
B問題
枚のカード全てを見て,書かれている数字をカウントします.
~のうち,カウントされた回数がである数字が答えです.
(答え以外の数字は全部カウントがになります.)
C問題
setなどを使い,急行列車が止まる駅を全て覚えておきます.
各が,上で覚えておいた停車駅に含まれていればYes,含まれていなければNoです.
要素数のsetから要素を見つける最悪計算量はなので間に合います.(調べて知りました.)
感想
Highest更新しましたー!
C問題までは簡単だったので,罠に引っかかってないか用心深く提出しましたが,普通に簡単だっただけでしたね.
D問題はqueueを使ってDFSっぽいことをしましたが,サンプルまでしか通らずACには至りませんでした.
ABC234
結果
A
B
C
D
1WAの4完で,パフォは,rating変動はででした.
考察
A問題
関数を宣言して問題に忠実に出力計算式を書けばACです.
見間違えに気を付ける.
B問題
個目の点( )と個目の点( )で全探索をして,最大値を更新していきます.
このやり方だと,自分自身との距離とか,同じ点同士の距離計算を2回したりとか無駄が多いですが,面倒だし計算量的には変わらないのでこれでOK.
C問題
を2進数で表し,をで置き換えればACです.
0と2のみで構成される数字を小さい方から並べていくと,2進数で1ずつ加算していく計算をすることとほぼ同じことに気づけば簡単です.(私はすぐに気付きませんでしたが)
D問題
登場した数列を連想配列で保持しておきます.(大小関係を高速に保持したいため)
の先頭項のうち,番目に大きい連想配列の場所をitとします(iteratorの意味).初めに先頭項を連想配列に突っ込んでおくと,itの初期値は連想配列の先頭です.
順列の番目以降はまずは連想配列に入れますが,それがitの値より大きければ番目に大きい値は1つずれるので,itを1つ先に送ります.itの値より小さければ番目に大きい値はそのままです.
感想
C問題で2ベキが絡みそうなことはすぐ気づけましたが,ACまではかなり時間がかかってしまったのが悔しいです.
D問題は凡ミスで20分無駄にしたのでもっと日々コードを書けという気持ちになりました....はい,書きます.
ABC232
結果
A
B
C
D
WAの完で,パフォは,rating変動はででした.
考察
A問題
1, 3文字目をintに変換して普通にかけ算します.
久しぶりだったので,「intに直す関数なんだっけ」ってなったり,
「いや,-'0'でいいのか.あれ,+'0'だっけどっち?」
みたいな初心者みたいなことをしていて3分ぐらいかかりました.
B問題
これはなんでACしたかよくわからん.
とりあえずよくわからん解法を載せます.ACしていない人は読まないでください.
初期で一致していないindexのところだけ行き先を記憶しておきます.行き先が2つ以上あったらNoです.(pp→abみたいに)
あとは,行き先の行き先が自分自身だったらNoです.(ab→baだと,aの行き先はbで,bの行き先はaなのでNo)
これでなぜかACしたけど妥当性は完全に不明.
2021/12/20追記
問題をすごく読み違えていたことに気づきました.
ACしたのが奇跡です.
C問題
順列全探索です.
~ までの数列を,全ての順列で回しながら以下を行います.
1.青木くんのおもちゃの繋がり方をグラフとして表現
2.全てのひもに対して,青木くんのボールと繋がっているボールの中に青木くんのボールは存在するかを確認する.
全てのひもで2.が成り立っていれば,その数列が答えです.
ちなみに,頂点を0-indexedしていなかったので2WAしました.
D問題
グリッドのBFSです.
各地点までの距離をINFとかで初期化して,BFSをするだけです.
私はDPっぽい条件式で距離を更新しようとしていましたが,最短経路が常に出るので全く意味のない事をしていました.
vectorとかqueueってどうやって使うんだっけとなりました.
感想
1か月ほぼ全く競プロを触っていなかったので,色々忘れていてかなり焦っておりました.振り返ってみると,全体的に意味不明なコードを書いていたような気がします()
実は,B問題が終わった時点で下位5%ぐらいにいたので辞めちゃおうかと思いましたが,最後までやってよかったです.久しぶりのABC,楽しかった.
そういえば,rating変動0って初めてかも
ABC227
結果
A
B
C
ノーペナ完で,パフォは,rating変動はででした.
考察
A問題
人から枚配った先,つまりを考えます.
これがで割り切れればを出力し,割り切れなければを出力してAC.
(は,をで割った剰余)
色々パニックになっていたのでコードはもっと汚いですし,10分もかかりました.
B問題
全探索します.以上.
変数は全て正の整数で,があるので,で全探索しました.
まぁ多い分には適当でもいいので...
C問題
なので,の範囲はでOKです.
(言い換えると, となる以上の整数)
さらに,の範囲はから始めて,が成り立つ間です.
計算量評価はかなーりざっくりですが,のループはなので最悪 から ぐらいで,のループも(多分)同様にから ぐらいです.
まぁのループの方がのループより若干少ないのかなーって気持ちはあります.
どっちにしろ最悪の場合でもの処理で,中での処理は軽いので間に合うかなーってかんじで提出したらACしました.
の計算ですが,で個数が出てきます.
なので,を引いておく必要があります.
感想
コンテスト自体は少しずつ参加していましたが,めんどくさくて時間がなくて記事は書いていませんでした.
highest更新できてやったー!
共通テストの問題を深さ優先探索してみた
競プロとは直接関係ありませんが,競プロで得た知識のDFS(深さ優先探索)を使って問題を解きました.
本記事では言語はC++を使っていますが,一応他の言語を使った人でも読めるように解説したつもりです.
ちなみに,初めて紙面上で解いた時はDFSではなくBFS(幅優先探索)で私は解きました.
手作業ならDFSは大変なので...
BFSの実装は綺麗なステップ数の保持の仕方がよくわかりませんでした(おい)
BFSで実装した人はぜひ議論しましょう.
問題設定
以下,共通テストの数学IA,題4問より抜粋です.
第4問
円周上に15個の点が反時計回りに順に並んでいる.
最初,点に石がある.
さいころを投げて偶数の目が出たら石を反時計回りに5個先の点に移動させ,奇数の目が出たら時計回りに3個先の点に移動させる.
この操作を繰り返す.
例えば,石が点にあるとき,さいころを投げて6の目が出たら石を点に移動させる.
次に,5の目が出たら石を点に移動させる.
<中略>
(4)点の中から点を1つ選び,点にある石をさいころを何回か投げてその点に移動させる.
そのために必要となる,さいころを投げる最小回数を考える.
例えば,さいころを1回だけ投げて点にある石を点に移動させることはできないが,さいころを2回投げて偶数の目と奇数の目が1回ずつ出れば,点にある石を点へ移動させることができる.
したがって,点を選んだときには,この最小回数は2回である.
点のうち,この最小回数が最も大きいのは,点 シ であり,その最小回数は ス である.
(出典:独立行政法人 大学入試センター 共通テスト 数学IAより)
考察
以下,反時計回りの個先への移動を,時計回りの個先への移動をで表します.
まず,点から一手で行ける点は,の移動によると,の移動によるの2つです.
さらに,点からそれぞれの移動との移動を考えることで,点から二手で行ける点がわかります.
点からは点に,点からは点に一手で行けるので,点から二手で行ける点は点の3つです.
これを繰り返すことで点からの最小移動ステップ数が求まります.
私はこれをDFS(幅優先探索)で実装しました.
イメージ図は下のようになります.
左に伸びる辺はの移動を,右に伸びる辺はの移動を表しています.
色の説明をします.
青の点は,その点からの移動との移動をするために再帰的に操作をする点です.
赤の点は,現在のステップ数よりも最適なステップ数が既に見つかっているため,再帰をせず次の点の探索に移るという点です.
緑の点は,再帰呼び出しをしますが,後の方でより最適なステップ数が見つかるので図では省略しているという点です.(なので,実際の図はもっと大きくなります)
これをコードで書いていきます.
変数として以下を宣言します.
vector<int> step(15, 20);
記法の意味ですが,step[15]というint型の配列の要素を全て20で初期化する,と捉えてください.
vectorという型で宣言していますが,普通の配列だと思ってもらってもこの記事では差し支えありません.
step ]には,点から点に移動する最小ステップ数を更新しながら格納していきます.
それではDFSの中身を見ていきます.
void dfs(int current_point, int height){ int next_point1 = (current_point + 5)%15; int next_point2 = (current_point - 3 + 15)%15; if(height < step[next_point1]){ step[next_point1] = height; dfs(next_point1, height+1); } if(height < step[next_point2]){ step[next_point2] = height; dfs(next_point2, height+1); } }
引数は,現在見ている点current_point,現在の点のステップ数に+1をした値のheight,の2つです.
1行目と2行目で次に訪れる点を計算します.15個の点は円上に並んでおり,点と点は互いに移り合うので,15で割った余りの考え方で計算できます.
負数になることも考慮して,の移動では15を足してからmod 15をします.
その下の2つのif文は同じことをしているので1つ目だけ説明します.
移動がの先の点で同じことをするので再帰をするのですが,再帰をする条件としては,現在のステップ数heightが,移動先の点のその時点での最適ステップ数より小さいことです.
再帰をするとステップ数は1増えるので,移動先の点のその時点での最適ステップ数がheightより小さければ再帰をする意味がないです.
それでは最後に実行結果を以下に示します.
点 最小ステップ数 0 0 1 5 2 2 3 4 4 4 5 1 6 3 7 3 8 5 9 2 10 2 11 4 12 1 13 6 14 3
これを見ると,点からの最小ステップ数は点が一番大きいことがわかります.
よって設問(4)の答えは, シ :13, ス :6です.
というわけで競プロ番外編,共通テストの問題を深さ優先探索してみた,でした.
ABC215
結果
A
B
C
WAの完で,パフォは,rating変動はででした.
考察
A問題
stringで受け取り,"Hello,World!"と比較して一致すればAC,そうでなければWAを出力します.
(C++の文字列比較をすっかり忘れていたため時間を無駄にしました...)
B問題
をどんどんで割っていき,を下回ったらそれまでにで割った回数を出力します.
の形の時に注意します.
ちなみに,初期値をにしてを超えるまでをかけ算するやり方はオーバーフロウが怖いので避けました.
C問題
初めにSを昇順にソートしておき,next_permutationを行います.
回だけnext_permutationを行い,その結果を出力します.
感想
コンテスト終了から分後にD問題をACしました.
素因数分解のコードで凡ミスをしていたので整数問題を復習します...
ABC214
結果
A
B
C
ノーペナ完で,パフォは,rating変動はででした.
考察
A問題
ならを出力.
ならを出力.
ならを出力.
B問題
は非負整数なので,を満たすは,です.
の最大はなので,で全探索できます.
C問題
番目の人の出力結果をで初期化しておきます.
番目の人から反時計回りに宝石を渡し続けていき,渡す時刻が最適であれば更新し,そうでなければ番目の人に移ります.
一見二重ループですが,渡す時刻が更新されるのは高々2回(多分?)なので問題ありません.
例えば内側のループで番目の人まで渡す時刻を更新し続けたとすると,外側のループでは番目の人から番目の人までは見る必要はありません.(実装的には,内側のループは1回目で脱出します.)このときの内側のループの更新では,明らかに番目の外側のループと同じ更新をすることになるためです.
よって,続きは番目の人から見ればよく,計算量は線型です.
外側のループで最後に見る人が最適な時刻を持っていた時が最悪で,このときは最後に全ての時刻を更新することになります.(この時が更新回数が最大で2回?)
感想
1か月ぶりのABCでしたが,ほとんど冷えなくてよかったです.
仕事が落ち着いてきたので(?)少しずつ復帰したいです.