2020/10/10、11に開催されたコンテストの感想

HHKBプログラミングコンテスト2020(AtCoder)

A

条件に応じて大文字にしたりしなかったりして出力

• toupper()を使うと変換できる
• 32をxorすると書いてあった。なるほど

B

二次元グリッド上で2つ並んだドットの場所を数える

• やるだけ
• 配列外参照怖いね

C

配列のi番目までに出てきてない最小の非負整数

• 順に出力するけど、最小の非負整数は単調非減少
• 現時点で出現してない最小の数とすでに出た数を記録しておけば最小値の更新は高々10⁶オーダで収まるので大丈夫

D

一辺Nの正方形に一辺Aの正方形と一辺Bの正方形を重ならないように置く総数

• むずかったので順位表を見て先にEを解きました
• 制約を見るとおそらくO(1)算数というやつ
• とりあえず一個置いて、その中に置く置き方のうちNの枠からはみ出る…とか考えたけどなんか難しそうなので却下
• x軸とy軸に射影することを考える
• 余事象を使いたい
• Aだけを置くとき各軸への射影は(N-A+1)通り、Bも同様
• 射影上での重なりを無視した場合、各軸(N-A+1)*(N-B+1)通りの射影
• 各軸について、重なりのない射影は正方形の左右または上下関係を固定すると max(0,N-A-B+2)C2通り
• 左右両パターンでその2倍
• これは正方形の位置関係を固定して、片方の正方形の位置を固定したときもう片方の正方形の位置が何通りあるか考えると出た
• x軸どうでもいいy軸重なってない+y軸どうでもいいx軸重なってない-x軸重なってないy軸重なってない、が答え

E

一直線に照らすランプがある。ランプのすべての置き方について、照らされるマス数の総和

• どっかで見た問題な気がする(ABC129-D)
• 数えるものを変える
• 全部の置き方に対して、それぞれのマスは何回照らされるか
• あるマスが照らされるパターンはそのマスを照らすランプが1個以上あって、そのマスを照らさないランプがあったりなかったりする場合
• マスを照らすランプx個、そうでないランプy個とすると、マスを照らす置き方は(2^x-1)*(2^y)通り
• 全マスこれを計算して足し合わせるだけ

Codeforces Global Round 11

A

できるなら、数列を前から何項の和も0にならないように並び替えよ

• 0の付近をうろつきたくない
• めっちゃ遠ざかって戻ってくる
• 0が含まれているのを考慮して昇順ソートと降順ソートを試す
• 両方ダメなら諦め

B

n回の試合の勝敗をk回まで書き換えて、得点を最大化せよ。 得点は1勝1点、ただしその前の試合も勝っていれば2点

• 当然、可能な限り負けを勝ちにする
• むやみに書きかえるのはダメ
• 勝ちと勝ちの間の負けを埋めるようにするのがよい
• 連敗数を調べて、小さい連敗から順番に勝ちに書き換える
• 埋められる連敗部分の数がわかって、あとはごちゃごちゃした計算

C

二次元グリッド上を移動して一瞬だけ現れる人間と遭遇できる回数を最大化

• 愚直なDPじゃ間に合わないしうまい方針も浮かばなかったので撤退

D

順列をブロックに区切り、そのブロックを逆順に並べる操作を繰り返してソートせよ。可能な操作回数は要素数nに等しい

• nが小さく割と何をしてもよさそう
• 1と2を繋げて2と3を繋げて…ができればうまくいく
• つなぐとき、[xx][2xx][1][xx]みたいに区切ればつながる
• が、xx 2 xx 1 xx のような場合はいいが xx 1 xx 2 xx のような場合は無理
• でも、そうなってるxとx+1のペアはどこかに存在する、しないならそれはソート済
• 隣り合うペアを見つけ次第つなぐ方針で良さそう
• 見つけ次第の方針に変更したせいで問題が生じる
• [6xx][5]か、[6x][x5]か、[6xx][5]かを間違うとせっかくソートした部分が壊れる
• けど6の後ろどこまでがソートされているか調べてソートできてない部分との境で区切ればいい
• この最後の考察をして書き換えて出したのが終了30秒ちょい前ぐらい、通ってよかった

Educational Codeforces Round 96

A

{3,5,7}部屋のアパートには{3,5,7}枚の窓、全部でn枚の窓なら各アパートいくつずつ？（あり得ない入力あり）

• 多重for文で全探索
• 窓7の部屋数と窓5の部屋数をループ変数として、窓3の部屋は固定されるので…といういつもの計算量減らし
• TL厳しいケースがPretestになくて、終了後にHackされまくってた

B

バケツの水を別のバケツに全部移す操作をk回まで行って最大量と最小量の差を最大化するといくらか

• 1回以上操作するので0のバケツを生むことは可能
• 多いバケツに多い水を入れる
• ソートして水が多いバケツk+1個の総量が答え（+1を忘れそうになる 最多のバケツに2番目以降を入れるので…）

C

1からnまでの数が黒板にある 2個消して平均の切り上げを書く操作を繰り返すと最大でいくつになるか、その操作はどのように行うか

• 奇数同士、偶数同士がうれしい気がする
• nとn-2、あとは生成された数と残ってる最大の数でいい
• コンテスト後を見るにどうやら必ず2になるらしく、同様の方針だがnとn-1から始めていいらしい

D

01文字列から1文字消したあと先頭から同じ文字が続く限り消す操作を最大で何回行えるか

• 何はともあれランレングス圧縮
• 111...のような複数連続している区間はそこから1つ消した後それ自身を消せるので得
• 010101のように1こずつ交互になっているところでは先頭を消すのがよさそう、一度に先頭2文字消える
• 途中を消して01001みたいにするとかなり損に見えるので先頭から消すべきっぽいよね、と。
• 複数連続しているところは削れるだけ削って問題ない（どうせ一気に消されるので）
• 複数連続しているところがいくつかあるなら先頭に近いほうから削るべき
• 結構ふんわりしてるけど実際これでうまくいってくれで通してしまったもので。
• 連続している場所があればそのうち先頭に近いところから1個消して先頭を消す、なければ先頭から消す
• 個数と連続した箇所の情報をもっていい感じにする

E

隣同士のスワップを何回やったら文字列を反転できるか

• 解けず。でも転倒数を使うっぽいということはわかった

AtCoder Regular Contest 105

A

A,B,C,Dを2つに分けて総和を等しくできるか

• 黙ってbit全探索
• 実はソートするとあり得る組合せを減らせるらしい

B

数列の最大値=最小値になるまで操作を繰り返すと結局残る数は?

操作：最大値のものをすべて最大値-最小値に置き換える

• setに突っ込んで愚直にやれば行けるのでは、TLEしたら考えるか
• 間に合ったので次へ。
• 本当はユークリッドの互除法の匂いがするよね

C

重さの違うラクダが隊列を組んで橋を渡る。橋のパーツには長さと耐荷重がある。ラクダの先頭と末尾の距離を最小でいくつにできるか。どうやっても無理な場合もある

• 無理な場合は耐荷重が弱いものと重いラクダを比較して簡単にはじける
• ラクダの数が少ないので順列全探索ができる
• 耐荷重でソートしたい
• 長さはmax(長さ、自身より耐荷重が軽いものの長さ)としておく
• 各順列に対してラクダはその順にわたるものとして距離を求め最後にそれらのmin
• ラクダの列の全ての区間に対してそれぞれ最低限とるべき距離を二分探索で求める
• この制約を使ってDPをする
• TLEした。二分探索のlogが重いとみえる
• ラクダを1頭以上選んでできる重さの種類はあまり多くないので前もってbit全探索を使って計算しておくと間に合う

D

拡張したNim。N個の袋から1つ選んで中のコインをN枚の皿のどれかに全部出す操作をするところから始める

• 時間がないので適当に投げまくる。無理
• 結果的にCよりもDのほうが解かれてた。