外部サイトへ移動します

リンク先の URL を確認してから開いてください。

別タブで開く

解説

D - ANDORXOR

作成者 sevenc_nanashi

テスター unbakedbread

配点 250 点

実行時間制限
2 秒
メモリ制限
512 MiB

解説

まずSSを処理するところから始めます。

「カーソル」を使って、以下のように実装するのが良いでしょう:

  • まずカーソルをSSの最初の文字に置き、また演算子をいれる配列を作ります。
  • カーソルの指す文字がAの場合、ANDを配列に追加し、カーソルを3つ進めます。
  • カーソルの指す文字がOの場合、ORを配列に追加し、カーソルを2つ進めます。
  • カーソルの指す文字がXの場合、XORを配列に追加し、カーソルを3つ進めます。

では計算しましょう。これは3回に分けて行うのが良いでしょう。

ANDのみを処理した数列(スタック)BBと、AND以外の演算子を入れる配列ttを作ることを考えます。

  • まずBBにA1A_1を入れます。
  • その後、sis_iがANDの場合、BBの最後の要素とAi+1A_{i+1}をAND\text{AND}して、BBの最後の要素を計算結果で置き換えます。
  • sis_iがORまたはXORの場合、Ai+1A_{i+1}をBBに追加し、演算子をttに追加します。

これでANDの処理が完了したので、同様にORを処理したあとの数列CCを作り(演算子配列は処理後に全てXORになるので不要です)、その要素を全てXORで計算すれば最終的な結果が得られます。

計算量はO(N)O(N)です。

実装例(Ruby、201ms)

Bonus:配列を一回だけ走査する形で実装してみましょう。

ユーザー解説

ユーザー解説を書く

ユーザー解説はまだありません。