アジの開きを閉じる。

競プロ(AtCoder)中心のブログ

【随時更新】競プロでちょっと便利な実装Tips(C++)

C++ 備忘録

便利だなーと思ったTips．(C++)

vectorの要素出力で，スペース区切りで最後に改行

for(int i = 0; i < vec.size(); i++) {
  cout << vec[i] << " /n"[i + 1 == vec.size()];
}

vector⇄set の生成

コンストラクタを使う．

// vector→set
set<int> st(vec.begin(), vec.end());

// set→vector
vector<int> vec(st.begin(), st.end());

set, mapの要素全取得

for-eachを使う．

// set
for(auto val : st) {
  // ...
}

// map
for(auto [key, val] : mp) {
  // ...
}

pair, tupleの分解

構造化束縛を使う．

//pair
auto [a, b] = p;

// tuple
auto [a, b, c] = t;

グリッドで隣接する八方を調べる

差分-1~1の二重for．dx=0, dy=0はcontinueすることに注意！

// x: 今見ているマスのx座標
// y: 今見ているマスのy座標
for(int dx = -1; dx <= 1; dx++) {
  for(int dy = -1; dy <= 1; dy++) {
    if(dx == 0 && dy == 0) continue;

    int nx = x + dx;
    int ny = y + dy;
    // ...
  }
}

枠内チェックも一緒にしちゃう版．

for(int nx = max(x - 1, 0); nx <= min(x + 1, h - 1); nx++) {
  for(int ny = max(y - 1, 0); ny <= min(y + 1, w - 1); ny++) {
    if(nx == x && ny == y) continue;

    // ...
  }
}

【ゲーム】HTTPステータスコードで神経衰弱するゲームを開発しました

開発 React

Reactで何か作りたいけどネタがない，，，
そういえばHTTPステータスコード忘れてきてるな，，，

せや！！！

＼＼爆誕／／
HTTPステータスコード神経衰弱(プレイページ)
開発リポジトリ

プレイ中の画像
プレイ中の画像

目次

どんなゲーム？

HTTPステータスコードはWEB開発の基本中の基本です．
そんなHTTPステータスコードを楽しみながら覚えられるようなゲームを作りました．
以下の3つのモードで遊ぶことができます．

  • CPUと対戦: コンピュータと対戦できます．強さは「弱い」「普通」「強い」から選べます．
  • 2人で対戦: ローカルで2人で対戦できます．
  • トレーニング: 1人でプレイできます．

工夫したところ

今回は実装練習重視だったのと，個人的にシンプルなUIが好きなので，UIはAnt Designをそのまま使っています．
画面は「モード選択」「ゲーム設定」「プレイ画面」の3つの画面を作成し，以下のことを意識しました．

  • 画面の共通化: どのモードでも画面構成はほぼ同じなので，選択したモードやゲーム設定をContextに持たせて画面の出し分けを行い，実装量を減らしました．
  • UIとロジックの分離: 実装していると，カードの出し分けを行うUIの処理と神経衰弱のゲームロジックの処理が混在した巨大なファイルが出来上がってしまいました．そこで，UI処理はpage.tsxのそのままに，ゲームロジックをカスタムフックに切り出して分離しました．かなり実装しやすくなりました．

開発で難しかったところ

2つあります．

その1: 再レンダリングのタイミング

実装では，カードの表・裏の状態はopenedというboolean型配列のstateで管理していました．
カードのonClick関数が走ると，openedをtrueに変更することでそのカードが裏返るCSSを当て，再レンダリングされた瞬間から500msかけて裏返る(ように見える)ようになっています．
1枚目のカード選択はそれで良いのですが，2枚目のカード選択後は，裏返ってから，ペアならばカードが除去されペアでなければ再び裏返るようにしないといけません．

Reactは基本的にstateを更新する処理が実行されると，すぐに再レンダリングしてしまいます．
そのためonClick関数の中でopenedをfalseに戻したり，カードが場にあるかを管理する別のstateを更新してしまうと，カードが表向きになるモーションが起こらなかったり，表向きになる前に除去されたりしてしまいます．

理想は「onClickが走る→カードの再レンダリング→裏返るモーション→カードの再レンダリング→再び裏返るモーションor除去」です．
つまり，onClickが走るタイミングと2回目の再レンダリングには時差があります．

そこで今回は，onClickの中でsetTimeoutを呼び出し，1500ms後に再度stateを更新して再レンダリングするようにして実現しました．

setState関数が実行するタイミングや，setState関数に値では無くコールバック関数を渡した場合の挙動などが勉強になりました．

CPUの連続した選択もsetTimeoutをネストした1ターン分の処理を，再帰で呼び出して実現しています．(setTimeoutのネストは正直好きではないですが，，，)

その2: CPUのアルゴリズム

CPUのカード選択のアルゴリズムは思っていたより大変でした．
過去に裏返った既知のカードの情報から強さに応じて選択の仕方を変える実装が難しかったです．

ペアを作るかどうかは生成した乱数が強さに応じた閾値を超えるかどうかで判定すれば良いです．*1
ただペアを作らなかった場合にわざと外す2枚を選ぶのか，未知のカードの中から選ぶのかは場の状況に依ります．（すべて既知ならわざと外さないといけないし，未知のカードがあるならまずはそこから1枚選ぶ）

結局は人間の行動を模倣しているのですが，場の状況と確率的判定と組み合わせた選択をコードに書き起こすのに苦労しました．
もしかしたら上手いまとめ方があるのかもしれません．
プレイ中，CPUのターンが1枚選んで終わってしまうことがあります．発生条件や原因はよく分かっていません．アルゴリズムのバグではないはずです．バグってたらごめん！

また，UIへの反映も工夫したところです．
先述の通りstateの更新と再レンダリングは密接な関係があるので，先にCPUの選択するカードをすべて決定してから，setTimeoutを呼び出す関数を再帰して1手ずつ描画しました．*2
競プロやってなかったら「そうだ，京都，行こう．」のノリで「そうだ，再帰，実装しよう．」なんて思わないぞ！！！？！

既知のカードの情報はUIには直接関係ないのでstateではなくrefで管理することも意識しました．

最後に

せっかくなのでGitHub ActionsでGitHub PagesのBuild&Deployも行ってみました．
deployブランチを変更するだけでBuild&Deployしてくれるのはかなり楽で嬉しいですね．

次は何作ろうかな～！！(ネタが無い)

*1:実装では閾値を超えると選択しない．

*2:今思えばrefは常にリアルタイムの値を取得できるので，「CPUのターンで先にすべての選択を決定してからUIに反映」じゃなくても良かったかも．

【精進支援ツール】AtCoder Editorial Problemsを開発しました

ツール 開発 React

AtCoderの問題を解説の筆者から検索することができるWebアプリ「AtCoder Editorial Problems」を開発しました！

開発リポジトリ: AtCoderEditorialProblems(GitHub)

これは使用した技術や工夫の記録です．

AtCoder Editorial ProblemsのTOPページ．

目次

AtCoder Editorial Problems(AEP)とは？

AEPは，AtCoderの問題を解説の筆者から検索することができるWebアプリです．
PDFで解説を配布していた昔のコンテストを除き，ABC/ARCのすべての公式/ユーザー解説を検索することができます！

「この人の解説は自分に合っているな～」と思ったときに超便利です．

開発中のあれこれ

Writer(問題を書いた人)に得意不得意がある人は一度は思ったことがあると思います．

「苦手Writerの対策をしたいな～～～～」

って．

これが開発のきっかけでした．
それまではWriter経験のある人が自身のブログにまとめる程度で，まとまって情報を入手できる場所がありませんでした．

なので作ることにしました．
ちょうど「一度はWebアプリを作ってみたいけど題材が無い状態」だったので，自分の学習のためにももってこいのアイデアでした．

公式解説の筆者がその問題のWriterだと思っていたので(たぶん多くの人がそう思っている)，当初はそのように定義したWriterから問題検索できるように開発していました．
しかし目標だった年内リリースの期限直前!! 12/30に，

  • 公式に公表されていない「問題ごとのWriter」を決めつけてサービス提供するのはどうなのか．
  • おっと，Writerが解説も書いているとは限らないぞ．
  • はたまた1問題1Writerとも限らないぞ．

などの懸念があり，急遽「Writerから問題検索できる」から「解説の筆者から問題検索できる」に変更しました．(リリース直前にサービス内容変更ができるのも個人開発の良くない醍醐味？)
流石に変更に合わせてシステムを全改修するのは間に合わないので，一旦公式の筆者だけ検索できる状態のままリリースし，4日でPDF以外のすべての解説を検索できるようにしました．

結果としてやりたかったことがそのまま形になった訳ではないですが，解説の好みも人によってはあると思うし，自分もあるので，これはこれで「確かにあると便利なサービス」だったのではないかなと思います．

ちなみに検索結果で公式解説なのかユーザー解説なのかが分かるので，当初描いていた「Writerからの問題検索」という使い方もできます．しめしめ．

開発で大切にしたこと

下手にいろいろな技術に手を出さない

高度な技術や便利なライブラリに下手に触れませんでした． 理由としては，

  • 開発は「自分の学習のため」でもあり基礎を学びたかったから．
  • 高度な技術はそれなりに学習コストが高いから．
  • 初めての技術が多すぎると脳がパンクするから．
  • 初めての技術をいろいろ採用しすぎて，「結局なにもわからなかった」となるのは避けたかったから．
  • よく分からない技術をよく分からないままに使用するのは嫌だったから．(セキュリティ的にもこわい)

です．
具体的にはAWSやReact，Next.jsの基本的な使い方の習得に集中したかったので，便利なライブラリとかIaCとかは採用しませんでした．

あえて泥臭い実装をすることで，いざ高度な技術や便利な技術を学んだときのインパクトが強く，そのときの学習効果も高いと思っています．

また，例えばDBだと本音はDynamo DBを使ってみたかったのですが，やるならDB設計からちゃんと学びたくそれはそれで学習に時間がかかるので，使用経験のあるPosgreSQLを採用しました．

年内リリース

「個人開発のコツは期限を決めること！！」(らしい)

7月にTwitterで期限を宣言しました．

この時点ではReactは知っていたもののNext.jsは名前も聞いたことが無く，AWSも「なんかAPI Gateway+Lambdaで簡単にAPIがつくれるらしい」程度でした．

別に期限を決めなくても開発はするのですが，決めた理由は以下の通りです．

  • 割と誰でも思いつき，かつ開発も難しくはないであろう単純なサービスだったので，誰かに先を越される可能性が高いと感じたため．
  • 長期間作り込んでリリースしたもののウケなかったら悲しいため．
  • 早めにニーズを確認したかったため．

平日は仕事にエネルギーを費やしていたので，土日に開発を進めていました．

結果，12/31 19:05にリリースすることができました！
ギリギリになったのは思っていたよりもデプロイに手間取ったためです．

年末恒例の紅と白に分かれて歌合戦する某番組が始まる前で良かった！

採用した技術

採用しなかった技術

今後リファクタリングや学習の一環で採用する可能性はあります．

  • Chakra UI
    • Ant Designと両方使ってみた結果，理想のUIを実現するには使いにくいと感じたため．
    • 検索機能付きSelectが公式には無かったため．非公式で誰かがGitHubに上げていたが理想のUIではなかった．
  • Dynamo DB
    • 先述の通り，期限に対して学習コストが高いため．
  • 独自ドメイン
    • 最初は独自ドメインに憧れていたが時間的に今後も個人開発を行っていくとは限らないため．取得はいろいろ開発するようになってからでも遅くはない．
    • このアプリ特有のドメイン取得もチラついたが，サ終後に手放したドメインが悪意を持ったユーザに利用され，Twitterやこの記事で宣伝時に貼ったURLやブックマークからアクセスしたら変なサイトが開いて困る人が出るかもしれないと考えたため．
    • そんなときにちょうど変なドメイン取るな!!!.netを見かけ，強く決意したため．
  • GitHub Actionsによるデプロイ
    • 期限まで時間が無かったため妥協．

こだわりポイント

  • UX
    • 動きのある派手な画面よりシンプルで使いやすいのが一番．
    • 提示する情報や機能も最低限に．
      • 例えばAGCの問題を収集しても良いが，ほとんどのユーザにとっては不必要なタブが生まれる．選択時に認知負荷を少しでも低減させるために無駄なタブは削ぎ落とした．
  • 問題や解説の筆者の情報は自前のDBに保存
    • 検索の度に外部へリクエストをすると，本サービスを踏み台にしたDDoS攻撃になりうるため．
    • 外部へのリクエストは1秒おきに投げるようにしている．
  • Sliderによるdiffフィルター
    • 大発明では！？
    • 数値で範囲指定する方法など考えたが，色でフィルタリングできるSliderが直感的で良いと感じた．
    • Sliderを少しでも動かす度に範囲内の色を再レンダリングしているため，よく見ると少しガタつくのが惜しい．

最後に

自分でイチから考えて，好きなサービスを開発するのって楽しい！！
特に「ここはこうした方がユーザーは使いやすいんじゃないか」とユーザー指向で作っていくのが楽しかったです．

また，規模や出来にかかわらず自力で一つサービス開発した経験って，結構大きいと思いました．1年前の自分には全く考えられません．

これは自分への教訓ですが，どんなに汚い実装だと自分で思っていてもどんどん実装していくのが良いです．
自分は変数名一つでも考え込むので，後々相当悪い影響が想像できる場合でない限りは「一旦これでいいや」として先に進み，「DB構築できた」とか「API作ってブラウザから叩けた」とかどんどん実績解除していくのがモチベにも繋がって良いと思いました．

この記事が，誰か(読み返している未来の自分もだぞ)の開発のきっかけになれば嬉しいです．

次は何作ろうかなー．

ここまで読んでいただきありがとうございました！

AHC022 参加記 (RECRUIT 日本橋ハーフマラソン 2023夏)

AHC 備忘録

2023/08/11(金)12:00 ~ 08/20(日)19:00 の約1週間，RECRUIT 日本橋ハーフマラソン 2023夏(AtCoder Heuristic Contest 022) が行われました．

AHC参加5回目，Heuristic緑色の私は暫定427位/最終421位というまずまずの結果でしたが，取り組む中でいろいろ勉強になったので参加記を書きます．

前回の参加記は参加3回目のときで，人によっては1回飛んでるように感じられるかもしれません．気のせいです．

目次

問題概要

N個のワームホールがあり，入口と出口の対応を当てるゲーム．入口と出口は1対1に対応しており，異なる入口から入って同じ出口に出ることはない．
手がかりになるのは，温度．
あらかじめグリッド上の全てのマスに温度を設定しておき，任意のワームホールから入って，対応する出口から好きなだけ動いた位置で計測した温度を頼りにする．

難しいポイントは，

  1. 計測段階ではどの出口が対応しているのかは分からない
  2. 計測値は「真の温度+ノイズ」．ノイズはめっちゃ大きいケースもある

考察

とりあえずサンプルコードを提出して出席点をいただく．
絶対得点3,467,623点．

サンプルコードでは，各出口に10刻みで温度を設定して目印を付け，出口の計測値と最も近いものを推定結果としていた．
正直，これより良い解法がパッと思いつかなかったので，今回もダメかなーと半ば諦めモード．

せめて温度変化をなだらかにした方がコストが減ってマシになりそう．
それならグリッドの中心を0にして縁のほうへ離れるほど高温にしたほうが全体的によさそう．
じゃあ中心に近い出口から順に10刻みで温度をつけて，全体を均せばよさそう．

中心に近い出口から温度を設定する：各出口について中心からのマンハッタン距離を計算し，昇順ソートしたものに10刻みで温度設定．
全体的に均す：出口以外は周囲4マスの平均をとる．これを10,000回繰り返すと全体的にいい感じになった．(多分安定するまで10,000回もいらない)

seed=0．「綺麗なグラデーションだね」「君の方が綺麗だよ．」

75,704,338点．1ケタ伸びた！
温度分布はマシになったが，出口は10刻みなのでちょっとノイズが大きくなるだけで精度が悪化する．

ノイズの影響をもろに受ける1点計測だから良くないのかな．
周囲4方向にちょっと離れたマスの温度も計測して，計5点の平均を推定値にしてみたけど，あんまり良くならなかった．

さて，何も思いつきません．助けて～．

どうにもならないので，過去の類似のAHCを探して，その上位解法をパクる参考にすることにする．

そういえば，「ノイズ付きのoutputからinputを推定する」という構造がAHC016 Graphoreanに似ている．
公式解説やユーザ解説を見ていく．

上位解法は解説を読んでもよく分からない．公式解説を見てみると，何やら確率を使ってる．いかにも推定って感じ．
ふむふむ，各inputから計測値(output)が生まれる確率を計算し，最も高いものを推定結果としているのか．
これなら今回もできそう．

今回は入力で与えられるSを使って，平均0，標準偏差Sの正規分布からサンプリングした値がノイズとなっている．
これより，ある計測値に対し，各出口で真の温度とSの値を元にz得点を計算し，正規分布で±z得点以上の範囲の面積(確率)を算出．確率が最も高いものを推定結果とする．

z得点の計算は良いとして，面積の算出はどうやるの？積分するプログラム書けるの？？

知らん知らん！そんなもんは知らん！！
標準正規分布表からベタ書きじゃい！！！

ベタ書き．これも一つの手．

はい提出提出～！！
211,911,324点！！！
うぇ～～～い(また1ケタ伸びた)

そしてこのまま，ちょっとだけパラメータ調整して最終提出を迎えました．

最終提出

  • 配置
    • 各出口に，中心からマンハッタン距離で近い順に10刻みで温度を設定．
    • その後，配置時コストを減らすために全体を均す．
  • 計測
    • S=1の場合
      • 出口を1点計測．
      • 各出口についてその計測値以上に誤差のある値が計測される確率(の半分)を算出．最も確率の大きいものを推定結果とする．
    • S>1の場合
      • 出口1点と周囲4方向に7マス離れた地点の，計5点計測．
      • 計測した5点それぞれでS=1と同様に確率を算出．それらを掛け合わせた確率が最も大きいものを推定結果とする．

結果

seed=0

seed2(S=81)．この程度のSまではほぼ完答できる．

成績表

次に生かせそうな知識・テク

  • output(計測値)が得られる確率から推定する
    • 推定の基本的な考え方だと思う．
  • 詰まったら過去の類似回を参考にする
    • 今回に応用できるかな？などと考えるので記憶に残りやすい．
  • 簡単なケースでは着実に点を取る
    • AHC016公式解説でwataさんが「今回の点数計算式を見ると，ノイズが大きいときに1個でも多く当てるよりも，ノイズが小さいときに確実に当てるのが大事」というようなことを仰っていた．
    • 今回もそうなのかは分からないが，小さいノイズのケースで確実に当てるのは，同様のアルゴリズムを採用した集団の中でも高い順位を狙うという点で重要だと思う．今回はS=1だけ低コストで確実に当てるようにした．
  • 小数の積はlogを使う
    • kusanoさんのAHC016参加記で書かれていたが，小数の積をすると浮動小数点数の精度が足りなくなることがある．そんなときはlogを取って足し算すれば良い．
    • 今回は4回の掛け算で，足りる精度だったので採用しなかった．

コメント

  • 300位以内に入れるより上位の解法では1点だけ1000，他は0の温度設定にする，というものがあった．温度設定は全体的に均すべき，という固定観念では思いつかなかった，，，(Minecraftでちゃんと拠点に戻れるように土の塔を作るのと似てる？)
  • 今回ベタ書きした確率の求め方をより高い精度で求める方法をご存じでしたらご教授ください><

【解説】ABC310 B - Strictly Superior

ABC 解説

執筆時レート：水色

問題文→https://atcoder.jp/contests/abc301/tasks/abc310_d
公式解説→https://atcoder.jp/contests/abc301/tasks/abc310_d/editorial

目次

問題

N 個の商品がある．
各商品には価格と機能が以下のように定義されている．

  • 商品 i の価格は P_{i}
  • 商品 i の機能は C_{i} 個あり， j 番目の機能は 1 以上 M 以下の整数 F_{i,j} として表される

このとき，以下の条件を全て満たすような商品 i ，商品 j の組は存在するか？

  • P_{i} \geq P_{j}
  • 商品 j は商品 i がもつ機能をすべてもつ
  • P_{i} > P_{j} であるか，商品 j は商品 i にない機能を 1 つ以上もつ

制約

  • 2 \leq N \leq 100
  • 1 \leq M \leq 100
  • 1 \leq P_{i} \leq {10}^{5}
  • 1 \leq C_{i} \leq M
  • 1 \leq F_{i,1} \lt F_{i,2} ... \lt F_{i,C_{i}} \leq M
  • 入力は全て整数

解説

まずは全探索を考えるのが基本．
全ての組 (i,j) について，問題文の条件を全て満たすものがあるか調べる．

問題文の条件が何を意味しているのかが分からないときは，言葉で表現してみると分かりやすくなるかも．

  • P_{i} \geq P_{j}

これは「商品 j の方が安いか，同じ価格」．

  • 商品 j は商品 i のもつ機能をすべてもつ

これはそのままの意味．
「商品 j は商品 i 以上に多機能」とも言い換えられる．

  • P_{i} > P_{j} であるか，商品 j は商品 i にない機能を 1 つ以上もつ

価格については「商品 j の方が安い」ということ．
機能についてはそのままの意味だが，二つ目の条件を満たしているときは，「商品 j の機能 = 商品 i の機能 + α 」，つまり「商品 j の方が多機能」ということになる．

このような3条件を全て満たす組があるか調べれば良い．

計算量はどうだろう．
調べる組み合わせの数は O(N^{2}) で，ある組 (i,j) について各条件の判定に，

  • P の比較をすれば良いので O(1)
  • 商品 i の各機能が商品 j に含まれているか素朴に調べて O(M^{2})
  • 価格の比較も機能数の比較も O(1) なので，合わせて O(1)

これだと全体の計算量は， O(N^{2}M^{2}) となり，今回の制約だとまあ間に合うかな，という感じ．(C++の処理の速さを信じて)
他の言語だと間に合わないかもしれないし，定数倍がこわいときは，set(集合に対して所属判定を \log (サイズ) で行える構造体)を使えば高速化が図れる．
具体的には，判定では O(M^{2}) がボトルネックになっているので，商品 j の機能をまとめたsetに対して商品 i の各機能が含まれているかを調べれば，判定は O(M \log M) ，全体で O(N^{2}M \log M) になる．

さらに，各商品について「あり得る M 個の機能のうち持っているものにフラグを立てる」という管理をすれば，二つ目の条件の判定を O(M) ，全体で O(N^{2}M) に落とせる．

実装

O(N^{2}M^{2}) 解法．余裕で間に合う．
提出

#include <bits/stdc++.h>
using namespace std;

int main(){
  // 入力を受け取る
  int n,m; cin>>n>>m;
  vector<int> p(n);
  vector<vector<int>> func(n);
  for(int i=0; i<n; i++) {
    cin>>p[i];
    int c;cin>>c;
    for(int j=0; j<c; j++) {
      int f; cin>>f;
      func[i].push_back(f);
    }
  }

  // 判定
  for(int i=0; i<n; i++) {
    for(int j=0; j<n; j++) {
      if(p[i]>=p[j]){
        // 一つ目の条件を満たしている

        // 二つ目の条件「商品jが商品iの機能をすべて含んでいるか」を調べる
        bool inc=true; // 商品iの機能をすべて含むか？
        for(auto fi: func[i]) {
          // 商品iのある機能fiが商品jにあるか？
          bool exist=false;
          for(auto fj: func[j]) {
            if(fi==fj) exist=true;
          }

          // 無ければすべて含んでいないということ
          if(!exist) inc=false;
        }
        if(!inc) continue;

        // ここまでで二つ目の条件を満たしている
        // 最後の条件を満たすか調べる
        if(p[i]>p[j] || func[i].size()<func[j].size()) {
          // すべての条件を満たしている！
          cout<<"Yes"<<'\n';
          return 0;
        }

      }
    }
  }

  // すべての組を調べても無かった
  cout<<"No"<<'\n';

  return 0;
}

setを使った O(N^{2}M \log M) 解法．
提出

#include <bits/stdc++.h>
using namespace std;

int main(){
  // 入力を受け取る
  int n,m; cin>>n>>m;
  vector<int> p(n);
  vector<set<int>> func(n);
  for(int i=0; i<n; i++) {
    cin>>p[i];
    int c;cin>>c;
    for(int j=0; j<c; j++) {
      int f; cin>>f;
      func[i].insert(f);
    }
  }

  // 判定
  for(int i=0; i<n; i++) {
    for(int j=0; j<n; j++) {
      if(p[i]>=p[j]){
        // 一つ目の条件を満たしている

        // 二つ目の条件「商品jが商品iの機能をすべて含んでいるか」を調べる
        bool inc=true; // 商品iの機能をすべて含むか？
        for(auto fi: func[i]) {
          // 商品iのある機能fiが商品jに無ければ，すべて含んでいないということ
          if(!func[j].count(fi)) inc=false;
        }
        if(!inc) continue;

        // ここまでで二つ目の条件を満たしている
        // 最後の条件を満たすか調べる
        if(p[i]>p[j] || func[i].size()<func[j].size()) {
          // すべての条件を満たしている！
          cout<<"Yes"<<'\n';
          return 0;
        }

      }
    }
  }

  // すべての組を調べても無かった
  cout<<"No"<<'\n';

  return 0;
}

O(N^{2}M) 解法．
提出

#include <bits/stdc++.h>
using namespace std;

int main(){
  // 入力を受け取る
  int n,m; cin>>n>>m;
  vector<int> p(n);
  vector<int> c(n);
  vector<vector<bool>> func(n,vector<bool>(m));
  for(int i=0; i<n; i++) {
    cin>>p[i]>>c[i];
    for(int j=0; j<c[i]; j++) {
      int f; cin>>f;
      f--;
      func[i][f]=true;
    }
  }

  // 判定
  for(int i=0; i<n; i++) {
    for(int j=0; j<n; j++) {
      if(p[i]>=p[j]){
        // 一つ目の条件を満たしている

        // 二つ目の条件「商品jが商品iの機能をすべて含んでいるか」を調べる
        bool inc=true; // 商品iの機能をすべて含むか？
        for(int k=0; k<m; k++) {
          // 機能kを商品iはもっているが商品jはもっていなければ，すべて含んでいないということ
          if(func[i][k] && !func[j][k]) inc=false;
        }
        if(!inc) continue;

        // ここまでで二つ目の条件を満たしている
        // 最後の条件を満たすか調べる
        if(p[i]>p[j] || c[i]<c[j]) {
          // すべての条件を満たしている！
          cout<<"Yes"<<'\n';
          return 0;
        }

      }
    }
  }

  // すべての組を調べても無かった
  cout<<"No"<<'\n';

  return 0;
}

ABC304 F - Shift Table

ABC

執筆時レート：水色

問題文→https://atcoder.jp/contests/abc304/tasks/abc304_f
公式解説→https://atcoder.jp/contests/abc304/editorial/6511

目次

問題

高橋君と青木君は N 日間アルバイトをする．
高橋君のシフト表は文字列 S で与えられ， S [i] が#ならば i 日目に出勤，. ならば i 日目に欠勤する．
一方，青木君は以下の手順でシフト表を作成する．

  • N でない N の正の約数 M をとる．
  • 1 日目から M 日目までの勤怠を決める．
  • i = 1, 2,...,N-M の順に M+i 日目の勤怠が i 日目の勤怠と一致するように M+i 日目の勤怠を決める．

※ M の値が異なる場合でも最終的なシフトが等しくなる場合があることに注意．
N 日すべてについて高橋君と青木君の少なくとも一方が出勤することになったとき，青木君のシフト表として考えられるものの個数を 998244353 で割ったあまりを求めよ．

制約

  • N は 2 以上 {10}^{5} 以下の整数
  • S は長さ N の#, .からなる文字列

方針

サンプルケース1で考えてみる．

  • N=6
  • S= ##.#.#

青木君のシフト表を T とする．
M=3 で考えてみる．
高橋君が欠勤する日は青木君は必ず出勤しなければならないので，最初の M 日間のうち何日かは出勤で確定する(?は出勤か欠勤か選べる)．

  • T[:M]=?##

よって M=3 の場合では {2}^{?の個数} で 2 通り！
同じように他の M でも求めて合計すればOK！
としたいところだが，?を#にしたときの T= ######は，
M=1,2 でも生成でき，重複して計上してしまう．

問題は重複をどう排除するか？になる．

このようなとき，(多分)2通りの考え方がある．

  1. パターンと1対1対応するものを数える
  2. とりあえず重複を区別して数えてからダブりを引く

1.は今回だとTの最小周期の文字列に対応させるという考え方．
例えば T= ######の最小周期は#なのでこれだけを直接数えるように頑張る．
でもムズカシイ．

2.は， M を全探索してどこかのタイミングでダブりを引く．
M を固定したとき，重複を区別すると {2}^{?の個数} というのは簡単．
どのようにしてダブりを引くか？

######を計上するのは1.と同じように最小周期で数えるとして， M がそれ以外の周期のときでは計上しないようにしたい．

M=3 と固定して考える．
.##.##のような，「 M が最小周期である場合」はここで初めて計上する．
一方，######のような，「 M が最小周期でない場合」は， M が最小周期のときに計上してるはずなので，ここでは計上しないようにする．

では「 M が最小周期でない場合」を引くために，最小周期と M の関係について調べてみる．

最小周期を t ( \lt M ) とすると弱周期性補題より \gcd (t,M) も周期．
\gcd (t,M) \leq t であり， \gcd (t,M) \lt t と仮定すると t が最小周期であることに矛盾するので， \gcd (t,M) = t ． よって t は M の約数である．

つまり，「最小周期 \Rightarrow M でない M の約数」が成立する．

よって，各 M では「 M が最小周期である場合」を計上しているので，ある M が最小周期である場合の数は，

  • \displaystyle {2}^{?の個数} - \sum_{t \in {\{MでないMの約数\}}}{tが最小周期である場合の数}

で求められる． M が小さい方から全探索すればよい．

計算量

N の約数の個数を d(N) とする．
各 M について，?の個数を数えるのに O(N) ，ダブりを引くのに O(M) かかるので，結局 O(N) かかる．
よって，最終的な計算量は O(Nd(N)) となる．
今回の制約( N \leq {10}^{5} )では，Nの約数の個数は高々128個なので十分高速である．

実装

https://atcoder.jp/contests/abc304/submissions/41989568

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<n; i++)

/* Modint構造体(省略) */

// 約数列挙
vector<ll> divisor(ll n){
  vector<ll> ret;
  for(ll i=1;i*i<=n;i++){
    if(n%i==0) {
      ret.push_back(i);
      if(i!=n/i) ret.push_back(n/i);
    }
  }
  sort(ret.begin(),ret.end());
  return ret;
}
 
int main(){
  int n;cin>>n;
  string s;cin>>s;
 
  // nの約数列挙
  auto divs=divisor(n);
 
  // rem[i]:=最小周期がiである場合の数
  vector<mint> rem(n+1);
  // p2[i]:=2のi乗
  vector<mint> p2(n+1);
  p2[0]=1;
  rep(i,n) p2[i+1]=p2[i]*2;
  
  for(auto m:divs){
    if(m==n) continue;
 
    // 出勤/欠勤を選べる日数を数える
    int cnt=0;
    vector<bool> must(m);
    rep(i,n) {
      if(s[i]=='.'){
        must[i%m]=true;
      }
    }
    rep(i,m) if(!must[i]) cnt++;
 
    // 重複を区別した場合の数
    rem[m]=p2[cnt];
 
    // ここからダブりを引く
    for(int i=1;i<m;i++){
      if(m%i==0){
        rem[m]-=rem[i];
      }
    }
 
  }
 
  // remの合計が答え
  mint res=0;
  for(auto r:rem) res+=r;
 
  cout<< res <<'\n';
 
  return 0;
}

【解説】ABC301 D - Bitmask

ABC 解説

執筆時レート：水色

問題文→https://atcoder.jp/contests/abc301/tasks/abc301_d
公式解説→https://atcoder.jp/contests/abc301/tasks/abc301_d/editorial

目次

問題

0, 1, ?からなる文字列 S および整数 N が与えられる．
S に含まれる?をそれぞれ0または1に置き換えて2進数と見なしたとき， N 以下で最大のものを(10進数として)出力せよ．
ただし，そのような N 以下の値が存在しなければ，-1を出力せよ．

制約

  • S は0, 1, ?からなる文字列
  • 1 \leq |S| \leq 60
  • 1 \leq N \leq {10}^{18}
  • N は整数

解説

S にある?の個数を K とすると，作られる2進数は {2}^{K} 種類になる．
このうち N 以下で最大のものを見つけたい．
サンプルケース1で樹形図を書いてみる．

サンプルケース1の樹形図

ここで N がどこにあるか書き込むと，

N以下はOK

N 以下をOKとすると単調性が見えてきた．二分探索っぽい．

?を上の桁から見ていって，1にしてもOKのものが存在するなら1にしたら良い．存在しなければ0にする．
「OKのものが存在するか」というのは，単調性により，その桁を1にしたときの最小値がOKかどうかを見れば良い．
つまり，その桁以降の?をすべて0にした数がN以下かどうかを見れば良い．

?ではない桁はどう扱うか．
S では1で N では0だとその時点で必ず S が上回ってしまう．
その時点で答えが-1であることは確定する．
他の1と0の組のパターンはN以下であることが保たれるので問題ない．
下の実装では途中で処理を打ち切らずに，最終的な答えが N 以下であるか，後で評価している．

実装

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<n; i++)
using ll = long long;

int main() {
  string s;
  ll n;
  cin>>s>>n;

  int len=s.size();

  // よく使うので2のべき乗を前計算
  // p2[i]=2のlen-i-1乗の値
  vector<ll> p2(len);
  p2[len-1]=1;
  for(int i=len-2;i>=0;i--) p2[i]=p2[i+1]*2;

  ll res=0;
  rep(i,len) {
    // 上からi桁目を見る

    if(s[i]=='?') {
      // この桁を1にして，それ以降の?を0にした値がn以下か？
      ll val=res;
      val+=p2[i];
      for(int j=i+1;j<len;j++) {
        if(s[j]=='1') val+=p2[i];
      }

      if(val<=n) {
        // この桁を1として良い
        res+=p2[i];
      }

    }else{
      if(s[i]=='1') {
        res+=p2[i];
      }
    }
  }

  // 最後にn以下かチェック
  if(res<=n) cout<< res <<'\n';
  else cout<< -1 <<'\n';

  return 0;
}

楽な実装

公式解説(楽な実装)では，最初に S のすべての?を0に変えた値が N 以下かをチェックしている．

S から作られる数の最小値が N を上回っていれば，どう作っても N 以下になるはずが無いので答えは-1に確定．
そうでないならば，少なくともその最小値が N 以下であるから，上の桁から見ていくアルゴリズムで必ず答えが得られることが保証される．
上の実装でのresが，よくやる二分探索の実装(okとかngとか使うやつ)でのokのように常に N 以下の値を保持しているイメージがする．

なぜ上の桁から決めることが二分探索なのか？

上の桁から決めることで，表現されうる数の範囲が半分ずつに絞られていくからだ．

2進数3桁で表現できる数

ちなみに

今回のABC301では初めて配点が問題に応じて調整された．
今まで：100-200-300-400-500-500-600-600
今回　：100-200-300-400-475-500-600-625

配点と言えば，過去に@kyopro_friendsさんが触れていた．

2進数表記だと
1-10-100-1000-10000-100000-1000000-10000000

ここでQuestion.
コンテスト終了後の得点が2進数表記で10110101だったら，その人は全体でどの辺りに位置しているだろうか？
二分探索で考えてみてね．