{ }codelper
真偽値累乗P0132

権限ビットのチェッカー

あるサービスは、ユーザーの権限を一つの整数(権限値)にまとめて持っている。
一行目に権限の数 k が与えられ、二行目に権限名 k 個が空白一つずつで区切って与えられる。
前から 0 番目、1 番目、…、(k-1) 番目の権限とし、i 番目の権限は値 2^i に当たる。
権限値を二進数で書いたとき、2^i の桁が 1 なら i 番目の権限を持ち、0 なら持たない。
たとえば権限が read write delete admin の順なら、権限値 5(= 1 + 4)は read と delete を持つ。
三行目に質問の数 q が与えられ、続く q 行に質問が一つずつ与えられる。
質問は、権限値、方式、一つ以上の権限名を空白一つずつで区切ったものである。
方式が "all" なら書かれた権限をすべて持つとき、"any" なら一つでも持つとき、"none" なら一つも持たないときに合格である。
質問ごとに、合格なら "はい"、そうでなければ "いいえ" を一行に出力せよ。

入力
1 ≤ k ≤ 30、権限名は英小文字 1~10 文字で互いに異なる、1 ≤ q ≤ 1,000、方式は all・any・none のいずれか、0 ≤ 権限値 < 2^k、質問の権限名はリストにあり互いに異なる
出力
質問ごとに "はい" または "いいえ" を一行
例 1 · stdin
4
read write delete admin
5
5 all read delete
5 all read write
2 any read delete
2 any write admin
8 none read write
stdout
はい
いいえ
いいえ
はい
はい
main.py
入力(stdin)

実行すると、これらの行が順に input()・標準入力に渡されます(実行中に入力を求めません)。

$ 準備完了

コードを入力して解くにはパソコンで開いてください。モバイルでは問題と解答を見られます。

ほかの言語では?言語別の解答を見る · 8 言語の解答

i 番目の権限の値 2^i は、C・C++・Java・C#・JS・TS・Python のどれでもビットシフト 1 << i で正確に得られます。
Python の 2 ** i、Java・C# の Math.pow/Math.Pow(実数を返す)でもできますが、2 の累乗には整数のままの 1 << i がいちばんすっきりします。
2 ^ i は累乗ではなくビット XOR なので(2 ^ 0 = 2、2 ^ 1 = 3)、エラーなしに違う権限を調べます。
Craykon にはビット演算も累乗の演算子もないので、1 から 値 *= 2 で倍々に表を作り、数学.商(mask, 値) % 2 == 1(2^i で割った商が奇数)でその桁が立っているかを見ます。
演算子の優先順位の落とし穴:C・C++・JS・TS で mask & bit != 0 は != が先なので mask & 1 になり、おかしな答えになります。
必ず (mask & bit) != 0 と括弧をつけます。
Java・C# では同じ式が int と bool を混ぜたとしてコンパイルエラーになるのですぐ気づき、Python は & が比較より先なので括弧なしでも正しいです。
真偽値の落とし穴:C・C++ は 0 でない整数を真とみなしますが、Java・C# は if (mask & bit) を受けつけず、本物の boolean が必要です。
C は <stdbool.h> の bool、Craykon は 真/偽 です。
all は真から始めて && で、any は偽から始めて || で集めます。
Python の all/any、JS・TS の every/some が同じことをします。
none は「any でない」であって「all でない」ではありません。
一部だけ持つユーザーで二つが分かれます。
1 << i は 32 ビットの int なので i が 31 だと負の数になり、Java・C#・JS・TS はシフト数を 32 で割った余りしか使わないので 1 << 32 は 1 になります(C・C++ では未定義動作)。
権限が 32 個を超えるなら 64 ビット整数(1L << i、1LL << i、JS・TS は BigInt)が必要ですが、この問題は k ≤ 30 なので大丈夫です。

Pythonmain.py · 15 行
k = int(input())names = input().split()bit_of = {name: 1 << i for i, name in enumerate(names)}  # i번째 권한의 값은 2^iq = int(input())for _ in range(q):    t = input().split()    mask, mode, wanted = int(t[0]), t[1], t[2:]    has = [mask & bit_of[w] != 0 for w in wanted]  # Python은 &가 !=보다 먼저 계산된다    if mode == "all":        ok = all(has)    elif mode == "any":        ok = any(has)    else:  # none        ok = not any(has)    print("はい" if ok else "いいえ")
JavaScriptmain.js · 16 行
const lines = require("fs").readFileSync(0, "utf8").split("\n");const names = lines[1].trim().split(/\s+/);const bitOf = new Map(names.map((name, i) => [name, 1 << i])); // i번째 권한의 값은 2^iconst q = Number(lines[2]);const out = [];for (let j = 0; j < q; j++) {  const [m, mode, ...wanted] = lines[3 + j].trim().split(/\s+/);  const mask = Number(m);  const has = wanted.map((w) => (mask & bitOf.get(w)) !== 0); // 괄호 필수: !==가 &보다 먼저다  let ok;  if (mode === "all") ok = has.every((h) => h);  else if (mode === "any") ok = has.some((h) => h);  else ok = !has.some((h) => h); // none  out.push(ok ? "はい" : "いいえ");}console.log(out.join("\n"));
TypeScriptmain.ts · 17 行
import { readFileSync } from "node:fs";const lines: string[] = readFileSync(0, "utf8").split("\n");const names: string[] = lines[1].trim().split(/\s+/);const bitOf = new Map<string, number>(names.map((name, i) => [name, 1 << i])); // i번째 권한의 값은 2^iconst q = Number(lines[2]);const out: string[] = [];for (let j = 0; j < q; j++) {  const [m, mode, ...wanted] = lines[3 + j].trim().split(/\s+/);  const mask = Number(m);  const has: boolean[] = wanted.map((w) => (mask & bitOf.get(w)!) !== 0); // 괄호 필수: !==가 &보다 먼저다  let ok: boolean;  if (mode === "all") ok = has.every((h) => h);  else if (mode === "any") ok = has.some((h) => h);  else ok = !has.some((h) => h); // none  out.push(ok ? "はい" : "いいえ");}console.log(out.join("\n"));
JavaMain.java · 30 行
import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.HashMap;import java.util.Map; public class Main {    public static void main(String[] args) throws Exception {        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));        int k = Integer.parseInt(in.readLine().trim());        String[] names = in.readLine().trim().split("\\s+");        Map<String, Integer> bitOf = new HashMap<>();        for (int i = 0; i < k; i++) bitOf.put(names[i], 1 << i); // i번째 권한의 값은 2^i        int q = Integer.parseInt(in.readLine().trim());        StringBuilder out = new StringBuilder();        for (int j = 0; j < q; j++) {            String[] t = in.readLine().trim().split("\\s+");            int mask = Integer.parseInt(t[0]);            String mode = t[1];            boolean all = true, any = false;            for (int w = 2; w < t.length; w++) {                boolean has = (mask & bitOf.get(t[w])) != 0; // Java는 int를 참·거짓으로 쓸 수 없어 != 0이 꼭 필요하다                all = all && has;                any = any || has;            }            boolean ok = mode.equals("all") ? all : mode.equals("any") ? any : !any;            out.append(ok ? "はい" : "いいえ").append('\n');        }        System.out.print(out);    }}
C#Main.cs · 32 行
using System;using System.Collections.Generic;using System.Text; class Program{    static void Main()    {        int k = int.Parse(Console.ReadLine());        string[] names = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries);        var bitOf = new Dictionary<string, int>();        for (int i = 0; i < k; i++) bitOf[names[i]] = 1 << i; // i번째 권한의 값은 2^i        int q = int.Parse(Console.ReadLine());        var sb = new StringBuilder();        for (int j = 0; j < q; j++)        {            string[] t = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries);            int mask = int.Parse(t[0]);            string mode = t[1];            bool all = true, any = false;            for (int w = 2; w < t.Length; w++)            {                bool has = (mask & bitOf[t[w]]) != 0; // C#은 int를 bool로 쓸 수 없어 != 0이 꼭 필요하다                all = all && has;                any = any || has;            }            bool ok = mode == "all" ? all : mode == "any" ? any : !any;            sb.Append(ok ? "はい" : "いいえ").Append('\n');        }        Console.Write(sb);    }}
C++main.cpp · 34 行
#include <iostream>#include <sstream>#include <string>#include <unordered_map> int main() {    int k;    std::cin >> k;    std::unordered_map<std::string, int> bitOf;    for (int i = 0; i < k; i++) {        std::string name;        std::cin >> name;        bitOf[name] = 1 << i; // i번째 권한의 값은 2^i    }    int q;    std::cin >> q;    std::string line;    std::getline(std::cin, line); // q 뒤에 남은 줄바꿈    for (int j = 0; j < q; j++) {        std::getline(std::cin, line);        std::istringstream ss(line);        int mask;        std::string mode, w;        ss >> mask >> mode;        bool all = true, any = false;        while (ss >> w) {            bool has = (mask & bitOf[w]) != 0; // 괄호 필수: != 가 & 보다 먼저 계산된다            all = all && has;            any = any || has;        }        bool ok = mode == "all" ? all : mode == "any" ? any : !any;        std::cout << (ok ? "はい" : "いいえ") << '\n';    }}
Cmain.c · 32 行
#include <stdbool.h>#include <stdio.h>#include <string.h> int main(void) {    int k;    char names[30][11];    scanf("%d", &k);    for (int i = 0; i < k; i++) scanf("%10s", names[i]);    int q;    scanf("%d", &q);    for (int j = 0; j < q; j++) {        int mask;        char mode[5];        scanf("%d %4s", &mask, mode);        bool all = true, any = false;        /* 이름들은 줄 끝까지 이어진다: 다음 글자가 줄바꿈이면 멈춘다 */        int c;        while ((c = getchar()) == ' ') {            char w[11];            scanf("%10s", w);            int i = 0;            while (strcmp(names[i], w) != 0) i++;            bool has = (mask & (1 << i)) != 0; /* 괄호 필수: != 가 & 보다 먼저 계산된다 */            all = all && has;            any = any || has;        }        bool ok = strcmp(mode, "all") == 0 ? all : strcmp(mode, "any") == 0 ? any : !any;        puts(ok ? "はい" : "いいえ");    }    return 0;}
Craykonmain.cray · 44 行
// 크레이콘에는 비트 연산이 없다: mask를 2^i로 나눈 몫이 홀수이면 i번째 비트가 켜져 있다켜졌나(mask, 값){    返す 数学.商(mask, 값) % 2 == 1;} k = コンソール.行読み().数に();names = コンソール.行読み().分ける();bitOf = 辞書();값 = 1;繰り返す (i = 0; i < k; i++){    bitOf[names[i]] = 값; // i번째 권한의 값은 2^i: 1에서 시작해 두 배씩    값 *= 2;}q = コンソール.行読み().数に();繰り返す (j = 0; j < q; j++){    t = コンソール.行読み().分ける();    mask = t[0].数に();    mode = t[1];    모두 = 真;    하나라도 = 偽;    繰り返す (w = 2; w < t.個数; w++)    {        있음 = 켜졌나(mask, bitOf[t[w]]);        모두 = 모두 && 있음;        하나라도 = 하나라도 || 있음;    }    ok = 偽;    もし (mode == "all")    {        ok = 모두;    }    でなければ もし (mode == "any")    {        ok = 하나라도;    }    でなければ    {        ok = !하나라도;    }    コンソール.書く(ok ? "はい" : "いいえ");}