2022-01-23

ABC236

結果

A $\ 01:26$

B $\ 04:46$

C $\ 07:21$

ノーペナ $3$ 完で，パフォは $994$ ，rating変動は $+16$ で $838 \to 854$ でした．

考察

A問題

私はtmpにb文字目を一時退避してa文字目と入れ替えましたが，stringの中でswapって使えるんですかね．

調べる時間の方が勿体なかったのでswapを実装しました．

B問題

$4N-1$ 枚のカード全てを見て，書かれている数字をカウントします．

$1$ ～ $N$ のうち，カウントされた回数が $3$ である数字が答えです．

(答え以外の数字は全部カウントが $4$ になります．)

C問題

setなどを使い，急行列車が止まる駅を全て覚えておきます．

各 $S [ i ]$ が，上で覚えておいた停車駅に含まれていればYes，含まれていなければNoです．

要素数 $N$ のsetから要素を見つける最悪計算量は $O(logN$ なので間に合います．(調べて知りました．)

感想

Highest更新しましたー！

C問題までは簡単だったので，罠に引っかかってないか用心深く提出しましたが，普通に簡単だっただけでしたね．

D問題はqueueを使ってDFSっぽいことをしましたが，サンプルまでしか通らずACには至りませんでした．

2022-01-08

ABC234

結果

A $01 \ : 54$

B $05 \ : 23$

C $35 \ : 03$

D $82 \ : 29$

1WAの4完で，パフォは $746$ ，rating変動は $-10$ で $848 \to 838$ でした．

考察

A問題

関数を宣言して問題に忠実に出力計算式を書けばACです．

見間違えに気を付ける．

B問題

$i$ 個目の点( $1 \leq i \leq N$ )と $j$ 個目の点( $1 \leq j \leq N$ )で全探索をして，最大値を更新していきます．

このやり方だと，自分自身との距離とか，同じ点同士の距離計算を2回したりとか無駄が多いですが，面倒だし計算量的には変わらないのでこれでOK．

C問題

$K$ を2進数で表し， $1$ を $2$ で置き換えればACです．

0と2のみで構成される数字を小さい方から並べていくと，2進数で1ずつ加算していく計算をすることとほぼ同じことに気づけば簡単です．(私はすぐに気付きませんでしたが)

D問題

登場した数列を連想配列で保持しておきます．(大小関係を高速に保持したいため)

$P$ の先頭 $i$ 項のうち， $K$ 番目に大きい連想配列の場所をitとします(iteratorの意味)．初めに先頭 $K$ 項を連想配列に突っ込んでおくと，itの初期値は連想配列の先頭です．

順列の $K+1$ 番目以降はまずは連想配列に入れますが，それがitの値より大きければ $K$ 番目に大きい値は1つずれるので，itを1つ先に送ります．itの値より小さければ $K$ 番目に大きい値はそのままです．

感想

C問題で2ベキが絡みそうなことはすぐ気づけましたが，ACまではかなり時間がかかってしまったのが悔しいです．

D問題は凡ミスで20分無駄にしたのでもっと日々コードを書けという気持ちになりました....はい，書きます．

2021-12-19

ABC232

結果

A $\ 02 : 46$

B $\ 26 : 07$

C $\ 65 : 59$

D $\ 91 : 19$

$4$ WAの $4$ 完で，パフォは $840$ ，rating変動は $\pm 0$ で $848 \to 848$ でした．

考察

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問題

順列全探索です．

$0$ ～ $N-1$ までの数列 $P$ を，全ての順列で回しながら以下を行います．

1.青木くんのおもちゃの繋がり方をグラフとして表現

2.全てのひも $i$ に対して，青木くんのボール $P_{A_{i} }$ と繋がっているボールの中に青木くんのボール $P_{B_{i}}$ は存在するかを確認する．

全てのひもで2.が成り立っていれば，その数列 $P$ が答えです．

ちなみに，頂点を0-indexedしていなかったので2WAしました．

D問題

グリッドのBFSです．

各地点までの距離をINFとかで初期化して，BFSをするだけです．

私はDPっぽい条件式で距離を更新しようとしていましたが，最短経路が常に出るので全く意味のない事をしていました．

vectorとかqueueってどうやって使うんだっけとなりました．

感想

1か月ほぼ全く競プロを触っていなかったので，色々忘れていてかなり焦っておりました．振り返ってみると，全体的に意味不明なコードを書いていたような気がします()

実は，B問題が終わった時点で下位5%ぐらいにいたので辞めちゃおうかと思いましたが，最後までやってよかったです．久しぶりのABC，楽しかった．

そういえば，rating変動0って初めてかも

2021-11-13

ABC227

結果

A $\ 11 : 37$

B $\ 15 : 54$

C $\ 50 : 20$

ノーペナ $3$ 完で，パフォは $1052$ ，rating変動は $+25$ で $823 \to 848$ でした．

考察

A問題

人 $A$ から $K$ 枚配った先，つまり $K+A$ を考えます．

これが $N$ で割り切れれば $K+A$ を出力し，割り切れなければ $(K+A) \% N$ を出力してAC．

( $X \% Y$ は， $X$ を $Y$ で割った剰余)

色々パニックになっていたのでコードはもっと汚いですし，10分もかかりました．

B問題

全探索します．以上．

変数は全て正の整数で， $4ab$ があるので $1 \leq a \leq 300$ ， $1 \leq b \leq 300$ で全探索しました．

まぁ多い分には適当でもいいので...

C問題

$A \leq B \leq C$ なので， $A$ の範囲は $1 \leq A \leq \sqrt[3]{N}$ でOKです．

(言い換えると， $A^{3} \leq N$ となる $1$ 以上の整数)

さらに， $B$ の範囲は $A$ から始めて， $AB^{2} \leq N$ が成り立つ間です．

計算量評価はかなーりざっくりですが， $A$ のループは $\sqrt[3]{N}$ なので最悪 $10^{3}$ から $10^{4}$ ぐらいで， $B$ のループも(多分)同様に $10^{3}$ から $10^{4}$ ぐらいです．

まぁ $B$ のループの方が $A$ のループより若干少ないのかなーって気持ちはあります．

どっちにしろ最悪の場合でも $10^{8}$ の処理で，中での処理は軽いので間に合うかなーってかんじで提出したらACしました．

$C$ の計算ですが， $(N/AB) - (B-1)$ で個数が出てきます．

$B \leq C$ なので， $B-1$ を引いておく必要があります．

感想

コンテスト自体は少しずつ参加していましたが，~~めんどくさくて~~時間がなくて記事は書いていませんでした．

highest更新できてやったー！

2021-09-23

共通テストの問題を深さ優先探索してみた

競プロとは直接関係ありませんが，競プロで得た知識のDFS(深さ優先探索)を使って問題を解きました．

本記事では言語はC++を使っていますが，一応他の言語を使った人でも読めるように解説したつもりです．

ちなみに，初めて紙面上で解いた時はDFSではなくBFS(幅優先探索)で私は解きました．

手作業ならDFSは大変なので...

BFSの実装は綺麗なステップ数の保持の仕方がよくわかりませんでした(おい)

BFSで実装した人はぜひ議論しましょう．

問題設定

以下，共通テストの数学IA，題4問より抜粋です．

第4問

円周上に15個の点 $P_0, P_1, \cdots , P_{14}$ が反時計回りに順に並んでいる．

最初，点 $P_0$ に石がある．

さいころを投げて偶数の目が出たら石を反時計回りに5個先の点に移動させ，奇数の目が出たら時計回りに3個先の点に移動させる．

この操作を繰り返す．

例えば，石が点 $P_5$ にあるとき，さいころを投げて6の目が出たら石を点 $P_{10}$ に移動させる．

次に，5の目が出たら石を点 $P_7$ に移動させる．

<中略>

(4)点 $P_1, P_2, \cdots, P_{14}$ の中から点を1つ選び，点 $P_0$ にある石をさいころを何回か投げてその点に移動させる．

そのために必要となる，さいころを投げる最小回数を考える．

例えば，さいころを1回だけ投げて点 $P_0$ にある石を点 $P_2$ に移動させることはできないが，さいころを2回投げて偶数の目と奇数の目が1回ずつ出れば，点 $P_0$ にある石を点 $P_2$ へ移動させることができる．

したがって，点 $P_2$ を選んだときには，この最小回数は2回である．

点 $P_1, P_2, \cdots, P_{14}$ のうち，この最小回数が最も大きいのは，点シであり，その最小回数はスである．

(出典：独立行政法人大学入試センター共通テスト数学IAより)

考察

以下，反時計回りの $n$ 個先への移動を $+n$ ，時計回りの $n$ 個先への移動を $-n$ で表します．

まず，点 $P_0$ から一手で行ける点は， $+5$ の移動による $P_5$ と， $-3$ の移動による $P_{12}$ の2つです．

さらに，点 $P_5, P_{12}$ からそれぞれ $+5$ の移動と $-3$ の移動を考えることで，点 $P_0$ から二手で行ける点がわかります．

点 $P_5$ からは点 $P_{10}, P_2$ に，点 $P_{12}$ からは点 $P_2, P_9$ に一手で行けるので，点 $P_0$ から二手で行ける点は点 $P_2, P_9, P_{10}$ の3つです．

これを繰り返すことで点 $P_0$ からの最小移動ステップ数が求まります．

私はこれをDFS(幅優先探索)で実装しました．

イメージ図は下のようになります．

f:id:chankilu23:20210125132731j:plain

左に伸びる辺は $+5$ の移動を，右に伸びる辺は $-3$ の移動を表しています．

色の説明をします．

青の点は，その点から $+5$ の移動と $-3$ の移動をするために再帰的に操作をする点です．

赤の点は，現在のステップ数よりも最適なステップ数が既に見つかっているため，再帰をせず次の点の探索に移るという点です．

緑の点は，再帰呼び出しをしますが，後の方でより最適なステップ数が見つかるので図では省略しているという点です．(なので，実際の図はもっと大きくなります)

これをコードで書いていきます．

変数として以下を宣言します．

vector<int> step(15, 20);

記法の意味ですが，step[15]というint型の配列の要素を全て20で初期化する，と捉えてください．

vectorという型で宣言していますが，普通の配列だと思ってもらってもこの記事では差し支えありません．

step $[ i$ ]には，点 $P_0$ から点 $P_i$ に移動する最小ステップ数を更新しながら格納していきます．

それでは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個の点は円上に並んでおり，点 $P_0$ と点 $P_{14}$ は互いに移り合うので，15で割った余りの考え方で計算できます．

負数になることも考慮して， $-3$ の移動では15を足してからmod 15をします．

その下の2つのif文は同じことをしているので1つ目だけ説明します．

移動が $+5, -3$ の先の点で同じことをするので再帰をするのですが，再帰をする条件としては，現在のステップ数heightが，移動先の点のその時点での最適ステップ数より小さいことです．

再帰をするとステップ数は1増えるので，移動先の点のその時点での最適ステップ数がheightより小さければ再帰をする意味がないです．

それでは最後に実行結果を以下に示します．

これを見ると，点 $P_0$ からの最小ステップ数は点 $P_{13}$ が一番大きいことがわかります．

よって設問(4)の答えは，シ：13，ス：6です．

というわけで競プロ番外編，共通テストの問題を深さ優先探索してみた，でした．

出典：独立行政法人大学入試センター共通テスト数学IA

2021-08-21

ABC215

結果

A $\ 02: 48$

B $\ 09: 35$

C $\ 16: 27$

$1$ WAの $3$ 完で，パフォは $687$ ，rating変動は $-14$ で $829 \to 815$ でした．

考察

A問題

stringで受け取り，"Hello,World!"と比較して一致すればAC，そうでなければWAを出力します．

(C++の文字列比較をすっかり忘れていたため時間を無駄にしました...)

B問題

$N$ をどんどん $2$ で割っていき， $2$ を下回ったらそれまでに $2$ で割った回数を出力します．

$N=2^{n}$ の形の時に注意します．

ちなみに，初期値を $1$ にして $N$ を超えるまで $2$ をかけ算するやり方はオーバーフロウが怖いので避けました．

C問題

初めにSを昇順にソートしておき，next_permutationを行います．

$K$ 回だけnext_permutationを行い，その結果を出力します．

感想

コンテスト終了から $5$ 分後にD問題をACしました．

素因数分解のコードで凡ミスをしていたので整数問題を復習します...

2021-08-14

ABC214

結果

A $\ 01 : 29$

B $\ 04 : 23$

C $\ 42 : 25$

ノーペナ $3$ 完で，パフォは $821$ ，rating変動は $-1$ で $830 \to 829$ でした．

考察

A問題

$1 \leq N \leq 125$ なら $4$ を出力．

$126 \leq N \leq 211$ なら $6$ を出力．

$212 \leq N$ なら $8$ を出力．

B問題

$a, b, c$ は非負整数なので， $a+b+c=S$ を満たす $a, b, c$ は， $0 \leq a, b, c \leq S$ です．

$S$ の最大は $100$ なので， $a, b, c$ で全探索できます．

C問題

$i$ 番目の人の出力結果を $T[ i ]$ で初期化しておきます．

$i$ 番目の人から反時計回りに宝石を渡し続けていき，渡す時刻が最適であれば更新し，そうでなければ $i+1$ 番目の人に移ります．

一見二重ループですが，渡す時刻が更新されるのは高々2回(多分？)なので問題ありません．

例えば内側のループで $i+j$ 番目の人まで渡す時刻を更新し続けたとすると，外側のループでは $i+1$ 番目の人から $i+j$ 番目の人までは見る必要はありません．(実装的には，内側のループは1回目で脱出します．)このときの内側のループの更新では，明らかに $i$ 番目の外側のループと同じ更新をすることになるためです．

よって，続きは $i+j+1$ 番目の人から見ればよく，計算量は線型です．

外側のループで最後に見る人が最適な時刻を持っていた時が最悪で，このときは最後に全ての時刻を更新することになります．(この時が更新回数が最大で2回？)

感想

1か月ぶりのABCでしたが，ほとんど冷えなくてよかったです．

仕事が落ち着いてきたので(?)少しずつ復帰したいです．