なんだかやる気がでないので競技に逃げ続けている。

A - 梱包できるかな？

向きを固定すれば、各方向に入る数の積で入る総数がでる。これを全ての荷物の向きに対して試せばよい。

最初問題文を少し勘違いして、Aなのに難しすぎるでしょどうやるんだ、ってなってた。

彼はとても几帳面な性格なので、荷物を全て同じ向きで梱包します。
ただし、荷物を横に90度倒すことはできます。

というのを、x,y軸の周りでは回転できないがz軸の周りでは回転できる、と誤読していた。

#include <iostream>
#include <algorithm>
#define repeat_from(i,m,n) for (int i = (m); (i) < (n); ++(i))
#define repeat(i,n) repeat_from(i,0,n)
using namespace std;
int main() {
    int a[3], b[3];
    repeat (i,3) cin >> a[i];
    repeat (i,3) cin >> b[i];
    sort(b, b + 3);
    int result = 0;
    do {
        int acc = 1;
        repeat (i,3) acc *= a[i] / b[i];
        result = max(result, acc);
    } while (next_permutation(b, b + 3));
    cout << result << endl;
    return 0;
}

始め難易度勘違いしてたのと、next_permutationの存在からc++。pythonにもitertools.permutationsってのがあるっぽいのでpythonで十分だった。

import Control.Applicative
import Data.List
main = do
    xs <- map read . words <$> getLine
    ys <- map read . words <$> getLine
    print . maximum . map (product . zipWith div xs) $ permutations ys

Bがhaskellで1行だったので、ついでにAもやってみた。

B - 引越しできるかな？

荷物それぞれについて各方向の大きさをソートして、1,2,3番目の方向それぞれについて最大値を取ればよい。

これも問題文勘違いして、少しの間絶望感につつまれてた。すぐに1つの箱に1つの荷物だと気付いて安堵した。

#!/usr/bin/env python3
c = int(input())
xs = 0, 0, 0
for i in range(c):
    ys = map(int,input().split())
    xs = map(max, xs, sorted(ys))
xs = list(xs)
print(xs[0] * xs[1] * xs[2])

これtransposeで一撃では、と思ったのでhaskellを書いた。でもpythonでもzip(*xss)と書けば転置できるようだ。

import Data.List
main = getContents >>= print . product . map maximum . transpose . map (sort . map read . words) . tail . lines

読めない。golfの点ではrubyに負けてた。

C - 笑いをとれるかな？

今の私にとって丁度よい難易度で考えてて楽しかった。

ただし1-indexedと0-indexedを取り違えて1WA。問題文中の図が3つ中2つ404していたのも原因の1つなので許されるべき。

問題

ハバネロがいくつか埋め込まれた豆腐がいくつか与えられる。豆腐を1つ選び座標軸に並行に切り片方を食べる、これを交互に繰り返す。先に食べた方の負け。必勝手番を求める。

解法

まず、豆腐が複数個存在することについて。これは明らかにゲームの和であり、1つの豆腐上のゲームのgrundy数を求める問題へと帰着される。

次に、豆腐のgrundy数について。豆腐の1辺の大きさは$10^9$と大きく、愚直に計算することはできない。 ここで、厚みが1で縦横共に$10^9$で左上にのみハバネロを持つ豆腐を考える。ハバネロを含む1x1x1の区画のみの状態から逆向きに考えていくと、その過程は縦軸と横軸それぞれの方向のゲームの和そのものであることに気付ける。よってこれを一般化し、ハバネロを含む長方形の区画の6つの面に鉛直な方向のゲーム6つの和で、1つの豆腐上のゲームが表せる。

解答

A,Bがhaskellゲーだったのでhaskell。

最初に書いたものは入力が大きいケースでTLEした。 !やseq付けたら縮んだけど全然足りなくて、haskellは競技プログラミングに向いていないのか、とか言ってた。 ByteStringを使うようにしたら100倍ほど高速化して通った。単に私の知識不足だった。なんだかちょっと恥ずかしい。

import Control.Arrow
import Control.Monad
import Data.Bits
import Data.List
import Data.Maybe
import qualified Data.ByteString.Char8 as B
readInt = fst . fromJust . B.readInt 
getInts = map readInt . B.words <$> B.getLine
main :: IO ()
main = do
    n <- readInt <$> B.getLine
    gs <- replicateM n $ do
        [x, y, z] <- getInts
        m <- readInt <$> B.getLine
        habaneros <- replicateM m getInts
        let [(xl,xr),(yl,yr),(zl,zr)] = map (minimum &&& maximum) $ transpose habaneros
        return $ foldl1 xor [xl, x - xr - 1, yl, y - yr - 1, zl, z - zr - 1]
    putStrLn . (\ g -> if g == 0 then "LOSE" else "WIN") $ foldl1 xor gs

haskellがなかなか通らないので一旦諦めてc++も書いた。

#include <iostream>
#include <vector>
#include <algorithm>
#define repeat_from(i,m,n) for (int i = (m); (i) < (n); ++(i))
#define repeat(i,n) repeat_from(i,0,n)
using namespace std;
int main() {
    int n; cin >> n;
    int g = 0;
    repeat (i,n) {
        int x, y, z; cin >> x >> y >> z;
        int m; cin >> m;
        vector<int> xs(m), ys(m), zs(m);
        repeat (j,m) cin >> xs[j] >> ys[j] >> zs[j];
        int xl = *min_element(xs.begin(), xs.end()); int xr = *max_element(xs.begin(), xs.end());
        int yl = *min_element(ys.begin(), ys.end()); int yr = *max_element(ys.begin(), ys.end());
        int zl = *min_element(zs.begin(), zs.end()); int zr = *max_element(zs.begin(), zs.end());
        g ^= xl ^ (x - xr - 1);
        g ^= yl ^ (y - yr - 1);
        g ^= zl ^ (z - zr - 1);
    }
    cout << (g == 0 ? "LOSE" : "WIN") << endl;
    return 0;
}

なぜ全問それぞれ2言語で書いてしまったのか。